論文の概要: Training Variational Quantum Algorithms Is NP-Hard, Even Locally

• arxiv url: http://arxiv.org/abs/2610.05128v1
• Date: Sun, 04 Oct 2026 11:18:55 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-10 23:11:21.992284
• Title: Training Variational Quantum Algorithms Is NP-Hard, Even Locally
• Title（参考訳）: 変分量子アルゴリズムのトレーニングはNPハード、ローカルでも
• Abstract要約: 変分量子アルゴリズムは古典的な最適化に依存して量子回路を訓練する。 このレターでは、そのようなVQAトレーニング目標の局所的な最小値を見つけるというより弱いタスクでさえ、強い$mathsfNP$-hardであることを示す。
• 参考スコア（独自算出の注目度）: 2.508240448634342
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Variational quantum algorithms (VQAs) generally rely on classical optimization to train parameterized quantum circuits. This training seeks to minimize an objective function, and its efficiency is central to the practical success of these algorithms. However, globally minimizing such training objectives over the circuit parameters is known to be $\mathsf{NP}$-hard, limiting the prospect of general guarantees for efficient training. In this Letter, we prove that even the weaker task of finding a local minimum of such VQA training objectives is strongly $\mathsf{NP}$-hard, including when the objective admits efficient classical evaluation. Moreover, we show that this hardness persists even for the task of finding a parameter vector within $\ell_p$-distance strictly less than $π/2$ of some local minimizer, for every $p\geq 1$. Our central technical result is that approximating a local minimizer of a Hermitian trigonometric polynomial is strongly $\mathsf{NP}$-hard. By explicitly constructing quantum circuits whose training objectives reproduce these hard instances, we obtain a polynomial-time reduction to VQA training. Our results establish a fundamental computational barrier to variational quantum training: even reaching the vicinity of a local minimum remains hard in the worst case.
• Abstract（参考訳）: 変分量子アルゴリズム(VQA)は一般にパラメータ化量子回路を訓練するための古典的な最適化に依存している。 この訓練は目的関数を最小化することを目的としており、その効率性はこれらのアルゴリズムの実践的な成功の中心である。 しかし、そのようなトレーニング対象を回路パラメータよりも世界規模で最小化することは$\mathsf{NP}$-hardであることが知られ、効率的なトレーニングのための一般的な保証の可能性を制限している。 本文では,VQA訓練目標の局所最小値を求める作業の弱ささえも,その目的が効率的な古典的評価を許容する場合を含め,強い$\mathsf{NP}$-hardであることを示す。 さらに、この硬さは、$\ell_p$-distance 内のパラメータベクトルを見つけるタスクでさえも、ある局所最小化器の$π/2$ より厳密には小さく、全ての$p\geq 1$ に対して持続することを示す。 我々の中心的な技術的結果は、エルミート三角多項式の局所最小値の近似が強い$\mathsf{NP}$-hardであるということである。 トレーニング目的がこれらのハードインスタンスを再現する量子回路を明示的に構築することにより、VQAトレーニングに対する多項式時間短縮が得られる。 この結果から,変分量子訓練における基本的な計算障壁が確立された。

関連論文リスト

• Verifiable quantum advantage in extremely low depth [52.51019642214249]
  浅量子回路では解けない問題を格子ベースの仮定で解くのが困難である。 浅量子回路は、解を効率よく検証できる古典的な難題を解くのに十分な構造を持っていることを証明している。
  論文  参考訳（メタデータ） (2026-09-01T15:54:34Z)
• CO-MAP: A Reinforcement Learning Approach to the Qubit Allocation Problem [1.8563570119552093]
  量子コンパイラは、抽象量子回路を物理量子コンピュータ上で実行可能にするため、量子コンピューティングパイプラインにおいて重要な部分である。 量子コンパイルにおける非常に重要なサブプロブレムの1つは、論理的-物理的量子ビットマッピングの生成である。 本稿では,量子ビットマッピング問題を解くための代替手法を提案する。
  論文  参考訳（メタデータ） (2026-05-13T15:04:09Z)
• Less is More: Convergence Benefits of Fewer Data Weight Updates over Longer Horizon [42.1998022417145]
  我々は、データ混合の収束挙動を有限個の内部ステップ$T$で解析する。 最適な$T$は$(log N)$ (resp., $((N log N)1/2)$)としてスケールし、完全なアクセスを伴うデータ混合の問題を示す。
  論文  参考訳（メタデータ） (2026-02-23T04:50:13Z)
• Sparse quantum state preparation with improved Toffoli cost [0.0]
  量子状態の生成は、量子コンピューティングにおける最も基本的なタスクの1つである。 我々は、$n$ qubitsでスパース量子状態を作成するアプローチを提案する。 速度アップは、アイソメトリの発見と実装のための効率的なアルゴリズムを設計することで達成される。
  論文  参考訳（メタデータ） (2026-01-14T11:28:27Z)
• Optimization and Synthesis of Quantum Circuits with Global Gates [41.99844472131922]
  我々は、イオントラップハードウェアに存在するGlobal Molmer-Sorensenゲートのようなグローバルな相互作用を用いて量子回路を最適化し、合成する。 このアルゴリズムはZX計算に基づいており、係留ゲートをGlobal MolmerSorensenゲートにグループ化する特別な回路抽出ルーチンを使用する。 我々は,このアルゴリズムを様々な回路でベンチマークし,最新ハードウェアによる性能向上の方法を示す。
  論文  参考訳（メタデータ） (2025-07-28T10:25:31Z)
• Gradient-Based Excitation Filter for Molecular Ground-State Simulation [6.627541720714792]
  本稿では,従来のコンピュータ上での単一および二重励起(UCCSD)アンサッツを用いたユニタリ結合クラスタを効率的に単純化する手法を提案する。 提案手法は,最大46%のパラメータ減少,60%の回路深さ減少,678タイムのランタイムを実現する。
  論文  参考訳（メタデータ） (2025-06-25T13:12:45Z)
• Training variational quantum algorithms with random gate activation [2.297921151044199]
  変分量子アルゴリズム(VQA)は、短期的な応用に大きな可能性を持っている。 VQAは深刻な不毛の高原問題に悩まされており、局所的なミニマに閉じ込められる可能性も高い。 本稿では,この2つの問題に効率よく対処するために,VQAのランダムな量子ゲートアクティベーションを用いた新しいトレーニングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-03-14T18:01:46Z)
• 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)
• Avoiding local minima in Variational Quantum Algorithms with Neural Networks [0.0]
  変分量子アルゴリズムは、短期計算の先導パラダイムとして登場してきた。 本稿では,勾配景観問題の事例をベンチマークする2つのアルゴリズムを提案する。 提案手法は,コストランドスケープが短期量子コンピューティングアルゴリズムを改善するための実りある道であることを示唆している。
  論文  参考訳（メタデータ） (2021-04-07T07:07:28Z)

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

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