論文の概要: 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を理想化された量子コンピュータ上で実行した場合のアルゴリズム成分としての有用性を示す。
関連論文リスト
- Solving various NP-Hard problems using exponentially fewer qubits on a
Quantum Computer [0.0]
NPハード問題は、一般時間アルゴリズムで正確に解けるとは考えられていない。
本稿では,問題のサイズに応じて対数的にスケールする独自手法を構築した。
これらのアルゴリズムは、100以上のノードのグラフサイズを持つ量子シミュレータと、256のグラフサイズまでの実際の量子コンピュータでテストされる。
論文 参考訳(メタデータ) (2023-01-17T16:03:33Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳(メタデータ) (2022-12-06T22:01:49Z) - 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) - Quantum approximate optimization algorithm for qudit systems [0.0]
量子近似最適化アルゴリズム(QAOA)について考察する。
本稿では、QAOAを用いて様々な整数最適化問題を定式化する方法を説明する。
最大$kのカラー化問題にマッピングした充電最適化問題の数値計算結果を示す。
論文 参考訳(メタデータ) (2022-04-01T10:37:57Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。