論文の概要: Fault-tolerant cost of shallow QAOA on near-symmetric optimization problems

• arxiv url: http://arxiv.org/abs/2609.39922v1
• Date: Wed, 30 Sep 2026 15:11:20 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-01 18:57:27.963767
• Title: Fault-tolerant cost of shallow QAOA on near-symmetric optimization problems
• Title（参考訳）: 準対称最適化問題における浅部QAOAの耐故障コスト
• Abstract要約: 深さ1量子近似最適化アルゴリズム (QAOA) は, ある種の近対称制約満足度問題の植込み解を求める。 我々は、小角クリフォード$+T$合成回転により、回路当たりの非クリフォードコストが各節の局所性に対して$widetilde O(n2)$に削減されることを示す。 一定のQAOA成功の根底にあるメカニズムは、コストの次数1フーリエ係数を補正し、その兆候は植付された解を明らかにする。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Montanaro and Zhou proved that depth-one Quantum Approximate Optimization Algorithm (QAOA) finds the planted solution of certain near-symmetric constraint satisfaction problems with probability $Ω(1)$, and observed exponential runtimes for general-purpose classical solvers on explicit realizations, providing strong evidence of an empirical exponential speedup of low-depth QAOA. We ask what such a circuit costs fault-tolerantly. Although the cost Hamiltonian carries $Θ(n^\ell)$ clauses, the rotation angle at which QAOA succeeds shrinks as $n^{1-\ell}$, and we show that small-angle Clifford$+T$ rotation synthesis reduces the non-Clifford cost per circuit to $\widetilde O(n^2)$ for every clause locality $\ell$. Compiling the circuit, however, requires the explicit clause list. We find that the mechanism underlying constant QAOA success fixes the degree-one Fourier coefficients of the cost, whose signs reveal the planted solution. However, this leakage need not reveal the solution: we design families in which the quadratic non-Clifford scaling and hard exact optimization coexist.
• Abstract（参考訳）: モンタナロと周は、深さ1の量子近似最適化アルゴリズム (QAOA) が確率$Ω(1)$の近対称制約満足度問題の植込み解を見つけ、明示的な実現に関する一般の古典的解法に対する指数的実行を観察し、低深度QAOAの指数的高速化の実証的な証拠を与えることを示した。 このような回路は耐障害性が高いか尋ねる。 コストは、ハミルトニアンが$(n^\ell)$節を運ぶが、QAOAが成功する回転角は$n^{1-\ell}$に縮まり、小角Clifford$+T$回転合成が回路当たりの非クリフォードコストを$\widetilde O(n^2)$に還元することを示す。 しかし、回路をコンパイルするには明示的な節リストが必要である。 一定のQAOA成功の根底にあるメカニズムは、コストの次数1フーリエ係数を補正し、その兆候は植付された解を明らかにする。 しかし、このリークは解決方法を明らかにする必要はない:我々は二次的な非クリフォードスケーリングと厳密な最適化が共存するファミリを設計する。

関連論文リスト

• More efficient Clifford+T synthesis for small-angle rotations and application to Trotterization [1.3048920509133806]
  我々は、小さな角度ではずっと良くでき、Tコストを$tilde O(2/)$に減らし、最悪の場合、既存の$O(log1/)$に戻すことができることを示した。 我々の研究はクリフォード+T回転合成が$$とは無関係に高コストであることの主張を退け、さらに回転合成のためのスケーラブルな準確率法を開発した。
  論文  参考訳（メタデータ） (2026-05-29T16:59:34Z)
• Provably Efficient Algorithms for S- and Non-Rectangular Robust MDPs with General Parameterization [85.91302339486673]
  我々は、s-正方形および非正方形不確実性集合の下で、一般的な政策パラメータ化を伴うロバストマルコフ決定過程(RMDP)について検討する。 無限状態空間に拡張する一般政策パラメタライゼーションに対する新しいリプシッツ・リプシッツ・スムースネス特性を証明した。 本研究では,S-正方形不確かさに対する勾配降下アルゴリズムと非正方形不確かさに対するFrank-Wolfeアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2026-02-11T21:44:20Z)
• Evidence that the Quantum Approximate Optimization Algorithm Optimizes the Sherrington-Kirkpatrick Model Efficiently in the Average Case [3.4872784636892047]
  Sherrington-Kirkpatrick(SK)モデルは、混乱したシステムを理解するための基盤となるフレームワークである。 量子近似最適化アルゴリズム (Quantum Approximate Optimization Algorithm, QAOA) は、量子最適化アルゴリズムであり、その性能は深さ$p$で単調に向上する。 無限大の極限においてSKモデルに適用されたQAOAを解析し、回路深さ$mathcalO(n/epsilon1.13)$の最適エネルギーに対して1-epsilon$の近似が得られるという数値的な証拠を与える。
  論文  参考訳（メタデータ） (2025-05-12T18:00:01Z)
• Convergence Rate Analysis of LION [54.28350823319057]
  LION は、勾配カルシュ=クーン=T (sqrtdK-)$で測定された $cal(sqrtdK-)$ の反復を収束する。 従来のSGDと比較して,LIONは損失が小さく,性能も高いことを示す。
  論文  参考訳（メタデータ） (2024-11-12T11:30:53Z)
• Quantum speedups in solving near-symmetric optimization problems by low-depth QAOA [0.0]
  我々は、対称性を示し、植込み解を含む最適化問題の族に焦点をあてる。 1ステップの量子近似最適化アルゴリズム (QAOA) が$Omega (1/sqrtn)$の成功確率を実現することを厳密に証明する。 最後に、準対称なMax-SAT問題の様々なファミリーを構築し、最先端の古典的解法をベンチマークする。
  論文  参考訳（メタデータ） (2024-11-07T18:51:44Z)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。 我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
  論文  参考訳（メタデータ） (2024-01-17T18:59:38Z)
• 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)
• The Parameterized Complexity of Quantum Verification [7.7155343772895275]
  量子回路の整合性の問題に対して,非クリフォードゲート数で指数関数的にスケーリングすることで問題を解くアルゴリズムが存在することを示す。 我々は、サーキット適合性のインスタンスの$T$-countと$W$-stateの$$$-countに新しい下位境界を導出する。
  論文  参考訳（メタデータ） (2022-02-16T14:53:42Z)
• 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)
• Solving correlation clustering with QAOA and a Rydberg qudit system: a full-stack approach [94.37521840642141]
  量子近似最適化アルゴリズム(QAOA)とクォーディットを用いた相関クラスタリング問題について検討する。 具体的には、中性原子量子コンピュータを検討し、相関クラスタリングのためのフルスタックアプローチを提案する。 ゲート数によって定量化されるように、quditの実装はqubitエンコーディングよりも優れていることを示す。
  論文  参考訳（メタデータ） (2021-06-22T11:07:38Z)

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

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