論文の概要: 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$は時間境界のない有界誤差対数空間量子アルゴリズムによって解決できる問題のクラスと一致することも示している。
関連論文リスト
- Halving the Cost of Quantum Algorithms with Randomization [0.138120109831448]
量子信号処理(QSP)は、線形演算子の変換を実装するための体系的なフレームワークを提供する。
近年の研究では、量子チャネルへのユニタリゲートを促進する技術であるランダム化コンパイルが開発されている。
提案アルゴリズムは, 平均進化が対象関数に収束するように戦略的に選択されたランダム化の確率的混合を実装し, 誤差は等価個体よりも2次的に小さい。
論文 参考訳（メタデータ） (2024-09-05T17:56:51Z) - Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている
SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。
この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
論文 参考訳（メタデータ） (2024-08-14T19:04:13Z) - Quantum and classical algorithms for nonlinear unitary dynamics [0.5729426778193399]
我々は$fracd|urangledtという形の非線形微分方程式に対する量子アルゴリズムを提案する。
また,Euler法に基づく古典的アルゴリズムを導入し,制限された場合の量子アルゴリズムへのコンパラブルなスケーリングを実現する。
論文 参考訳（メタデータ） (2024-07-10T14:08:58Z) - The Power of Lorentz Quantum Computer [6.9754404995027794]
本稿では,最近提案されたローレンツ量子コンピュータ(LQC)の,従来の量子コンピュータと比較して優れた性能を示す。
計算複雑性クラス$text Psharp textP$を導入し、複雑性クラス$text Psharp textP$と等価性を実証する。
Aaronsonが提案したポストセレクションによる量子コンピューティングはLQCで効率的にシミュレートできるが、その逆ではない。
論文 参考訳（メタデータ） (2024-03-07T03:00:09Z) - On the quantum time complexity of divide and conquer [42.7410400783548]
量子分割の時間的複雑さと古典的問題に対するアルゴリズムの克服について検討する。
これらの定理を、弦、整数、幾何学的対象を含む一連の問題に適用する。
論文 参考訳（メタデータ） (2023-11-28T01:06:03Z) - Dense outputs from quantum simulations [5.295277584890625]
量子密度出力問題は、時間依存の量子力学から時間累積観測値を評価する過程である。
この問題は量子制御や分光計算などの応用で頻繁に発生する。
我々は、早期および完全フォールトトレラントな量子プラットフォームの両方で動作するように設計されたアルゴリズムを提示する。
論文 参考訳（メタデータ） (2023-07-26T18:16:51Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳（メタデータ） (2022-12-06T22:01:49Z) - Quantum Depth in the Random Oracle Model [57.663890114335736]
浅量子回路の計算能力と古典計算の組合せを包括的に評価する。
いくつかの問題に対して、1つの浅い量子回路で適応的な測定を行う能力は、適応的な測定をせずに多くの浅い量子回路を実行する能力よりも有用である。
論文 参考訳（メタデータ） (2022-10-12T17:54:02Z) - 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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。