論文の概要: Towards a universal QAOA protocol: Evidence of quantum advantage in solving combinatorial optimization problems

• arxiv url: http://arxiv.org/abs/2405.09169v1
• Date: Wed, 15 May 2024 08:07:52 GMT
• ステータス: 処理完了
• システム内更新日: 2024-05-16 14:06:01.284505
• Title: Towards a universal QAOA protocol: Evidence of quantum advantage in solving combinatorial optimization problems
• Title（参考訳）: 普遍的QAOAプロトコルに向けて:組合せ最適化問題の解法における量子優位性の証明
• Authors: J. A. Montanez-Barrera, Kristel Michielsen,
• Abstract要約: 固定線形ランプスケジュールがQAOAパラメータの普遍的な集合であることを示す。 我々は、IonQ Aria、Quantinuum H2-1、IBM Brisbane、IBM Kyoto、IBM Osakaを用いて、実ハードウェア上でLR-QAOAをテストする。
• 参考スコア（独自算出の注目度）: 0.46040036610482665
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The quantum approximate optimization algorithm (QAOA) is a promising algorithm for solving combinatorial optimization problems (COPs). In this algorithm, there are alternating layers consisting of a mixer and a problem Hamiltonian. Each layer $i=0,\ldots,p-1$ is parameterized by $\beta_i$ and $\gamma_i$. How to find these parameters has been an open question with the majority of the research focused on finding them using classical algorithms. In this work, we present evidence that fixed linear ramp schedules constitute a universal set of QAOA parameters, i.e., a set of $\gamma$ and $\beta$ parameters that rapidly approximate the optimal solution, $x^*$, independently of the COP selected, and that the success probability of finding it, $probability(x^*)$, increases with the number of QAOA layers $p$. We simulate linear ramp QAOA protocols (LR-QAOA) involving up to $N_q=42$ qubits and $p = 400$ layers on random instances of 9 different COPs. The results suggest that $probability(x^*) \approx 1/2^{(\eta N_q / p)}$ for a constant $\eta$. For example, when implementing LR-QAOA with $p=42$, the $probability(x^*)$ for 42-qubit Weighted MaxCut problems (W-MaxCut) increases from $2/2^{42}\approx 10^{-13}$ to an average of 0.13. We compare LR-QAOA, simulated annealing (SA), and branch-and-bound (B\&B) finding a fundamental improvement in LR-QAOA. We test LR-QAOA on real hardware using IonQ Aria, Quantinuum H2-1, IBM Brisbane, IBM Kyoto, and IBM Osaka, encoding random weighted MaxCut (W-MaxCut) problems from 5 to 109 qubits and $p=3$ to $100$. Even for the largest case, $N_q=109$ qubits and $p=100$, information about the LR-QAOA optimization protocol is present. The circuit involved requires 21200 CNOT gates. These results show that LR-QAOA effectively finds high-quality solutions for COPs and suggests an advantage of quantum computation for combinatorial optimization in the near future.
• Abstract（参考訳）: 量子近似最適化アルゴリズム(QAOA)は組合せ最適化問題を解くための有望なアルゴリズムである。 このアルゴリズムでは、ミキサーとハミルトニアンの問題からなる交互層が存在する。 各層$i=0,\ldots,p-1$は$\beta_i$と$\gamma_i$でパラメータ化される。 これらのパラメータをどうやって見つけるかはオープンな問題であり、研究の大半は古典的なアルゴリズムを使ってそれらを見つけることに重点を置いている。 本研究では、固定線形ランプスケジュールがQAOAパラメータの普遍的な集合、すなわち最適解を高速に近似する$\gamma$と$\beta$パラメータの集合であるCOPとは独立に$x^*$であり、それを見つける成功確率である$probability(x^*)$はQAOA層数$p$で増加することを示す。 最大$N_q=42$ qubits と $p = 400$ 層を含むリニアランプQAOAプロトコル(LR-QAOA)を9種類のCOPのランダムなインスタンス上でシミュレートする。 この結果は、定数$\eta$に対して$probability(x^*) \approx 1/2^{(\eta N_q / p)}$であることが示唆されている。 例えば、LR-QAOAを$p=42$で実装する場合、42量子重み付きMaxCut問題(W-MaxCut)に対する$probability(x^*)$は2/2^{42}\approx 10^{-13}$から平均0.13まで増加する。 LR-QAOA, 模擬アニール (SA), 分岐結合 (B\&B) を比較し, LR-QAOAの根本的な改善について検討した。 LR-QAOAをIonQ Aria, Quantinuum H2-1, IBM Brisbane, IBM Kyoto, IBM Osakaを用いて実ハードウェア上でテストし, ランダム重み付きMaxCut(W-MaxCut)問題を5～109キュービット,$p=3$から100$で符号化した。 最大の場合であっても、$N_q=109$ qubitsと$p=100$は、LR-QAOA最適化プロトコルに関する情報である。 回路は21200個のCNOTゲートを必要とする。 これらの結果は、LR-QAOAがCOPの高品質な解を効果的に見つけることを示し、近い将来に組合せ最適化のための量子計算の利点を示唆している。

