論文の概要: Evidence of Scaling Advantage for the Quantum Approximate Optimization
Algorithm on a Classically Intractable Problem
- arxiv url: http://arxiv.org/abs/2308.02342v1
- Date: Fri, 4 Aug 2023 14:17:21 GMT
- ステータス: 処理完了
- システム内更新日: 2023-08-07 12:42:08.367209
- 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)は、量子コンピュータにおける最適化問題を解くための主要な候補アルゴリズムである。
本稿では,Low Autocorrelation Binary Sequences (LABS) 問題に対するQAOAの広範な数値解析を行う。
このシステムサイズ、固定パラメータと一定の数のレイヤを持つQAOAのランタイムは、ブランチ・アンド・バウンド・ソルバよりも優れたスケールである。
- 参考スコア（独自算出の注目度）: 16.821121709738957
- 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.
In this paper, we perform an extensive numerical investigation of QAOA on the
Low Autocorrelation Binary Sequences (LABS) problem. The rapid growth of the
problem's complexity with the number of spins $N$ makes it classically
intractable even for moderately sized instances, with the best-known heuristics
observed to fail to find a good solution for problems with $N \gtrapprox 200$.
We perform noiseless simulations with up to 40 qubits and observe that out to
this system size, the runtime of QAOA with fixed parameters and a constant
number of layers 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 on an idealized quantum computer gives the best empirical
scaling of any algorithm for the LABS problem. We demonstrate experimental
progress in compiling and 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 when executed on an idealized quantum computer.
- Abstract（参考訳）: 量子近似最適化アルゴリズム(QAOA)は、量子コンピュータにおける最適化問題を解くための主要な候補アルゴリズムである。
しかし、古典的に難解な問題に取り組むQAOAの可能性は、まだ不明である。
本稿では,Low Autocorrelation Binary Sequences (LABS) 問題に対するQAOAの広範な数値解析を行う。
n$のスピン数による問題の複雑さの急速な増大は、中程度の大きさのインスタンスでも古典的に難解であり、最もよく知られたヒューリスティックスは、$n \gtr 約200$の問題のよい解を見つけられなかった。
我々は最大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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。