論文の概要: Quantum Logarithmic Space and Post-selection
- arxiv url: http://arxiv.org/abs/2105.02681v1
- Date: Thu, 6 May 2021 14:02:01 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-01 07:59:26.811549
- Title: Quantum Logarithmic Space and Post-selection
- Title(参考訳): 量子対数空間とポスト選択
- Authors: Fran\c{c}ois Le Gall, Harumichi Nishimura, and Abuzer Yakary{\i}lmaz
- Abstract要約: ポストセレクション(Post-Selection)は、アーロンソンによって量子複雑性理論の分野に導入された影響力ある概念である(Royal Society A, 2005 の論文)。
我々の主な結果は、$sf PostBQL=$、すなわち、選択後(sf PostBQL$)で境界付きエラー(polynomial-time)対数空間量子アルゴリズムによって解決できる問題のクラスを示す。
また、$sf$は時間制限のない有界誤差対数空間量子アルゴリズムによって解くことができる問題のクラスと一致することを示す。
- 参考スコア(独自算出の注目度): 0.4588028371034406
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Post-selection, the power of discarding all runs of a computation in which an
undesirable event occurs, is an influential concept introduced to the field of
quantum complexity theory by Aaronson (Proceedings of the Royal Society A,
2005). In the present paper, we initiate the study of post-selection for
space-bounded quantum complexity classes. Our main result shows the identity
$\sf PostBQL=PL$, i.e., the class of problems that can be solved by a
bounded-error (polynomial-time) logarithmic-space quantum algorithm with
post-selection ($\sf PostBQL$) is equal to the class of problems that can be
solved by unbounded-error logarithmic-space classical algorithms ($\sf PL$).
This result gives a space-bounded version of the well-known result $\sf
PostBQP=PP$ proved by Aaronson for polynomial-time quantum computation. As a
by-product, we also show that $\sf PL$ coincides with the class of problems
that can be solved by bounded-error logarithmic-space quantum algorithms that
have no time bound.
- Abstract(参考訳): ポスト選択は、望ましくない事象が発生する計算の全ての実行を破棄する力であり、アーロンソンによって量子複雑性理論の分野に導入された影響力のある概念である(王立協会a, 2005)。
本稿では,空間境界量子複雑性クラスに対するポスト選択の研究を開始する。
我々の主な結果は、$\sf PostBQL=PL$、すなわち、ポスト選択(\sf PostBQL$)を持つ有界エラー(多項式時間)対数空間量子アルゴリズムによって解ける問題のクラスは、非有界エラー対数空間古典アルゴリズム(\sf PL$)によって解ける問題のクラスに等しいことを示す。
この結果は、多項式時間量子計算のためにアーロンソンによって証明されたよく知られた結果の空間有界版$\sf PostBQP=PP$を与える。
副産物として、$\sf PL$は時間境界のない有界誤差対数空間量子アルゴリズムによって解決できる問題のクラスと一致することも示している。
関連論文リスト
- The Power of Lorentz Quantum Computer [8.240558902431976]
本稿では,最近提案されたローレンツ量子コンピュータ(LQC)の,従来の量子コンピュータと比較して優れた性能を示す。
最大独立集合の問題とNP, co-NP, PH (polynomial hierarchy), PP (probabilistic-time), $text Psharp textP$ のクラスにおける問題を解くLQCアルゴリズムを提案する。
論文 参考訳(メタデータ) (2024-03-07T03:00:09Z) - On the quantum time complexity of divide and conquer [42.7410400783548]
量子分割の時間的複雑さと古典的問題に対するアルゴリズムの克服について検討する。
これらの定理を、弦、整数、幾何学的対象を含む一連の問題に適用する。
論文 参考訳(メタデータ) (2023-11-28T01:06:03Z) - Taming Quantum Time Complexity [50.10645865330582]
時間複雑性の設定において、正確さと遠心性の両方を達成する方法を示します。
我々は、トランスデューサと呼ばれるものに基づく量子アルゴリズムの設計に新しいアプローチを採用する。
論文 参考訳(メタデータ) (2023-11-27T14:45:19Z) - Dense outputs from quantum simulations [1.8076403084528587]
量子密度出力問題は、時間依存の量子力学から時間累積観測値を評価する過程である。
この問題は量子制御や分光計算などの応用で頻繁に発生する。
我々は、早期および完全フォールトトレラントな量子プラットフォームの両方で動作するように設計されたアルゴリズムを提示する。
論文 参考訳(メタデータ) (2023-07-26T18:16:51Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳(メタデータ) (2022-12-06T22:01:49Z) - Complexity-Theoretic Limitations on Quantum Algorithms for Topological
Data Analysis [59.545114016224254]
トポロジカルデータ解析のための量子アルゴリズムは、古典的手法よりも指数関数的に有利である。
我々は、量子コンピュータにおいても、TDA(ベッチ数の推定)の中心的なタスクが難解であることを示します。
我々は、入力データが単純さの仕様として与えられると、指数的量子優位性を取り戻すことができると論じる。
論文 参考訳(メタデータ) (2022-09-28T17:53:25Z) - A single $T$-gate makes distribution learning hard [56.045224655472865]
この研究は、局所量子回路の出力分布の学習可能性に関する広範な評価を提供する。
ハイブリッド量子古典アルゴリズムを含む多種多様な学習アルゴリズムにおいて、深度$d=omega(log(n))$ Clifford回路に関連する生成的モデリング問題さえも困難であることを示す。
論文 参考訳(メタデータ) (2022-07-07T08:04:15Z) - Limits of quantum speed-ups for computational geometry and other
problems: Fine-grained complexity via quantum walks [0.0]
いくつかの計算問題に対して、量子アルゴリズムの時間的複雑さを最適に下界として証明する。
我々の下界のほとんどは、既知の上界と一致しているため、量子スピードアップに厳しい制限が課せられるため、最適である。
論文 参考訳(メタデータ) (2021-06-03T17:22:08Z) - Reassessing the computational advantage of quantum-controlled ordering
of gates [0.0]
量子計算において、不確定因果構造は、2つのユニタリゲートが各ゲートへの1つの呼び出しで通勤するか反通勤するかを決定する。
本研究では,この利点が期待よりも小さいことを示す。
我々は、$O(nlog(n))$クエリで唯一知られている特定のFPPを解決する因果アルゴリズムと、$O(nsqrtn)$クエリですべてのFPPを解決する因果アルゴリズムを提案する。
論文 参考訳(メタデータ) (2021-02-22T19:00:08Z) - Quantum Gram-Schmidt Processes and Their Application to Efficient State
Read-out for Quantum Algorithms [87.04438831673063]
本稿では、生成した状態の古典的ベクトル形式を生成する効率的な読み出しプロトコルを提案する。
我々のプロトコルは、出力状態が入力行列の行空間にある場合に適合する。
我々の技術ツールの1つは、Gram-Schmidt正則手順を実行するための効率的な量子アルゴリズムである。
論文 参考訳(メタデータ) (2020-04-14T11:05:26Z) - Estimating the entropy of shallow circuit outputs is hard [77.34726150561087]
シャノンエントロピー推定の意思決定問題バージョンはエントロピー差分(ED)である
量子回路(QED)の類似の問題
オラクルと比較して、これらの問題は指数関数的に大きい回路と同等に難しいものではないことを示す。
論文 参考訳(メタデータ) (2020-02-27T15:32:08Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。