論文の概要: The QAOA on the ring of disagrees
- arxiv url: http://arxiv.org/abs/2606.29562v1
- Date: Sun, 28 Jun 2026 19:00:40 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-06-30 18:07:15.959487
- Title: The QAOA on the ring of disagrees
- Title(参考訳): 不一致環上のQAOA
- Abstract要約: 我々は、QAOAがこの値を達成することを証明し、Farhi, Goldstone, Gutmann の長年の予想である。
次数 2p-1 の最適ローラン対を見つけることは同値であることを示す。
これは量子信号処理の言語でQAOAを1量子ビットで再キャストすることで実現される。
- 参考スコア(独自算出の注目度): 0.13537117504260623
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study the performance of symmetric local algorithms finding large cuts on the cycle graph. Such algorithms that cannot see the whole graph at depth p cut at most a (2p+1)/(2p+2) fraction of edges in expectation. We prove that the QAOA achieves this value, a long-standing conjecture of Farhi, Goldstone, and Gutmann. Curiously we do this without finding the optimal parameters. Instead we show it is equivalent to find an optimal pair of Laurent polynomials of degree at most 2p-1. This is made possible by recasting the QAOA on one qubit in the language of quantum signal processing.
- Abstract(参考訳): サイクルグラフ上の大きな切断点を求める対称局所アルゴリズムの性能について検討する。
深さ p でグラフ全体を見ることができないようなアルゴリズムは、予想されるエッジの少なくとも (2p+1)/(2p+2) を切断する。
我々は、QAOAがこの値を達成することを証明し、Farhi, Goldstone, Gutmann の長年の予想である。
奇妙なことに、最適なパラメータを見つけずにこれを行います。
代わりに、次数 2p-1 のローラン多項式の最適対を見つけることは同値であることを示す。
これは量子信号処理の言語でQAOAを1量子ビットで再キャストすることで実現される。
関連論文リスト
- Evaluating QAOA expectation values can be as hard as counting optimal solutions [0.0]
我々は、$pgeq 2$の精度または指数関数的に精度の高い予測値の評価が、決定論的時間チューリング削減の下で#P-hardであることを示す。
本研究の応用例として,QAOA回路の計算とヘシアンに類似した硬さ結果を示す。
論文 参考訳(メタデータ) (2026-08-11T19:47:04Z) - Quantum Speedups for Stochastic Optimization with Heavy-Tailed Noise [49.730496294398726]
重み付き確率変数に対する新しい量子平均推定器を開発した。
尾指数>4/3$のより強い下界を導出し、次元への非自明な依存が避けられないことを示す。
凸目的関数に対して,量子射影勾配降下法を提案する。
論文 参考訳(メタデータ) (2026-07-28T09:29:37Z) - A Unified Complexity-Algorithm Account of Constant-Round QAOA Expectation Computation [5.137643077079792]
一般グラフと任意の固定ラウンド$pge2$に対して、所定の角度での固定ラウンドQAOAの期待を正確に評価することは、$mathrmNP$-hardであることを示す。
フレームワークを汎用バイナリ非制約組合せ最適化(BUCO)に拡張する。
論文 参考訳(メタデータ) (2025-11-25T11:35:37Z) - 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) - Modified Recursive QAOA for Exact Max-Cut Solutions on Bipartite Graphs: Closing the Gap Beyond QAOA Limit [4.364124102844566]
量子近似最適化アルゴリズム(Quantum Approximate Optimization Algorithm, QAOA)は、MAX-CUT問題などの最適化問題を概ね解くことを目的として提案された量子古典ハイブリッドアルゴリズムである。
まず、二部グラフ上のMAX-CUT問題の解法におけるレベル1QAOAの性能限界を解析的に証明する。
第2に、再帰的QAOA(RQAOA)は、QAOAをサブルーチンとしてグラフサイズを削減し、レベル1のQAOAを上回る性能を示す。
最後に,制限パラメータを持つRQAOAが,これらの制約に完全に対処可能であることを示す。
論文 参考訳(メタデータ) (2024-08-23T16:35:47Z) - Moments, Random Walks, and Limits for Spectrum Approximation [40.43008834125277]
我々は、ワッサーシュタイン1距離において精度$epsilon$に近似できない$[-1,1]$に分布が存在することを示す。
正規化グラフ隣接行列のスペクトルに対する$epsilon$-accurate近似を一定の確率で計算することはできない。
論文 参考訳(メタデータ) (2023-07-02T05:03:38Z) - A Newton-CG based barrier-augmented Lagrangian method for general nonconvex conic optimization [53.044526424637866]
本稿では、2つの異なる対象の一般円錐最適化を最小化する近似二階定常点(SOSP)について検討する。
特に、近似SOSPを見つけるためのNewton-CGベースの拡張共役法を提案する。
論文 参考訳(メタデータ) (2023-01-10T20:43:29Z) - Quantum Depth in the Random Oracle Model [57.663890114335736]
浅量子回路の計算能力と古典計算の組合せを包括的に評価する。
いくつかの問題に対して、1つの浅い量子回路で適応的な測定を行う能力は、適応的な測定をせずに多くの浅い量子回路を実行する能力よりも有用である。
論文 参考訳(メタデータ) (2022-10-12T17:54:02Z) - Polyak-Ruppert Averaged Q-Leaning is Statistically Efficient [90.14768299744792]
我々はPolyak-Ruppert 平均 Q-leaning (平均 Q-leaning) を用いた同期 Q-learning を$gamma$-discounted MDP で検討した。
繰り返し平均$barboldsymbolQ_T$に対して正規性を確立する。
要するに、我々の理論分析は、Q-Leaningの平均は統計的に効率的であることを示している。
論文 参考訳(メタデータ) (2021-12-29T14:47:56Z) - 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) - The Quantum Approximate Optimization Algorithm Needs to See the Whole
Graph: Worst Case Examples [6.810856082577402]
量子近似最適化アルゴリズムは、エッジに対応する項の和であるコスト関数を持つグラフ上の探索問題に適用することができる。
我々は、$(d-1)2p nA$ の QAOA が任意の$A1$ に対して、d 大のランダムな d-正規グラフ上の Max-Cut に対して 1/2 の近似比しか達成できないことを示す。
論文 参考訳(メタデータ) (2020-05-18T14:23:09Z) - The Quantum Approximate Optimization Algorithm Needs to See the Whole
Graph: A Typical Case [6.810856082577402]
量子回路は、グラフの局所性を尊重するユニタリ作用素の p 個の応用を持つ。
我々は、d と n を大きく保った dn/2 エッジを持つランダムグラフにおいて、大きな独立集合を見つけることに集中する。
論文 参考訳(メタデータ) (2020-04-20T00:48:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。