論文の概要: The Quantum Approximate Optimization Algorithm Can Require Exponential Time to Optimize Linear Functions
- arxiv url: http://arxiv.org/abs/2505.06404v2
- Date: Mon, 26 May 2025 18:23:43 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-05-28 14:37:19.36915
- Title: The Quantum Approximate Optimization Algorithm Can Require Exponential Time to Optimize Linear Functions
- Title（参考訳）: 線形関数を最適化するために指数時間を必要とする量子近似最適化アルゴリズム
- Authors: Francisco Chicano, Zakaria Abdelmoiz Dahi, Gabriel Luque,
- Abstract要約: ここでは,QAOAが線形関数を解くのに指数時間を要することを示す。
我々は QAOA が任意の定数 $p$ に対して線型関数の大域的最適化を求めるには指数時間が必要であると推測し、ランタイムが線型であることは$p geq n$ の場合のみである。
- 参考スコア（独自算出の注目度）: 1.3108652488669732
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: QAOA is a hybrid quantum-classical algorithm to solve optimization problems in gate-based quantum computers. It is based on a variational quantum circuit that can be interpreted as a discretization of the annealing process that quantum annealers follow to find a minimum energy state of a given Hamiltonian. This ensures that QAOA must find an optimal solution for any given optimization problem when the number of layers, $p$, used in the variational quantum circuit tends to infinity. In practice, the number of layers is usually bounded by a small number. This is a must in current quantum computers of the NISQ era, due to the depth limit of the circuits they can run to avoid problems with decoherence and noise. In this paper, we show mathematical evidence that QAOA requires exponential time to solve linear functions when the number of layers is less than the number of different coefficients of the linear function $n$. We conjecture that QAOA needs exponential time to find the global optimum of linear functions for any constant value of $p$, and that the runtime is linear only if $p \geq n$. We conclude that we need new quantum algorithms to reach quantum supremacy in quantum optimization.
- Abstract（参考訳）: QAOAはゲートベース量子コンピュータの最適化問題を解くためのハイブリッド量子古典アルゴリズムである。
これは変分量子回路に基づいており、量子異性体が従うアニール過程の離散化として解釈でき、与えられたハミルトニアンの最小エネルギー状態を求める。
これにより、QAOAは、変動量子回路で使用される層数$p$が無限大となる場合、任意の最適化問題に対して最適な解を見つけなければならない。
実際には、レイヤの数は通常、少数の数で制限される。
これは現在のNISQ時代の量子コンピュータでは必須であり、デコヒーレンスやノイズの問題を避けるために動作可能な回路の深さ制限のためである。
本稿では,QAOAが線形関数を解くのに指数時間を要するという数学的証拠を示す。
QAOA は任意の定数 $p$ に対して線型関数の大域的最適化を求める指数時間を必要とし、ランタイムが線型であることは$p \geq n$ の場合のみである。
我々は、量子最適化において量子超越性に到達するために新しい量子アルゴリズムが必要であると結論づける。
関連論文リスト
- Optimization by Decoded Quantum Interferometry [43.55132675053983]
Decoded Quantum Interferometry (DQI) という量子アルゴリズムを導入する。
有限フィールド上のデータに対する最適適合性を近似するために、DQIは我々の知る時間よりも優れた近似比を達成する。
30,000以上の変数を持つインスタンスをベンチマークすることで、これを実証します。
論文 参考訳（メタデータ） (2024-08-15T17:47:42Z) - Calculating response functions of coupled oscillators using quantum phase estimation [40.31060267062305]
量子コンピュータを用いた結合型古典的高調波発振器系の周波数応答関数の推定問題について検討する。
提案する量子アルゴリズムは,標準的な$sスパース,オーラクルベースのクエリアクセスモデルで動作する。
そこで,本アルゴリズムの簡単な適応により,時間内に無作為な結束木問題を解くことを示す。
論文 参考訳（メタデータ） (2024-05-14T15:28:37Z) - Q-Newton: Hybrid Quantum-Classical Scheduling for Accelerating Neural Network Training with Newton's Gradient Descent [37.59299233291882]
本稿では,ニュートンのGDを用いたニューラルネットワークトレーニングの高速化を目的とした,ハイブリッド量子古典スケジューラQ-Newtonを提案する。
Q-Newtonは量子と古典的な線形解法を協調する合理化スケジューリングモジュールを使用している。
評価の結果,Q-Newtonは一般的な量子機械と比較してトレーニング時間を大幅に短縮できる可能性が示された。
論文 参考訳（メタデータ） (2024-04-30T23:55:03Z) - Quantum Dueling: an Efficient Solution for Combinatorial Optimization [3.7398607565670536]
量子デュエル(quantum dueling)と呼ぶ汎用最適化のための新しいアルゴリズムを提案する。
量子デュエルは、追加のqubitレジスタを統合することで革新的であり、2組のソリューションが競合するデュエルのシナリオを効果的に生成する。
我々の研究は、量子ビットの数を増やすことで、これまで考えられていなかったアルゴリズムの開発が可能になり、効率的な量子アルゴリズム設計の進歩の道を開くことを実証している。
論文 参考訳（メタデータ） (2023-02-20T18:33:55Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳（メタデータ） (2022-12-06T22:01:49Z) - Quantum State Preparation with Optimal Circuit Depth: Implementations
and Applications [10.436969366019015]
我々は、$Theta(n)$-depth回路は、$O(ndlog d)$ acillary qubitsを持つ$Theta(log(nd))で作成可能であることを示す。
我々は、ハミルトンシミュレーション、方程式の線形系解法、量子ランダムアクセスメモリの実現など、異なる量子コンピューティングタスクにおける結果の適用について論じる。
論文 参考訳（メタデータ） (2022-01-27T13:16:30Z) - Efficient Classical Computation of Quantum Mean Values for Shallow QAOA
Circuits [15.279642278652654]
浅いQAOA回路の量子ビット数と線形にスケールするグラフ分解に基づく古典的アルゴリズムを提案する。
我々の結果は、QAOAによる量子アドバンテージの探索だけでなく、NISQプロセッサのベンチマークにも有用である。
論文 参考訳（メタデータ） (2021-12-21T12:41:31Z) - Estimating Gibbs partition function with quantumClifford sampling [6.656454497798153]
分割関数を推定するハイブリッド量子古典アルゴリズムを開発した。
我々のアルゴリズムは浅い$mathcalO(1)$-depth量子回路を必要とする。
浅層量子回路は、現在利用可能なNISQ(ノイズ中間スケール量子)デバイスにとって極めて重要であると考えられている。
論文 参考訳（メタデータ） (2021-09-22T02:03:35Z) - Quantum Gram-Schmidt Processes and Their Application to Efficient State
Read-out for Quantum Algorithms [87.04438831673063]
本稿では、生成した状態の古典的ベクトル形式を生成する効率的な読み出しプロトコルを提案する。
我々のプロトコルは、出力状態が入力行列の行空間にある場合に適合する。
我々の技術ツールの1つは、Gram-Schmidt正則手順を実行するための効率的な量子アルゴリズムである。
論文 参考訳（メタデータ） (2020-04-14T11:05:26Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。