論文の概要: 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年) の研究で見出された様々なノイズ設定や,新しい古典的硬度結果についても検討する。

関連論文リスト

• Dynamical simulations of many-body quantum chaos on a quantum computer [3.731709137507907]
  本稿では,二元一元回路として知られる最大カオス回路のクラスについて検討する。 91量子ビットの超伝導量子プロセッサは、これらの相関子を正確にシミュレートできることを示す。 次に、回路を二重ユニタリ点から遠ざけることによって、正確な検証以上のダイナミクスを探索する。
  論文  参考訳（メタデータ） (2024-11-01T17:57:13Z)
• Oracle Separations for the Quantum-Classical Polynomial Hierarchy [0.0]
  量子古典的階層 QCPH について検討する。これは、交互古典的量子化器の定数数で解ける言語のクラスである。 我々は、量子アルゴリズムに新しい切り換え補題を与えるが、これは独立した関心を持つかもしれない。
  論文  参考訳（メタデータ） (2024-10-24T18:12:03Z)
• 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)
• Taming Quantum Time Complexity [45.867051459785976]
  時間複雑性の設定において、正確さと遠心性の両方を達成する方法を示します。 我々は、トランスデューサと呼ばれるものに基づく量子アルゴリズムの設計に新しいアプローチを採用する。
  論文  参考訳（メタデータ） (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)
• Majorization-based benchmark of the complexity of quantum processors [105.54048699217668]
  我々は、様々な量子プロセッサの動作を数値的にシミュレートし、特徴付ける。 我々は,各デバイスの性能をベンチマークラインと比較することにより,量子複雑性を同定し,評価する。 我々は、回路の出力状態が平均して高い純度である限り、偏化ベースのベンチマークが成り立つことを発見した。
  論文  参考訳（メタデータ） (2023-04-10T23:01:10Z)
• 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)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。