論文の概要: Towards a Linear-Ramp QAOA protocol: Evidence of a scaling advantage in solving some combinatorial optimization problems

• arxiv url: http://arxiv.org/abs/2405.09169v3
• Date: Mon, 04 Aug 2025 14:10:48 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-08-05 18:25:21.519886
• Title: Towards a Linear-Ramp QAOA protocol: Evidence of a scaling advantage in solving some combinatorial optimization problems
• Title（参考訳）: 線形ランプQAOAプロトコルに向けて:組合せ最適化問題の解法におけるスケーリング優位性の証明
• Authors: J. A. Montanez-Barrera, Kristel Michielsen,
• Abstract要約: 線形ランプQAOAは,様々な最適化問題にまたがる最適解を効率的に近似できることを示す。 最大$N_q = 109$ qubits,$p=100$,21,200 CNOTゲートを必要とする回路を有する複数のQPU上での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), with performance governed by variational parameters $\{\gamma_i, \beta_i\}_{i=0}^{p-1}$. While most prior work has focused on classically optimizing these parameters, we demonstrate that fixed linear ramp schedules, linear ramp QAOA (LR-QAOA), can efficiently approximate optimal solutions across diverse COPs. Simulations with up to $N_q=42$ qubits and $p=400$ layers suggest that the success probability scales as $P(x^*) \approx 2^{-\eta(p) N_q + C}$, where $\eta(p)$ decreases with increasing $p$. For example, in Weighted Maxcut instances, $\eta(10) = 0.22$ improves to $\eta(100) = 0.05$. Comparisons with classical algorithms, including simulated annealing, Tabu Search, and branch-and-bound, show a scaling advantage for LR-QAOA. We show results of LR-QAOA on multiple QPUs (IonQ, Quantinuum, IBM) with up to $N_q = 109$ qubits, $p=100$, and circuits requiring 21,200 CNOT gates. Finally, we present a noise model based on two-qubit gate counts that accurately reproduces the experimental behavior of LR-QAOA.
• Abstract（参考訳）: 量子近似最適化アルゴリズム(Quantum Approximate Optimization Algorithm, QAOA)は、組合せ最適化問題(COP)を解くための有望なアルゴリズムであり、性能は変動パラメータ$\{\gamma_i, \beta_i\}_{i=0}^{p-1}$で制御される。 従来の研究はこれらのパラメータを古典的に最適化することに重点を置いているが、線形ランプQAOA (LR-QAOA) は様々なCOPの最適解を効率的に近似できることを示した。 最大$N_q=42$ qubitsと$p=400$層を持つシミュレーションでは、成功確率は$P(x^*) \approx 2^{-\eta(p) N_q + C}$となり、$\eta(p)$は$p$の増加とともに減少する。 例えば、重み付きマックスカットの場合、$\eta(10) = 0.22$は$\eta(100) = 0.05$に改善される。 シミュレーションアニーリング、タブサーチ、ブランチ・アンド・バウンドといった古典的アルゴリズムとの比較は、LR-QAOAのスケーリング上の利点を示している。 最大$N_q = 109$ qubits,$p=100$,21,200 CNOTゲートを必要とする回路を持つ複数のQPU(IonQ, Quantinuum, IBM)上でLR-QAOAの結果を示す。 最後に、LR-QAOAの実験挙動を正確に再現する2ビットゲート数に基づくノイズモデルを提案する。

関連論文リスト

• Near-Optimal Parameter Tuning of Level-1 QAOA for Ising Models [3.390330377512402]
  2次元の$(gamma, beta)$サーチを$gamma$より1次元の検索に還元する方法を示し、$beta*$を解析的に計算する。 このアプローチはRecursive QAOA (RQAOA) を用いて検証され、粗い最適化RQAOAと半定値プログラムを一貫して上回る。
  論文  参考訳（メタデータ） (2025-01-27T19:00:00Z)
• An Adaptive Mixer Allocation Algorithm for the Quantum Alternating Operator Ansatz [2.7704630812545474]
  制約付き最適化問題の解法としてアダプティブミキサーアロケーションアルゴリズム(AMA)を提案する。 AMAはリソース消費を大幅に減らし、QAOA+の回路深度は34.08%$29.77%、CNOTゲートの数は15.05%$18.72%である。
  論文  参考訳（メタデータ） (2024-12-27T12:43:36Z)
• 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)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• 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)
• Convergence of Sparse Variational Inference in Gaussian Processes Regression [29.636483122130027]
  計算コストが$mathcalO(log N)2D(log N)2)$の手法を推論に利用できることを示す。
  論文  参考訳（メタデータ） (2020-08-01T19:23:34Z)
• 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)

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

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