論文の概要: Improved separation between quantum and classical computers for sampling and functional tasks

• arxiv url: http://arxiv.org/abs/2410.20935v1
• Date: Mon, 28 Oct 2024 11:30:10 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-10-29 12:21:07.912519
• Title: Improved separation between quantum and classical computers for sampling and functional tasks
• Title（参考訳）: サンプリングおよび機能タスクのための量子コンピュータと古典コンピュータの分離の改善
• Authors: Simon C. Marshall, Scott Aaronson, Vedran Dunjko,
• Abstract要約: 本稿では、量子コンピュータが古典的コンピュータを超えた計算が可能であるという既存の証拠をさらに強調する。 i)ポストセレクションを持つ量子コンピュータは、ポストセレクションを持つ古典的コンピュータと同じくらい強力である。 正確な数え上げオラクルで解ける問題と近似数え上げオラクルで解ける問題の間に同値性が存在すると証明すると、階層構造はその第2レベルに崩壊する。
• 参考スコア（独自算出の注目度）: 3.618534280726541
• License:
• Abstract: This paper furthers existing evidence that quantum computers are capable of computations beyond classical computers. Specifically, we strengthen the collapse of the polynomial hierarchy to the second level if: (i) Quantum computers with postselection are as powerful as classical computers with postselection ($\mathsf{PostBQP=PostBPP}$), (ii) any one of several quantum sampling experiments ($\mathsf{BosonSampling}$, $\mathsf{IQP}$, $\mathsf{DQC1}$) can be approximately performed by a classical computer (contingent on existing assumptions). This last result implies that if any of these experiment's hardness conjectures hold, then quantum computers can implement functions classical computers cannot ($\mathsf{FBQP\neq FBPP}$) unless the polynomial hierarchy collapses to its 2nd level. These results are an improvement over previous work which either achieved a collapse to the third level or were concerned with exact sampling, a physically impractical case. The workhorse of these results is a new technical complexity-theoretic result which we believe could have value beyond quantum computation. In particular, we prove that if there exists an equivalence between problems solvable with an exact counting oracle and problems solvable with an approximate counting oracle, then the polynomial hierarchy collapses to its second level, indeed to $\mathsf{ZPP^{NP}}$.
• Abstract（参考訳）: 本稿では、量子コンピュータが古典的コンピュータを超えた計算が可能であるという既存の証拠をさらに強調する。 具体的には、多項式階層の崩壊を次のレベルに拡張する。 (i)ポストセレクションを持つ量子コンピュータは、ポストセレクションを持つ古典的コンピュータと同じくらい強力である(\mathsf{PostBQP=PostBPP}$) (ii)いくつかの量子サンプリング実験 (\mathsf{BosonSampling}$, $\mathsf{IQP}$, $\mathsf{DQC1}$) のうちの1つは、古典的なコンピュータで概ね実行することができる。 この最後の結果は、これらの実験の硬さ予想のいずれかが成り立つならば、多項式階層が第2レベルに崩壊しない限り、量子コンピュータは古典的コンピュータでは不可能な関数("\mathsf{FBQP\neq FBPP}$")を実装できることを意味している。 これらの結果は,第3段階の崩壊を達成した,あるいは正確なサンプリングに関心を持った以前の作業よりも改善された。 これらの結果の成果は、量子計算以上の価値を持つ可能性がある、新しい技術的複雑性理論的な結果である。 特に、正確な数え上げオラクルで解ける問題と近似数え上げオラクルで解ける問題の間に同値性が存在すると証明すると、多項式階層はその第2レベル(実際は$\mathsf{ZPP^{NP}}$)に崩壊する。

関連論文リスト

• Quantum Circuit Learning on NISQ Hardware [0.0]
  現在の量子コンピュータは小さく、エラーを起こしやすいシステムである。 フォールトトレラントな量子コンピュータは近い将来は利用できない。 我々は,IBM量子コンピュータ上で最大3キュービットのQCL回路が実行可能であることを示す。
  論文  参考訳（メタデータ） (2024-05-03T13:00:32Z)
• The hardness of quantum spin dynamics [1.1999555634662633]
  量子スピンハミルトニアンの幅広いクラスが生成する出力分布からのサンプリングは、古典コンピュータにとって難しい問題であることを示す。 約200スピンのインスタンスは、古典的なデバイスでは難しいが、フォールトトレラント量子ビットを持つ中間スケールの量子コンピュータでは実現可能であると推定する。
  論文  参考訳（メタデータ） (2023-12-12T19:00:03Z)
• Quantum Depth in the Random Oracle Model [57.663890114335736]
  浅量子回路の計算能力と古典計算の組合せを包括的に評価する。 いくつかの問題に対して、1つの浅い量子回路で適応的な測定を行う能力は、適応的な測定をせずに多くの浅い量子回路を実行する能力よりも有用である。
  論文  参考訳（メタデータ） (2022-10-12T17:54:02Z)
• BQP is not in NP [0.0]
  量子計算は、古典的なコンピュータの能力を超える問題を効率的に解くことができることを示す。 このことは、量子計算が古典的なコンピュータの能力を超える問題を効率的に解くことができることを証明している。
  論文  参考訳（メタデータ） (2022-09-19T23:17:57Z)
• 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)
• Realization of arbitrary doubly-controlled quantum phase gates [62.997667081978825]
  本稿では,最適化問題における短期量子優位性の提案に着想を得た高忠実度ゲートセットを提案する。 3つのトランペット四重項のコヒーレントな多レベル制御を編成することにより、自然な3量子ビット計算ベースで作用する決定論的連続角量子位相ゲートの族を合成する。
  論文  参考訳（メタデータ） (2021-08-03T17:49:09Z)
• Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
  3次元形状と画像のマッチング問題は、NPハードな置換行列制約を持つ二次代入問題(QAP)としてしばしば定式化される。 本稿では,量子ハードウェア上での効率的な実行に適した制約のない問題として,いくつかのQAPの再構成を提案する。 提案アルゴリズムは、将来の量子コンピューティングアーキテクチャにおいて、より高次元にスケールする可能性がある。
  論文  参考訳（メタデータ） (2021-07-08T17:59:55Z)
• Depth-efficient proofs of quantumness [77.34726150561087]
  量子性の証明は、古典的検証器が信頼できない証明器の量子的利点を効率的に証明できる挑戦応答プロトコルの一種である。 本稿では、証明者が量子回路を一定深度でしか実行できない量子性構成の証明を2つ与える。
  論文  参考訳（メタデータ） (2021-07-05T17:45:41Z)
• Resource-Efficient Quantum Computing by Breaking Abstractions [9.695745674863554]
  現在の量子ソフトウェアスタックは、古典的なコンピュータのスタックに似た階層化されたアプローチに従っている。 本稿では,これらの層間の抽象化を分解することで,量子コンピューティングシステムの高効率性を実現することができることを指摘する。
  論文  参考訳（メタデータ） (2020-10-30T18:18:23Z)
• An Application of Quantum Annealing Computing to Seismic Inversion [55.41644538483948]
  小型地震インバージョン問題を解決するために,D波量子アニールに量子アルゴリズムを適用した。 量子コンピュータによって達成される精度は、少なくとも古典的コンピュータと同程度である。
  論文  参考訳（メタデータ） (2020-05-06T14:18:44Z)

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

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