論文の概要: Evaluating QAOA expectation values can be as hard as counting optimal solutions
- arxiv url: http://arxiv.org/abs/2608.11385v1
- Date: Tue, 11 Aug 2026 19:47:04 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-08-13 19:07:54.363108
- Title: Evaluating QAOA expectation values can be as hard as counting optimal solutions
- Title（参考訳）: QAOA予測値の評価は最適解を数えるのと同じくらい難しい。
- Abstract要約: 我々は、$pgeq 2$の精度または指数関数的に精度の高い予測値の評価が、決定論的時間チューリング削減の下で#P-hardであることを示す。
本研究の応用例として,QAOA回路の計算とヘシアンに類似した硬さ結果を示す。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Evaluating expectation values is a critical task for variational quantum eigensolvers, and for parameterized quantum circuits and other quantum algorithms more generally. We consider the well-studied case of the Quantum Approximate Optimization Algorithm (QAOA) for the MaxCut problem. Recent work of Wang et al. [arXiv:2511.20212] showed this task to be NP-hard in general for any QAOA depth $p\geq 2$, complementing past results showing efficiently computable formulas for $p=1$ with arbitrary problem graphs. We sharpen this dichotomy showing that for $p\geq 2$ exact or exponentially precise cost expectation value evaluation is #P-hard under deterministic polynomial-time Turing reductions. Hardness at $p\geq 2$ is shown to remain even for evaluating single pairwise correlators $\langle Z\otimes Z\rangle $, as well as for highly restricted sets of algorithm parameters. Our proof refines the NP-hardness construction of Wang et al. that recovers the maximum cut value from the largest exponent of a QAOA Laurent polynomial, utilizing a distinct and simpler construction that extracts a value proportional to the total number of maximum cuts, in addition to the optimal cut value. Thus we show that the QAOA expectation value hardness transition from $p=1$ to $p=2$ is not only from tractability to optimization hardness, but to that of counting optimal solutions. As an application we show our results imply analogous hardness results for computing gradients and Hessians of QAOA circuits.
- Abstract（参考訳）: 期待値を評価することは、変分量子固有解法やパラメータ化量子回路や他の量子アルゴリズムにとって、より一般的に重要なタスクである。
我々は、MaxCut問題に対する量子近似最適化アルゴリズム(QAOA)のよく研究された事例について考察する。
Wang et al [arXiv:2511.20212] の最近の研究は、このタスクが任意のQAOA深さ$p\geq 2$に対して一般にNPハードであることを示し、任意の問題グラフを持つ$p=1$の計算可能な公式を効率的に示す過去の結果を補完している。
我々は、$p\geq 2$の精度または指数関数的に精度の高いコスト予測値の評価が、決定論的多項式時間チューリング還元の下で#Pハードであることを示す。
p\geq 2$ のハードネスは、一対の相関子 $\langle Z\otimes Z\rangle $ の評価や、アルゴリズムパラメータの高度に制限された集合に対しても残る。
本稿では, QAOA Laurent 多項式の最大の指数から最大カット値を復元する Wang et al の NP-hardness 構造を改良し, 最大カット数に比例する値を抽出し, 最適カット値に加えて, より単純な構成を用いる。
したがって、QAOA期待値硬度が$p=1$から$p=2$への遷移は、トラクタビリティから最適化硬度へだけでなく、最適解を数えることからもたらされる。
本研究の応用例として,QAOA回路の勾配とヘシアンの計算結果に類似した硬度結果を示す。
関連論文リスト
- Quantum Speedups for Stochastic Optimization with Heavy-Tailed Noise [49.730496294398726]
重み付き確率変数に対する新しい量子平均推定器を開発した。
尾指数>4/3$のより強い下界を導出し、次元への非自明な依存が避けられないことを示す。
凸目的関数に対して,量子射影勾配降下法を提案する。
論文 参考訳（メタデータ） (2026-07-28T09:29:37Z) - Provably Adaptive Linear Approximation for the Shapley Value and Beyond [73.0940890296463]
基本的で長期にわたる課題は、その効率的な近似である。
一般に用いられるすべての半値に対して$P(|hatboldsymbol-boldsymbol|_2geq)leq$を必要とする線形空間アルゴリズムを開発する。
本アルゴリズムは,各ユーティリティ関数の平均二乗誤差の明示的最小化を可能にする。
論文 参考訳（メタデータ） (2026-04-09T16:38:14Z) - Quantum Approximate Optimization of Integer Graph Problems and Surpassing Semidefinite Programming for Max-k-Cut [0.8084252698425037]
グラフ上の整数問題に適用された量子近似最適化アルゴリズム(QAOA)について検討する。
任意の大きさの高次$d$正則グラフ上で、深さ-p$QAOA予想に対する一般的な反復公式を導出する。
その結果、二進法から整数最適化問題への移動は、量子的優位性のために新しい道を開くことができることを示した。
論文 参考訳（メタデータ） (2026-02-05T18:11:18Z) - 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) - 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) - Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。
我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
論文 参考訳（メタデータ） (2024-01-17T18:59:38Z) - 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) - Predicting parameters for the Quantum Approximate Optimization Algorithm
for MAX-CUT from the infinite-size limit [0.05076419064097732]
推定次数$d$のランダムエルドス・レーニグラフに適用したMAX-CUT上でのQAOAの性能を評価するための明示的なアルゴリズムを提案する。
この解析により、エルドス・レーニグラフ上のMAX-CUTのQAOAパラメータとシェリントン・カークパトリックモデルとの明示的なマッピングが得られる。
論文 参考訳（メタデータ） (2021-10-20T17:58:53Z) - Solving correlation clustering with QAOA and a Rydberg qudit system: a
full-stack approach [94.37521840642141]
量子近似最適化アルゴリズム(QAOA)とクォーディットを用いた相関クラスタリング問題について検討する。
具体的には、中性原子量子コンピュータを検討し、相関クラスタリングのためのフルスタックアプローチを提案する。
ゲート数によって定量化されるように、quditの実装はqubitエンコーディングよりも優れていることを示す。
論文 参考訳（メタデータ） (2021-06-22T11:07:38Z) - Expectation Values from the Single-Layer Quantum Approximate
Optimization Algorithm on Ising Problems [1.8732539895890135]
単一層(p=1$)量子近似最適化アルゴリズム(QAOA)によって生成されるエネルギー-観測値のランドスケープについて報告する。
景観は我々が導いた解析式を用いて得られる。
数千量子ビットの量子コンピュータ上で実行される場合、単層QAOAがどの程度うまく機能するかを推定する。
論文 参考訳（メタデータ） (2020-12-07T02:23:37Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。