関連論文リスト

• A Multilevel Approach For Solving Large-Scale QUBO Problems With Noisy Hybrid Quantum Approximate Optimization [3.3493770627144004]
  既存の量子処理ユニット(QPU)がマルチレベル戦略においてサブソルバとしてどのように機能するかを実験的に検証する。 完全連結な 82$-qubit Sherrington-Kirkpatrick グラフに対して 10$ の近似解を求める。 量子最適化の結果は古典学と比較して解の質に関して競争力がある。
  論文  参考訳（メタデータ） (2024-08-14T20:06:32Z)
• Transfer learning of optimal QAOA parameters in combinatorial optimization [0.46040036610482665]
  本研究では,ある問題インスタンスの事前学習されたQAOAパラメータを異なるCOPインスタンスに再利用するために,転送学習(TL)手法について検討する。 本研究では、旅行セールスマン問題(TSP)、ビン包装問題(BPP)、クナップサック問題(KP)、最大カット問題(MaxCut)、ポートフォリオ最適化問題(PO)の小さな事例を選択する。 我々は,BPP のパラメータを持つ D-Wave Advantage 量子アニールを用いて,クロスプラットフォーム TL が可能であることを示す。
  論文  参考訳（メタデータ） (2024-02-08T10:35:23Z)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。 我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
  論文  参考訳（メタデータ） (2024-01-17T18:59:38Z)
• An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue Optimization Problems [76.2042837251496]
  相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。 注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。 本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
  論文  参考訳（メタデータ） (2023-06-30T08:34:29Z)
• Near-Optimal Non-Convex Stochastic Optimization under Generalized Smoothness [21.865728815935665]
  2つの最近の研究は、$O(epsilon-3)$サンプル複雑性を確立し、$O(epsilon)$-定常点を得る。 しかし、どちらも$mathrmploy(epsilon-1)$という大きなバッチサイズを必要とする。 本研究では,STORMアルゴリズムの単純な変種を再検討することにより,従来の2つの問題を同時に解決する。
  論文  参考訳（メタデータ） (2023-02-13T00:22:28Z)
• Mind the gap: Achieving a super-Grover quantum speedup by jumping to the end [114.3957763744719]
  本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。 このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。 また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
  論文  参考訳（メタデータ） (2022-12-03T02:45:23Z)
• 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)
• Practical and Parallelizable Algorithms for Non-Monotone Submodular Maximization with Size Constraint [20.104148319012854]
  サイズ制約に関して、必ずしも単調ではない部分モジュラ函数に対して存在および並列化可能である。 最適な適応性とほぼ最適な複雑性クエリを持つアルゴリズムによって達成される最適な近似係数を、0.193 - varepsilon$に改善する。
  論文  参考訳（メタデータ） (2020-09-03T22:43:55Z)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)
• FANOK: Knockoffs in Linear Time [73.5154025911318]
  本稿では,ガウスモデル-Xノックオフを効率的に実装し,大規模特徴選択問題における誤発見率を制御するアルゴリズムについて述べる。 当社のメソッドは、最大50,000ドルという問題でテストしています。
  論文  参考訳（メタデータ） (2020-06-15T21:55:34Z)

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

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