論文の概要: Quantum Approximate Optimization of Integer Graph Problems and Surpassing Semidefinite Programming for Max-k-Cut
- arxiv url: http://arxiv.org/abs/2602.05956v1
- Date: Thu, 05 Feb 2026 18:11:18 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-02-06 18:49:09.107394
- Title: Quantum Approximate Optimization of Integer Graph Problems and Surpassing Semidefinite Programming for Max-k-Cut
- Title（参考訳）: 整数グラフ問題の量子近似最適化とMax-k-Cutの半有限計画法
- Authors: Anuj Apte, Sami Boulebnane, Yuwei Jin, Sivaprasad Omanakuttan, Michael A. Perlin, Ruslan Shaydulin,
- Abstract要約: グラフ上の整数問題に適用された量子近似最適化アルゴリズム(QAOA)について検討する。
任意の大きさの高次$d$正則グラフ上で、深さ-p$QAOA予想に対する一般的な反復公式を導出する。
その結果、二進法から整数最適化問題への移動は、量子的優位性のために新しい道を開くことができることを示した。
- 参考スコア（独自算出の注目度）: 0.8084252698425037
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Quantum algorithms for binary optimization problems have been the subject of extensive study. However, the application of quantum algorithms to integer optimization problems remains comparatively unexplored. In this paper, we study the Quantum Approximate Optimization Algorithm (QAOA) applied to integer problems on graphs, with each integer variable encoded in a qudit. We derive a general iterative formula for depth-$p$ QAOA expectation on high-girth $d$-regular graphs of arbitrary size. The cost of evaluating the formula is exponential in the QAOA depth $p$ but does not depend on the graph size. Evaluating this formula for Max-$k$-Cut problem for $p\leq 4$, we identify parameter regimes ($k=3$ with degree $d \leq 10$ and $k=4$ with $d \leq 40$) in which QAOA outperforms the Frieze-Jerrum semi-definite programming (SDP) algorithm, which provides the best worst-case guarantee on the approximation ratio. To strengthen the classical baseline we introduce a new heuristic algorithm, based on the degree-of-saturation, that empirically outperforms both the Frieze-Jerrum algorithm and shallow-depth QAOA. Nevertheless, we provide numerical evidence that QAOA may overtake this heuristic at depth $p\leq 20$. Our results show that moving beyond binary to integer optimization problems can open up new avenues for quantum advantage.
- Abstract（参考訳）: 二進最適化問題に対する量子アルゴリズムは広範な研究の対象となっている。
しかし、整数最適化問題への量子アルゴリズムの適用は、いまだに未解明である。
本稿では,量子近似最適化アルゴリズム(QAOA)をグラフ上の整数問題に適用し,各整数変数をquditに符号化する。
任意の大きさの高次$d$正則グラフ上で、深さ-p$QAOA予想に対する一般的な反復公式を導出する。
式を評価するコストはQAOAの深さ$p$で指数関数的であるが、グラフのサイズに依存しない。
この式を$p\leq 4$のMax-$k$-Cut問題に対して評価すると、QAOA が Frieze-Jerrum semi-definite programming (SDP) アルゴリズムを上回り、近似比の最悪の保証を提供するパラメータ規則($d \leq 10$ と $k=4$ と $d \leq 40$)を識別する。
古典的ベースラインを強化するために,Freeze-Jerrumアルゴリズムと浅度QAOAの両方を経験的に上回る,飽和度に基づく新しいヒューリスティックアルゴリズムを導入する。
それでも、QAOAが深さ$p\leq 20$でこのヒューリスティックを克服できるという数値的な証拠を提供する。
その結果、二進法から整数最適化問題への移動は、量子的優位性のために新しい道を開くことができることを示した。
関連論文リスト
- Phantom Edges in the Problem Hamiltonian: A Method for Increasing Performance and Graph Visibility for QAOA [0.0]
Phantom-QAOAは新しいQAOAアンサッツで、標準アンサッツに1つの追加パラメータのみを導入する。
我々は、新しいアンザッツの一般式を$p=1$で導き、サイクルグラフの近似比の改善を解析的に示す。
論文 参考訳（メタデータ） (2024-11-07T22:20:01Z) - Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている
SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。
この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
論文 参考訳（メタデータ） (2024-08-14T19:04:13Z) - Alleviating the quantum Big-$M$ problem [0.22615818641180715]
古典的には "Big-$M$" 問題として知られており、物理的エネルギースケールに影響を与える。
我々は、量子ビッグ-M$問題を体系的に包含し、最適の$M$を見つけるのにNPハードネスを明らかにする。
本稿では,SDP緩和に基づく実用的な翻訳アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-07-19T18:00:05Z) - 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) - Quantum Goemans-Williamson Algorithm with the Hadamard Test and
Approximate Amplitude Constraints [62.72309460291971]
本稿では,n+1$ qubitsしか使用しないGoemans-Williamsonアルゴリズムの変分量子アルゴリズムを提案する。
補助量子ビット上で適切にパラメータ化されたユニタリ条件として目的行列を符号化することにより、効率的な最適化を実現する。
各種NPハード問題に対して,Goemans-Williamsonアルゴリズムの量子的効率的な実装を考案し,提案プロトコルの有効性を実証する。
論文 参考訳（メタデータ） (2022-06-30T03:15:23Z) - Wasserstein Solution Quality and the Quantum Approximate Optimization
Algorithm: A Portfolio Optimization Case Study [0.0]
金融資産のポートフォリオを最適化することは、量子処理単位(QPU)に適したアルゴリズムを用いて概ね解決できる重要な産業問題である
我々は,ゲートモデルQPUをターゲットとした量子近似最適化アルゴリズム(QAOA)を用いて,このアプローチの成功をベンチマークする。
我々の焦点は、正規化および補化Wasserstein Distance, $eta$によって決定されたソリューションの品質である。
論文 参考訳（メタデータ） (2022-02-14T15:00:28Z) - The Quantum Approximate Optimization Algorithm at High Depth for MaxCut
on Large-Girth Regular Graphs and the Sherrington-Kirkpatrick Model [0.0]
量子近似最適化アルゴリズム (QAOA) は最適化問題の近似解を求める。
任意の深さで$D$に対して性能を評価するための反復式を任意の深さ$p$で与える。
我々は、QAOAが無限大の$p$でパリの価値を達成できるという楽観的な予想を立てる。
論文 参考訳（メタデータ） (2021-10-27T06:35:59Z) - Solving correlation clustering with QAOA and a Rydberg qudit system: a
full-stack approach [94.37521840642141]
量子近似最適化アルゴリズム(QAOA)とクォーディットを用いた相関クラスタリング問題について検討する。
具体的には、中性原子量子コンピュータを検討し、相関クラスタリングのためのフルスタックアプローチを提案する。
ゲート数によって定量化されるように、quditの実装はqubitエンコーディングよりも優れていることを示す。
論文 参考訳（メタデータ） (2021-06-22T11:07:38Z) - Hybrid quantum-classical algorithms for approximate graph coloring [65.62256987706128]
量子近似最適化アルゴリズム(RQAOA)をMAX-$k$-CUTに適用する方法を示す。
任意のグラフに対するレベル-$1$QAOAとレベル-$1$RQAOAをシミュレートした,効率的な古典的シミュレーションアルゴリズムを構築する。
論文 参考訳（メタデータ） (2020-11-26T18:22:21Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。