論文の概要: Undecidable problems associated with variational quantum algorithms
- arxiv url: http://arxiv.org/abs/2503.23723v1
- Date: Mon, 31 Mar 2025 04:52:43 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-04-01 14:34:43.058358
- Title: Undecidable problems associated with variational quantum algorithms
- Title（参考訳）: 変分量子アルゴリズムに付随する決定不能な問題
- Authors: Georgios Korpas, Vyacheslav Kungurtsev, Jakub Mareček,
- Abstract要約: 変分量子アルゴリズム(VQA)は、短期量子優位性の候補として広く研究されている。
近年の研究では、VQAのトレーニングは一般にNPハードであることが示されている。
本稿では,VQAのトレーニングが,理想化されたノイズレス設定であっても決定不可能であることを示す条件付き結果を提案する。
- 参考スコア（独自算出の注目度）: 2.8166046619628315
- License:
- Abstract: Variational Quantum Algorithms (VQAs), such as the Variational Quantum Eigensolver (VQE) and the Quantum Approximate Optimization Algorithm (QAOA), are widely studied as candidates for near-term quantum advantage. Recent work has shown that training VQAs is NP-hard in general. In this paper, we present a conditional result suggesting that the training of VQAs is undecidable, even in idealized, noiseless settings. We reduce the decision version of the digitized VQA training problem-where circuit parameters are drawn from a discrete set-to the question of whether a universal Diophantine equation (UDE) has a root. This reduction relies on encoding the UDE into the structure of a variational quantum circuit via the matrix exponentials. The central step involves establishing a correspondence between the objective function of the VQA and a known UDE of 58 variables and degree 4. Our main result is conditional on a natural conjecture: that a certain system of structured complex polynomial equations-arising from the inner product of a VQA circuit output and a fixed observable-has at least one solution. We argue this conjecture is plausible based on dimension-counting arguments (degrees of freedom in the Hamiltonians, state vector, and observable), and the generic solvability of such systems in algebraic geometry over the complex numbers. Under this assumption, we suggest that deciding whether a digitized VQA achieves a given energy threshold is undecidable. This links the limitations of variational quantum algorithms to foundational questions in mathematics and logic, extending the known landscape of quantum computational hardness to include uncomputability. Additionally, we establish an unconditional undecidability result for VQA convergence in open quantum systems.
- Abstract（参考訳）: 変動量子固有解法 (VQE) や量子近似最適化アルゴリズム (QAOA) のような変分量子アルゴリズム (VQA) は、短期的な量子優位性の候補として広く研究されている。
近年の研究では、VQAのトレーニングは一般にNPハードであることが示されている。
本稿では,VQAのトレーニングが,理想的,ノイズのない設定でも決定不可能であることを示す条件付き結果を示す。
我々は,デジタル化VQAトレーニング問題の決定版を減らし,回路パラメータを離散的な集合から,普遍ディオファントス方程式(UDE)が根を持つかどうかという問題に導出する。
この還元は、行列指数による変分量子回路の構造へのUDEの符号化に依存している。
中心ステップは VQA の目的関数と 58 変数と次数 4 の既知の UDE との対応を確立することである。
我々の主な結果は、VQA回路出力の内積と固定可観測性を持つ少なくとも1つの解から得られる構造化複素多項式方程式のある種の系である、という自然予想に基づく条件付きである。
この予想は次元計数論(ハミルトニアンの自由度、状態ベクトル、可観測性)と複素数上の代数幾何学におけるそのような系の一般可解性(英語版)に基づいている。
この仮定では、デジタル化されたVQAが与えられたエネルギー閾値を達成するかどうかを決定することは不可能である。
これは変分量子アルゴリズムの限界を数学と論理学の基礎的な問題に結び付け、既知の量子計算の難しさの風景を計算不能を含むように拡張する。
さらに、開量子系におけるVQA収束に対する無条件不決定性(unconditional undecidability)結果を確立する。
関連論文リスト
- Generic and Scalable Differential Equation Solver for Quantum Scientific Computing [4.067407250874754]
量子科学計算における最も重要なトピックの1つは微分方程式の解法である。
本稿では,一般化量子汎関数展開フレームワークを提案する。
一般的なQFEフレームワークを示すために、4つの微分方程式が解かれる。
論文 参考訳（メタデータ） (2024-09-24T21:09:54Z) - Variational Quantum Algorithms for Combinatorial Optimization [0.571097144710995]
変分アルゴリズム (VQA) は, NISQシステムの実用化に向けた最有力候補の1つである。
本稿では,VQAの現状と最近の発展を考察し,近似最適化への適用性を強調した。
10ノードと20ノードのグラフ上でMaxCut問題を解くために,深さの異なるQAOA回路を実装した。
論文 参考訳（メタデータ） (2024-07-08T22:02:39Z) - Quantum Subroutine for Variance Estimation: Algorithmic Design and Applications [80.04533958880862]
量子コンピューティングは、アルゴリズムを設計する新しい方法の基礎となる。
どの場の量子スピードアップが達成できるかという新たな課題が生じる。
量子サブルーチンの設計は、従来のサブルーチンよりも効率的で、新しい強力な量子アルゴリズムに固い柱を向ける。
論文 参考訳（メタデータ） (2024-02-26T09:32:07Z) - Variational Quantum Eigensolver with Constraints (VQEC): Solving Constrained Optimization Problems via VQE [0.0]
変分量子アプローチは、計算的に困難なタスクに対する準最適解を見つけることに大きな期待を示している。
この研究は、VQECと呼ばれるハイブリッド量子古典的アルゴリズムパラダイムを提案し、制約による最適化を扱う。
論文 参考訳（メタデータ） (2023-11-14T19:49:09Z) - QNEAT: Natural Evolution of Variational Quantum Circuit Architecture [95.29334926638462]
我々は、ニューラルネットワークの量子対する最も有望な候補として登場した変分量子回路(VQC)に注目した。
有望な結果を示す一方で、バレン高原、重みの周期性、アーキテクチャの選択など、さまざまな問題のために、VQCのトレーニングは困難である。
本稿では,VQCの重みとアーキテクチャの両方を最適化するために,自然進化にインスパイアされた勾配のないアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-04-14T08:03:20Z) - Fundamental limitations on optimization in variational quantum
algorithms [7.165356904023871]
そのような短期量子アプリケーションを確立するための主要なパラダイムは、変分量子アルゴリズム(VQA)である。
このようなランダム回路の幅広いクラスにおいて、コスト関数の変動範囲は、高い確率で量子ビット数で指数関数的に消えることを示す。
この結果は、勾配に基づく最適化と勾配のない最適化の制約を自然に統一し、VQAのトレーニングランドスケープに余分な厳しい制約を明らかにすることができる。
論文 参考訳（メタデータ） (2022-05-10T17:14:57Z) - Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
3次元形状と画像のマッチング問題は、NPハードな置換行列制約を持つ二次代入問題(QAP)としてしばしば定式化される。
本稿では,量子ハードウェア上での効率的な実行に適した制約のない問題として,いくつかのQAPの再構成を提案する。
提案アルゴリズムは、将来の量子コンピューティングアーキテクチャにおいて、より高次元にスケールする可能性がある。
論文 参考訳（メタデータ） (2021-07-08T17:59:55Z) - Q-Match: Iterative Shape Matching via Quantum Annealing [64.74942589569596]
形状対応を見つけることは、NP-hard quadratic assignment problem (QAP)として定式化できる。
本稿では,アルファ拡大アルゴリズムに触発されたQAPの反復量子法Q-Matchを提案する。
Q-Match は、実世界の問題にスケールできるような長文対応のサブセットにおいて、反復的に形状マッチング問題に適用できる。
論文 参考訳（メタデータ） (2021-05-06T17:59:38Z) - Efficient measure for the expressivity of variational quantum algorithms [72.59790225766777]
我々は、変分量子アルゴリズムの表現率を研究するために、統計学習理論、すなわち被覆数に関する高度なツールを利用する。
まず、任意のアンサーゼを持つVQAの表現性は、量子ゲートの数と観測可能な測定値によって上限づけられていることを示す。
次に,システムノイズを考慮した量子チップ上でのVQAの表現性について検討する。
論文 参考訳（メタデータ） (2021-04-20T13:51:08Z) - Quantum-optimal-control-inspired ansatz for variational quantum
algorithms [105.54048699217668]
変分量子アルゴリズム (VQA) の中心成分は状態準備回路(英語版)であり、アンザッツ(英語版)または変分形式(英語版)とも呼ばれる。
ここでは、対称性を破るユニタリを組み込んだ「解」を導入することで、このアプローチが必ずしも有利であるとは限らないことを示す。
この研究は、より一般的な対称性を破るアンスの開発に向けた第一歩となり、物理学や化学問題への応用に繋がる。
論文 参考訳（メタデータ） (2020-08-03T18:00:05Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。