論文の概要: Oracle Separation between Noisy Quantum Polynomial Time and the Polynomial Hierarchy
- arxiv url: http://arxiv.org/abs/2405.07137v1
- Date: Sun, 12 May 2024 02:19:58 GMT
- ステータス: 処理完了
- システム内更新日: 2024-05-14 18:18:14.068769
- Title: Oracle Separation between Noisy Quantum Polynomial Time and the Polynomial Hierarchy
- Title(参考訳): ノイズ量子多項時間と多項階層のOracle分離
- Authors: Nai-Hui Chia, Min-Hsiu Hsieh, Shih-Han Hung, En-Jui Kuo,
- Abstract要約: 本研究では、雑音量子回路の物理的に動機付けられた複雑性クラス間のオラクル分離について検討する。
一定の誤差率で、分離はNPの観点で達成できると証明する。
特に、我々のオラクルは、全ての分離において、全ての量子回路が一定の深さであるため、エラー補正スキームやフォールトトレランスを必要としない。
- 参考スコア(独自算出の注目度): 9.839531457614031
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This work investigates the oracle separation between the physically motivated complexity class of noisy quantum circuits, inspired by definitions such as those presented by Chen, Cotler, Huang, and Li (2022). We establish that with a constant error rate, separation can be achieved in terms of NP. When the error rate is $\Omega(\log n/n)$, we can extend this result to the separation of PH. Notably, our oracles, in all separations, do not necessitate error correction schemes or fault tolerance, as all quantum circuits are of constant depth. This indicates that even quantum computers with minor errors, without error correction, may surpass classical complexity classes under various scenarios and assumptions. We also explore various common noise settings and present new classical hardness results, generalizing those found in studies by Raz and Tal (2022) and Bassirian, Bouland, Fefferman, Gunn, and Tal (2021), which are of independent interest.
- Abstract(参考訳): 本研究は、Chen, Cotler, Huang, Li (2022) などの定義に触発された、ノイズ量子回路の物理的に動機付けられた複雑性クラス間のオラクルの分離について研究する。
一定の誤差率で、分離はNPの観点で達成できると証明する。
誤差レートが$\Omega(\log n/n)$の場合、この結果をPHの分離にまで拡張することができる。
これは、誤りの少ない量子コンピュータでさえ、様々なシナリオや仮定の下で古典的な複雑性クラスを超える可能性があることを示している。
また,Raz と Tal (2022年) と Bassirian, Bouland, Fefferman, Gunn, Tal (2021年) の研究で見出された様々なノイズ設定や,新しい古典的硬度結果についても検討する。
関連論文リスト
- Quantum-Classical Separations in Shallow-Circuit-Based Learning with and without Noises [5.018448337319583]
定深さ(浅い)回路に基づく古典的学習モデルと量子教師あり学習モデルの量子古典的分離について検討する。
有界接続を持つ任意の古典的ニューラルネットワークは、指数的に小さい確率で正確に出力するために対数深度を必要とすることを厳密に証明する。
論文 参考訳(メタデータ) (2024-05-01T18:00:01Z) - Global Phase Helps in Quantum Search: Yet Another Look at the Welded Tree Problem [55.80819771134007]
本稿では、離散時間量子ウォークによる溶接木問題に対する最適線形打撃時間の簡単な証明を行う。
同じ手法は他の1次元階層グラフにも適用できる。
論文 参考訳(メタデータ) (2024-04-30T11:45:49Z) - Noise-induced shallow circuits and absence of barren plateaus [2.5295633594332334]
まず、雑音がほとんどの量子回路を効果的に対数深度に切り離すことを示す。
次に,非単位雑音下での量子回路は,局所可観測物からなるコスト関数に対するバレンプラトーの欠如を証明した。
また、逆多項式加法誤差内でのパウリ予想値を推定する古典的アルゴリズムを設計する。
論文 参考訳(メタデータ) (2024-03-20T19:00:49Z) - Taming Quantum Time Complexity [50.10645865330582]
時間複雑性の設定において、正確さと遠心性の両方を達成する方法を示します。
我々は、トランスデューサと呼ばれるものに基づく量子アルゴリズムの設計に新しいアプローチを採用する。
論文 参考訳(メタデータ) (2023-11-27T14:45:19Z) - Quantum algorithms: A survey of applications and end-to-end complexities [90.05272647148196]
期待されている量子コンピュータの応用は、科学と産業にまたがる。
本稿では,量子アルゴリズムの応用分野について検討する。
私たちは、各領域における課題と機会を"エンドツーエンド"な方法で概説します。
論文 参考訳(メタデータ) (2023-10-04T17:53:55Z) - Dense outputs from quantum simulations [5.295277584890625]
量子密度出力問題は、時間依存の量子力学から時間累積観測値を評価する過程である。
この問題は量子制御や分光計算などの応用で頻繁に発生する。
我々は、早期および完全フォールトトレラントな量子プラットフォームの両方で動作するように設計されたアルゴリズムを提示する。
論文 参考訳(メタデータ) (2023-07-26T18:16:51Z) - Krylov complexity and chaos in quantum mechanics [0.0]
演算子と状態に対するクリロフ複雑性を数値的に評価する。
ランツォス係数の分散と古典的なリャプノフ指数との明確な相関を見いだす。
私たちの仕事は、Krylov複雑性と古典的/量子的カオスの間にしっかりとした橋渡しを提供します。
論文 参考訳(メタデータ) (2023-05-26T06:32:45Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳(メタデータ) (2022-12-06T22:01:49Z) - Oracle separations of hybrid quantum-classical circuits [68.96380145211093]
量子計算の2つのモデル: CQ_dとQC_d。
CQ_dは、d-d-deepth量子コンピュータのシナリオを何度も捉え、QC_dは測定ベースの量子計算に類似している。
CQ_dとQC_dの類似性にもかかわらず、2つのモデルは本質的にはCQ_d $nsubseteq$QC_dとQC_d $nsubseteq$CQ_dである。
論文 参考訳(メタデータ) (2022-01-06T03:10:53Z) - Experimental violations of Leggett-Garg's inequalities on a quantum
computer [77.34726150561087]
単一および多ビット系におけるLeggett-Garg-Bellの不等式違反を実験的に観察する。
本分析では, 量子プラットフォームの限界に注目し, 上記の相関関数は, 量子ビットの数や回路深さが大きくなるにつれて, 理論的予測から逸脱することを示した。
論文 参考訳(メタデータ) (2021-09-06T14:35:15Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。