論文の概要: Threshold for Fault-tolerant Quantum Advantage with the Quantum Approximate Optimization Algorithm

• arxiv url: http://arxiv.org/abs/2504.01897v1
• Date: Wed, 02 Apr 2025 16:57:28 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-04-03 13:20:42.484564
• Title: Threshold for Fault-tolerant Quantum Advantage with the Quantum Approximate Optimization Algorithm
• Title（参考訳）: 量子近似最適化アルゴリズムによるフォールトトレラント量子アドバンテージの閾値
• Authors: Sivaprasad Omanakuttan, Zichang He, Zhiwei Zhang, Tianyi Hao, Arman Babakhani, Sami Boulebnane, Shouvanik Chakrabarti, Dylan Herman, Joseph Sullivan, Michael A. Perlin, Ruslan Shaydulin, Marco Pistoia,
• Abstract要約: 現実的な仮定の下では、量子コンピュータが古典的な最適化問題に勝ることはありそうにない。 さらに, 物理誤差率と耐故障性オーバーヘッドの低減が期待できるため, 古典的解法エネルギー消費に対するこの制限は緩和可能であることを示す。 これらの結果は、大規模フォールトトレラント量子コンピュータが最適化に有用であるという仮説を支持している。
• 参考スコア（独自算出の注目度）: 6.328164687610608
• License:
• Abstract: Optimization is often cited as a promising application of quantum computers. However, the low degree of provable quantum speedups has led prior rigorous end-to-end resource analyses to conclude that a quantum computer is unlikely to surpass classical state-of-the-art on optimization problems under realistic assumptions. In this work, we compile and analyze the Quantum Approximate Optimization Algorithm (QAOA) combined with Amplitude Amplification (AA) applied to random 8-SAT at the satisfiability threshold. Our compilation involves careful optimization of circuits for Hamiltonian simulation, which may be of independent interest. We use the analytical scaling of the time-to-solution for QAOA identified by PRX Quantum 5, 030348 (2024) and find that with QAOA depth $p=623$, QAOA+AA achieves a crossover with state-of-the-art classical heuristics at 179 variables and 14.99 hours of runtime when executed on a surface-code-based fault-tolerant quantum computer with 73.91 million physical qubits, a physical error rate of $10^{-3}$, and a $1~\mu$s code cycle time. Notably, we allow the classical solver to be parallelized as long as its total energy consumption is equal to that required for decoding in the surface code. We further show that this restriction on classical solver energy consumption can be relaxed given optimistic but plausible reductions in physical error rates and fault-tolerance overheads, enabling a crossover of 2.94 hours using 8.88 million physical qubits against a classical solver running on a supercomputer with $725,760$ CPU cores. These findings support the hypothesis that large-scale fault-tolerant quantum computers will be useful for optimization.
• Abstract（参考訳）: 最適化はしばしば量子コンピュータの有望な応用として言及される。 しかし、証明可能な量子スピードアップの低い程度は、厳密なエンド・ツー・エンドのリソース分析を先導し、現実的な仮定の下での最適化問題の古典的状態を超えることはありそうにないと結論づけている。 本研究では,量子近似最適化アルゴリズム (QAOA) とAmplitude Amplification (AA) を組み合わせて,確率8-SATを満足度閾値でコンパイルし,解析する。 我々のコンパイルでは、ハミルトンシミュレーションのための回路を慎重に最適化するが、これは独立した関心事であるかもしれない。 PRX Quantum 5, 030348 (2024) で同定されたQAOAの時間-解のスケーリングを用いて、QAOAの深さ$p=623$, QAOA+AAは、179変数の最先端の古典的ヒューリスティックスと14.99時間の実行時を、表面コードベースのフォールトトレラント量子コンピュータ上で実行した場合に、73.91万の物理量子ビット、物理エラーレート 10^{-3}$、および1–1\mu$sのコードサイクル時間で達成する。 特に、従来の解法は、その全エネルギー消費が表面符号の復号化に必要なものと等しい限り並列化できる。 さらに,CPUコア725,760ドルのスーパーコンピュータ上で動作している古典的ソルバに対して,888万の物理量子ビットを用いた2.94時間のクロスオーバーを可能にすることにより,この古典的ソルバエネルギー消費制限を緩和できることを示した。 これらの結果は、大規模フォールトトレラント量子コンピュータが最適化に有用であるという仮説を支持している。

関連論文リスト

• Benchmarking Quantum Optimization for the Maximum-Cut Problem on a Superconducting Quantum Computer [0.3518016233072556]
  超伝導量子コンピュータは、ハイブリッド量子古典アルゴリズムの性能を調べるために用いられる。 同様に高い性能の古典に対して量子解法をベンチマークする。 実行時解析により、大規模問題における量子解法は、グロビと競合するが、100量子ビットの量子コンピュータでは他より小さいことが示されている。
  論文  参考訳（メタデータ） (2024-04-26T17:59:22Z)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。 我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
  論文  参考訳（メタデータ） (2024-01-17T18:59:38Z)
