論文の概要: Complexity Barriers to State Preparation in Quantum Approximate Optimization

• arxiv url: http://arxiv.org/abs/2609.31520v1
• Date: Fri, 25 Sep 2026 16:57:00 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-28 18:27:51.497236
• Title: Complexity Barriers to State Preparation in Quantum Approximate Optimization
• Title（参考訳）: 量子近似最適化における状態形成への複雑性バリア
• Abstract要約: MaxCut の場合、ほぼ一様(通常の)近似比はランダムなカットよりもゼロに近い改善(ゲイン)と共存することができる。 標準的なエンコーディングでは、無条件のMaxCut-Gain硬さギャップは、全ての入力において最適古典的利得の固定された正の分率を回復する一様効率の量子またはハイブリッドプロシージャが、少なくとも逆多項式の成功確率でNPエンプチンBQPを配置することを意味する。 量子乱数アクセス最適化(QRAO)圧縮を継続し、古典的および緩和的最適値間の適用を証明した。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: For many important optimization problems we are restricted to approximate solutions in practice due to computational complexity. Distinct from the exact optimization setting, approximate optimization admits performance measures beyond whether the optimum is found, with different tradeoffs and complexity. For MaxCut, a near-unity (ordinary) approximation ratio can coexist with near-zero improvement (gain) over a random cut. For the standard encoding, the unconditional classical MaxCut-Gain hardness gap implies that \emph{any uniformly efficient quantum or hybrid procedure recovering a fixed positive fraction of the optimal classical gain on every input, with at least inverse-polynomial success probability, would place} NP \emph{in} BQP. Such a procedure is therefore believed impossible under standard assumptions. We broadly address where our worst-case barriers do or do not apply across the quantum algorithm landscape. We prove that the barrier survives quantum random access optimization (QRAO) compression and applies between the classical and relaxed optimal values. For every input, a product state attains the classical optimum. Thus the barrier to reaching the classical threshold does not arise from a need for entanglement. For $d\in\{2,3\}$ variables per qubit, the known decoder transfers encoded energy gain to decoded mean gain by the exact factor $1/d^2$. Combining this identity with MaxCut-Gain hardness gives an operational preparation barrier for QRAO. We also construct hard $n$-qubit families with relative quantum relaxation excess $Θ(1/n)$, while the maximally mixed state has energy approximation ratio $1-Θ(1/n)$, zero encoded energy gain, and hence zero decoded mean gain. Our results separate the effects of relaxation tightness and energy approximation from operational accessibility, motivating more comprehensive accounting in benchmarking and performance assessment.
• Abstract（参考訳）: 多くの重要な最適化問題に対して、計算複雑性のため、実際には近似解に制限される。 正確な最適化設定とは別として、近似最適化は、最適化が見つかるかどうかを超えるパフォーマンス対策を、異なるトレードオフと複雑さで認める。 MaxCut の場合、ほぼ一様(通常の)近似比はランダムなカットよりもゼロに近い改善(ゲイン)と共存することができる。 標準的なエンコーディングでは、非条件の古典的マックスコート-ゲイン硬度ギャップは、全ての入力において最適古典的ゲインの固定正の分率を回復する \emph{any が、少なくとも逆多項式成功確率でNP \emph{in} BQP を配置することを意味する。 したがって、そのような手続きは標準的な仮定では不可能であると考えられている。 我々は、量子アルゴリズムのランドスケープ全体で最悪の障壁がどこにあるか、あるいは適用されないかに広く対処する。 量子乱数アクセス最適化(QRAO)圧縮を継続し、古典的および緩和的最適値間の適用を証明した。 すべての入力に対して、積状態は古典的最適値に達する。 したがって、古典的なしきい値に達するための障壁は、絡み合いの必要性から生じない。 量子ビット当たりの$d\in\{2,3\}$変数に対して、既知のデコーダはエンコードされたエネルギーゲインを1/d^2$の正確な係数でデコードされた平均ゲインに転送する。 このアイデンティティとMaxCut-Gain硬さを組み合わせることで、QRAOの運用上の準備障壁となる。 また、強い$n$-qubit族を、相対的な量子緩和過剰$(1/n)$で構成する一方、最大混合状態はエネルギー近似比1〜2(1/n)$、ゼロエンコードエネルギーゲインを持ち、したがってゼロデコード平均ゲインを持つ。 本研究の結果は, 緩やかさとエネルギー近似の影響を操作的アクセシビリティから切り離し, ベンチマークや性能評価において, より包括的な会計を動機付けている。

関連論文リスト

• Performance guarantees of light-cone variational quantum algorithms for the maximum cut problem [12.148326652334598]
  変分量子アルゴリズム(VQA)は、古典的計算よりも短期的な量子コンピューティングの利点を実証することを約束している。 本稿では,標準VQAの最適ゲート列を選択することで,光円錐VQAを提案する。 1ラウンドの光円錐VQAはMaxCut問題に対して0.7926の近似比が得られることを示す。
  論文  参考訳（メタデータ） (2025-04-17T12:38:16Z)
• Limitations of Quantum Approximate Optimization in Solving Generic Higher-Order Constraint-Satisfaction Problems [0.0]
  量子近似最適化アルゴリズムの最適化問題に対する量子優位性を実現する能力はまだ不明である。 ランダムなMax-$k$XOR上でのQAOAの性能を$k$の関数と節対変数比として解析する。 満足度の高いレベルに達するには、非常に大きな$p$が必要であり、変動コンテキストと短期デバイスの両方において、かなり難しいとみなす必要がある。
  論文  参考訳（メタデータ） (2024-11-28T21:39:58Z)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。 我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
  論文  参考訳（メタデータ） (2024-01-17T18:59:38Z)
• Quasi-binary encoding based quantum alternating operator ansatz [7.681120805934572]
  本稿では, 離散変数を持つ2次最適化モデルを解くための準バイナリ符号化に基づくアルゴリズムを提案する。 QAOAフレームワークの他の部分では、CVaR-QAOAやパラメータスケジューリング手法といったアイデアもQAOAアルゴリズムに取り入れています。
  論文  参考訳（メタデータ） (2023-04-14T03:49:26Z)
• 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)
• Calibrating the Classical Hardness of the Quantum Approximate Optimization Algorithm [0.0]
  スケールのためのトレーディング忠実さは、近似古典的シミュレーターが正確な方法を超える量子回路を走らせることを可能にする。 最小化を目指すコスト関数の期待値を用いて、量子近似最適化アルゴリズムの忠実度を特徴付ける。 現実的な設定で量子ハードウェアの性能をベンチマークする。
  論文  参考訳（メタデータ） (2022-06-13T17:45:59Z)
• 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)
• Twisted hybrid algorithms for combinatorial optimization [68.8204255655161]
  提案されたハイブリッドアルゴリズムは、コスト関数をハミルトニアン問題にエンコードし、回路の複雑さの低い一連の状態によってエネルギーを最適化する。 レベル$p=2,ldots, 6$の場合、予想される近似比をほぼ維持しながら、レベル$p$を1に減らすことができる。
  論文  参考訳（メタデータ） (2022-03-01T19:47:16Z)

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

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