論文の概要: Why adiabatic quantum annealing is unlikely to yield speed-up
- arxiv url: http://arxiv.org/abs/2212.13649v1
- Date: Wed, 28 Dec 2022 00:05:30 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-09 02:07:22.832897
- Title: Why adiabatic quantum annealing is unlikely to yield speed-up
- Title（参考訳）: adiabatic quantum annealingはなぜスピードアップしないのか
- Authors: Aar\'on Villanueva, Peyman Najafi, Hilbert J. Kappen
- Abstract要約: 我々は最小のスペクトルギャップを$mathcalO (1/sqrtN)$で解析的に計算し、状態の総数とその位置を$N$とする。
量子スピードアップは、最適化問題の状態の密度が分かっている場合にのみ計算できる$z_*$の正確な知識を必要とすることを示す。
- 参考スコア（独自算出の注目度）: 0.9023847175654603
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study quantum annealing for combinatorial optimization with Hamiltonian $H
= z H_f + H_0$ where $H_f$ is diagonal, $H_0=-|\phi \rangle \langle \phi|$ is
the equal superposition state projector and $z$ the annealing parameter. We
analytically compute the minimal spectral gap as $\mathcal{O}(1/\sqrt{N})$ with
$N$ the total number of states and its location $z_*$. We show that quantum
speed-up requires an annealing schedule which demands a precise knowledge of
$z_*$, which can be computed only if the density of states of the optimization
problem is known. However, in general the density of states is intractable to
compute, making quadratic speed-up unfeasible for any practical combinatoric
optimization problems. We conjecture that it is likely that this negative
result also applies for any other instance independent transverse Hamiltonians
such as $H_0 = -\sum_{i=1}^n \sigma_i^x$.
- Abstract（参考訳）: h = z h_f + h_0$ ここで$h_f$ は対角的、$h_0=-|\phi \rangle \langle \phi|$ は等しい重ね合わせ状態プロジェクタであり、$z$ はアニーリングパラメータである。
解析的に最小のスペクトルギャップを$\mathcal{o}(1/\sqrt{n})$と計算し、n$ the total of states and its location $z_*$ と計算する。
量子速度アップには、最適化問題の状態密度が分かっている場合にのみ計算可能な$z_*$の正確な知識を必要とするアニーリングスケジュールが必要であることを示す。
しかし、一般に状態の密度は計算が困難であり、実用的な組合せ最適化問題では二次的なスピードアップは不可能である。
我々は、この負の結果が$h_0 = -\sum_{i=1}^n \sigma_i^x$のような任意のインスタンス独立な逆ハミルトニアンにも適用される可能性が高いと推測する。
関連論文リスト
- On Quantum Channel Learning [0.0]
$mathcalU$fidelity 上の二次体は、$sqrtrho(l) to sqrtvarrho(l)$ mapping と、クラウス階数 $N_s$ の一般的な量子チャネル上で構成できることが示されている。
このアプローチは、デコヒーレンス効果、自然的コヒーレンス、同期などを研究するために適用することができる。
論文 参考訳（メタデータ） (2024-07-05T10:43:24Z) - Measuring quantum relative entropy with finite-size effect [53.64687146666141]
相対エントロピー$D(rho|sigma)$を$sigma$が知られているときに推定する。
我々の推定器は次元$d$が固定されたときにCram'er-Rao型境界に達する。
論文 参考訳（メタデータ） (2024-06-25T06:07:20Z) - Hamiltonian simulation for low-energy states with optimal time dependence [45.02537589779136]
低エネルギー部分空間内のハミルトン$H$の下で時間発展をシミュレートする作業を考える。
我々は,$O(tsqrtlambdaGamma + sqrtlambda/Gammalog (1/epsilon))$クエリを,任意の$Gamma$に対するブロックエンコーディングに使用する量子アルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-04-04T17:58:01Z) - The classical limit of Quantum Max-Cut [0.18416014644193066]
我々は、大きな量子スピンの極限$S$は半古典的極限として理解されるべきであることを示した。
半定値プログラムの出力をブロッホコヒーレント状態の積に丸め、$mathrmQMaxCut_S$に対する古典近似アルゴリズムの2つのファミリを示す。
論文 参考訳（メタデータ） (2024-01-23T18:53:34Z) - Near-Optimal Bounds for Learning Gaussian Halfspaces with Random
Classification Noise [50.64137465792738]
この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。
我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
論文 参考訳（メタデータ） (2023-07-13T18:59:28Z) - An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue
Optimization Problems [76.2042837251496]
相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。
注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。
本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
論文 参考訳（メタデータ） (2023-06-30T08:34:29Z) - A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
しきい値定理は、フォールトトレラント量子計算の理論における基本的な結果である。
振幅雑音を伴う耐故障性量子計算の最大長に対する指数的上限を証明した。
論文 参考訳（メタデータ） (2022-01-31T22:19:49Z) - Random quantum circuits transform local noise into global white noise [118.18170052022323]
低忠実度状態におけるノイズランダム量子回路の測定結果の分布について検討する。
十分に弱くユニタリな局所雑音に対して、一般的なノイズ回路インスタンスの出力分布$p_textnoisy$間の相関(線形クロスエントロピーベンチマークで測定)は指数関数的に減少する。
ノイズが不整合であれば、出力分布は、正確に同じ速度で均一分布の$p_textunif$に近づく。
論文 参考訳（メタデータ） (2021-11-29T19:26:28Z) - Improved approximation algorithms for bounded-degree local Hamiltonians [12.961180148172197]
与えられた積状態によって達成される近似比を改善するために使用できる浅量子回路群について述べる。
結果は、$k$-local Hamiltonianと絡み合った初期状態に拡張します。
論文 参考訳（メタデータ） (2021-05-03T22:23:47Z) - Enhancing the Quantum Linear Systems Algorithm using Richardson
Extrapolation [0.8057006406834467]
Amathbfx=mathbfb$という形の線形方程式の系を解く量子アルゴリズムを提案する。
このアルゴリズムは古典的手法に対して$N$に対して指数関数的に改善する。
論文 参考訳（メタデータ） (2020-09-09T18:00:09Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。