• Simulation of IBM's kicked Ising experiment with Projected Entangled Pair Operator [71.10376783074766]
  我々は最近,誤りを軽減した量子回路を用いてエミュレートされた127量子ビットキックド・イジングモデルの古典的シミュレーションを行った。 提案手法はハイゼンベルク図の射影的絡み合ったペア作用素(PEPO)に基づいている。 我々はクリフォード展開理論を開発し、正確な期待値を計算し、それらをアルゴリズムの評価に利用する。
  論文  参考訳（メタデータ） (2023-08-06T10:24:23Z)
• Optimizing quantum gates towards the scale of logical qubits [78.55133994211627]
  量子ゲート理論の基本的な前提は、量子ゲートはフォールトトレランスの誤差閾値を超えることなく、大きなプロセッサにスケールできるということである。 ここでは、このような問題を克服できる戦略について報告する。 我々は、68個の周波数可変ビットの周波数軌跡をコレオグラフィーして、超伝導エラー中に単一量子ビットを実行することを示した。
  論文  参考訳（メタデータ） (2023-08-04T13:39:46Z)
• Enhancing Quantum Algorithms for Quadratic Unconstrained Binary Optimization via Integer Programming [0.0]
  本研究では,最適化のための量子および古典的手法の可能性を統合する。 線形緩和により問題のサイズを小さくし、最小サイズの量子マシンで問題を処理できるようにした。 実量子ハードウェアの計算結果を多数提示する。
  論文  参考訳（メタデータ） (2023-02-10T20:12:53Z)
• Calibrating the Classical Hardness of the Quantum Approximate Optimization Algorithm [0.0]
  スケールのためのトレーディング忠実さは、近似古典的シミュレーターが正確な方法を超える量子回路を走らせることを可能にする。 最小化を目指すコスト関数の期待値を用いて、量子近似最適化アルゴリズムの忠実度を特徴付ける。 現実的な設定で量子ハードウェアの性能をベンチマークする。
  論文  参考訳（メタデータ） (2022-06-13T17:45:59Z)
• Sampling Frequency Thresholds for Quantum Advantage of Quantum Approximate Optimization Algorithm [0.7046417074932257]
  量子近似最適化アルゴリズム(QAOA)の性能を最先端の古典解法と比較する。 古典的解法は線形時間複雑性において高品質な近似解を生成することができる。 異なるグラフ、重み付けされたMaxCut、最大独立集合、および3-SATといった他の問題は、短期量子デバイスにおける量子優位性を達成するのに適しているかもしれない。
  論文  参考訳（メタデータ） (2022-06-07T20:59:19Z)
• The QAOA with Few Measurements [4.713817702376467]
  近似量子最適化アルゴリズム (QAOA) はもともと最適化問題の解法として開発された。 完全な記述型ベンチマーク技術は、多くの量子ビットに対してしばしば高価である。 中性原子量子コンピュータのような実験的な量子コンピューティングプラットフォームは、繰り返し速度が遅い。
  論文  参考訳（メタデータ） (2022-05-13T18:42:20Z)
• Adiabatic Quantum Computing for Multi Object Tracking [170.8716555363907]
  マルチオブジェクト追跡(MOT)は、オブジェクト検出が時間を通して関連付けられているトラッキング・バイ・検出のパラダイムにおいて、最もよくアプローチされる。 これらの最適化問題はNPハードであるため、現在のハードウェア上の小さなインスタンスに対してのみ正確に解決できる。 本手法は,既成整数計画法を用いても,最先端の最適化手法と競合することを示す。
  論文  参考訳（メタデータ） (2022-02-17T18:59:20Z)
• Scaling Quantum Approximate Optimization on Near-term Hardware [49.94954584453379]
  我々は、様々なレベルの接続性を持つハードウェアアーキテクチャのための最適化回路により、期待されるリソース要求のスケーリングを定量化する。 問題の大きさと問題グラフの次数で指数関数的に増大する。 これらの問題は、ハードウェア接続性の向上や、より少ない回路層で高い性能を達成するQAOAの変更によって緩和される可能性がある。
  論文  参考訳（メタデータ） (2022-01-06T21:02:30Z)
• Space-efficient binary optimization for variational computing [68.8204255655161]
  本研究では,トラベリングセールスマン問題に必要なキュービット数を大幅に削減できることを示す。 また、量子ビット効率と回路深さ効率のモデルを円滑に補間する符号化方式を提案する。
  論文  参考訳（メタデータ） (2020-09-15T18:17:27Z)

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

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