論文の概要: Evidence of Scaling Advantage for the Quantum Approximate Optimization Algorithm on a Classically Intractable Problem
- arxiv url: http://arxiv.org/abs/2308.02342v2
- Date: Sun, 2 Jun 2024 13:49:44 GMT
- ステータス: 処理完了
- システム内更新日: 2024-06-04 21:10:26.439838
- Title: Evidence of Scaling Advantage for the Quantum Approximate Optimization Algorithm on a Classically Intractable Problem
- Title（参考訳）: 古典的難解問題に対する量子近似最適化アルゴリズムのスケーリング手法の証明
- Authors: Ruslan Shaydulin, Changhao Li, Shouvanik Chakrabarti, Matthew DeCross, Dylan Herman, Niraj Kumar, Jeffrey Larson, Danylo Lykov, Pierre Minssen, Yue Sun, Yuri Alexeev, Joan M. Dreiling, John P. Gaebler, Thomas M. Gatterman, Justin A. Gerber, Kevin Gilmore, Dan Gresh, Nathan Hewitt, Chandler V. Horst, Shaohan Hu, Jacob Johansen, Mitchell Matheny, Tanner Mengle, Michael Mills, Steven A. Moses, Brian Neyenhuis, Peter Siegfried, Romina Yalovetzky, Marco Pistoia,
- Abstract要約: 量子近似最適化アルゴリズム(QAOA)は、量子コンピュータにおける最適化問題を解くための主要な候補アルゴリズムである。
本稿では,低自己相関二項列(LABS)問題に対するQAOAの広範な数値的な検討を行う。
パラメータが固定されたQAOAのランタイムは、分岐とバウンドの解法よりも良くスケールする。
- 参考スコア（独自算出の注目度）: 8.738180371389097
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The quantum approximate optimization algorithm (QAOA) is a leading candidate algorithm for solving optimization problems on quantum computers. However, the potential of QAOA to tackle classically intractable problems remains unclear. Here, we perform an extensive numerical investigation of QAOA on the low autocorrelation binary sequences (LABS) problem, which is classically intractable even for moderately sized instances. We perform noiseless simulations with up to 40 qubits and observe that the runtime of QAOA with fixed parameters scales better than branch-and-bound solvers, which are the state-of-the-art exact solvers for LABS. The combination of QAOA with quantum minimum finding gives the best empirical scaling of any algorithm for the LABS problem. We demonstrate experimental progress in executing QAOA for the LABS problem using an algorithm-specific error detection scheme on Quantinuum trapped-ion processors. Our results provide evidence for the utility of QAOA as an algorithmic component that enables quantum speedups.
- Abstract（参考訳）: 量子近似最適化アルゴリズム(QAOA)は、量子コンピュータにおける最適化問題を解くための主要な候補アルゴリズムである。
しかし、古典的に難解な問題に取り組むQAOAの可能性は、まだ不明である。
本稿では,低自己相関バイナリシーケンス(LABS)問題に対するQAOAの広範な数値的な検討を行う。
最大40キュービットのノイズレスシミュレーションを行い、パラメータが固定されたQAOAのランタイムは、LABSの最先端の正確な解法であるブランチ・アンド・バウンド・ソルバよりも良くスケールすることを示した。
QAOAと量子最小探索の組み合わせは、LABS問題に対する任意のアルゴリズムの最良の経験的スケーリングを与える。
我々は,量子トラップイオンプロセッサ上でのアルゴリズム固有の誤り検出手法を用いて,LABS問題に対するQAOAの実行実験を行った。
本結果は,量子スピードアップを実現するアルゴリズムコンポーネントとしてのQAOAの有用性を示すものである。
関連論文リスト
- Hybrid Classical-Quantum Simulation of MaxCut using QAOA-in-QAOA [0.0]
そこで本研究では,MaxCut問題のスケーラブルな解に対するQAOA2法の実装について述べる。
The limit of the Goemans-Williamson (GW) algorithm as a purely classical alternative to QAOA。
最大33量子ビットの大規模シミュレーションの結果は、ある場合におけるQAOAの利点と実装の効率性を示す。
論文 参考訳（メタデータ） (2024-06-25T09:02:31Z) - Multiscale Quantum Approximate Optimization Algorithm [0.0]
量子近似最適化アルゴリズム(QAOA)は、最適化問題の近似解を見つけるために設計された標準アルゴリズムの1つである。
本稿では,QAOAの能力と実空間再正規化群変換を取り入れたQAOAの新バージョンを提案する。
論文 参考訳（メタデータ） (2023-12-11T07:47:16Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳（メタデータ） (2022-12-06T22:01:49Z) - How Much Entanglement Do Quantum Optimization Algorithms Require? [0.0]
ADAPT-QAOA施行時に発生する絡みについて検討した。
この柔軟性を漸進的に制限することにより、初期におけるより多くの絡み合いエントロピーが、後段におけるより速い収束と一致していることが分かる。
論文 参考訳（メタデータ） (2022-05-24T18:00:02Z) - QAOA-in-QAOA: solving large-scale MaxCut problems on small quantum
machines [81.4597482536073]
量子近似最適化アルゴリズム(QAOAs)は、量子マシンのパワーを利用し、断熱進化の精神を継承する。
量子マシンを用いて任意の大規模MaxCut問題を解くためにQAOA-in-QAOA(textQAOA2$)を提案する。
提案手法は,大規模最適化問題におけるQAOAsの能力を高めるために,他の高度な戦略にシームレスに組み込むことができる。
論文 参考訳（メタデータ） (2022-05-24T03:49:10Z) - 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) - Efficient Classical Computation of Quantum Mean Values for Shallow QAOA
Circuits [15.279642278652654]
浅いQAOA回路の量子ビット数と線形にスケールするグラフ分解に基づく古典的アルゴリズムを提案する。
我々の結果は、QAOAによる量子アドバンテージの探索だけでなく、NISQプロセッサのベンチマークにも有用である。
論文 参考訳（メタデータ） (2021-12-21T12:41:31Z) - Quantum Approximate Optimization Algorithm Based Maximum Likelihood
Detection [80.28858481461418]
量子技術の最近の進歩は、ノイズの多い中間スケール量子(NISQ)デバイスへの道を開く。
量子技術の最近の進歩は、ノイズの多い中間スケール量子(NISQ)デバイスへの道を開く。
論文 参考訳（メタデータ） (2021-07-11T10:56:24Z) - Quantum constraint learning for quantum approximate optimization
algorithm [0.0]
本稿では,探索部分空間を厳しく制約するミキサーハミルトンを学習するための量子機械学習手法を提案する。
学習したユニタリを直接適応可能なアンサッツを使用してQAOAフレームワークにプラグインすることができる。
また,Wasserstein距離を用いた近似最適化アルゴリズムの性能を,制約なしで評価する直感的計量法を開発した。
論文 参考訳（メタデータ） (2021-05-14T11:31:14Z) - Space-efficient binary optimization for variational computing [68.8204255655161]
本研究では,トラベリングセールスマン問題に必要なキュービット数を大幅に削減できることを示す。
また、量子ビット効率と回路深さ効率のモデルを円滑に補間する符号化方式を提案する。
論文 参考訳（メタデータ） (2020-09-15T18:17:27Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。