論文の概要: (Sub)Exponential advantage of adiabatic quantum computation with no sign
problem
- arxiv url: http://arxiv.org/abs/2011.09495v1
- Date: Wed, 18 Nov 2020 19:04:51 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-23 19:08:05.980163
- Title: (Sub)Exponential advantage of adiabatic quantum computation with no sign
problem
- Title(参考訳): (sub)符号問題のない断熱量子計算の指数的利点
- Authors: Andr\'as Gily\'en and Umesh Vazirani
- Abstract要約: 符号問題のないギャップ付きハミルトニアンの断熱経路に従う量子アルゴリズムによる(部分)指数量子スピードアップの可能性を示す。
このスピードアップを示すハミルトニアンは、無向グラフの隣接行列に由来する。
- 参考スコア(独自算出の注目度): 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We demonstrate the possibility of (sub)exponential quantum speedup via a
quantum algorithm that follows an adiabatic path of a gapped Hamiltonian with
no sign problem. This strengthens the superpolynomial separation recently
proved by Hastings. The Hamiltonian that exhibits this speed-up comes from the
adjacency matrix of an undirected graph, and we can view the adiabatic
evolution as an efficient $\mathcal{O}(\mathrm{poly}(n))$-time quantum
algorithm for finding a specific "EXIT" vertex in the graph given the
"ENTRANCE" vertex. On the other hand we show that if the graph is given via an
adjacency-list oracle, there is no classical algorithm that finds the "EXIT"
with probability greater than $\exp(-n^\delta)$ using at most $\exp(n^\delta)$
queries for $\delta= \frac15 - o(1)$. Our construction of the graph is somewhat
similar to the "welded-trees" construction of Childs et al., but uses
additional ideas of Hastings for achieving a spectral gap and a short adiabatic
path.
- Abstract(参考訳): 我々は,符号問題のないガッピングハミルトニアンの断熱経路に従う量子アルゴリズムを用いて,(サブ)指数量子スピードアップの可能性を示す。
これにより、最近hastingsによって証明された超多項分離が強化される。
このスピードアップを示すハミルトニアンは、無向グラフの隣接行列から来ており、「ENTRANCE」頂点が与えられたグラフの特定の「EXIT」頂点を見つけるための効率的な$\mathcal{O}(\mathrm{poly}(n))$-time量子アルゴリズムとして、断熱的進化を見ることができる。
一方、グラフが隣接リストのオラクルを介して与えられるならば、$\exp(-n^\delta)$ 以上の確率で$\delta= \frac15 - o(1)$ のクエリを最大$\exp(n^\delta)$ で使用する「exit」を見つける古典的なアルゴリズムは存在しない。
私たちのグラフの構築は、Childsらによる"welded-trees"構築と多少似ているが、スペクトルギャップと短い断熱経路を達成するためにHastingsのさらなるアイデアを使用している。
関連論文リスト
- Exponential speedups for quantum walks in random hierarchical graphs [6.896797484250303]
量子ウォークを階層グラフのクラスに一般化する方法を示す。
これらのグラフ上の量子ウォークのヒット時間は、特定の乱れた強結合ハミルトニアンにおけるゼロモードの局在特性に関係している。
論文 参考訳(メタデータ) (2023-07-27T17:59:58Z) - Moments, Random Walks, and Limits for Spectrum Approximation [40.43008834125277]
我々は、ワッサーシュタイン1距離において精度$epsilon$に近似できない$[-1,1]$に分布が存在することを示す。
正規化グラフ隣接行列のスペクトルに対する$epsilon$-accurate近似を一定の確率で計算することはできない。
論文 参考訳(メタデータ) (2023-07-02T05:03:38Z) - Parameter-free Regret in High Probability with Heavy Tails [45.11667443216861]
非有界領域に対するオンライン凸最適化のための新しいアルゴリズムを提案する。
高確率のパラメータフリーな後悔は、潜在的に重み付き下次推定にのみアクセス可能である。
論文 参考訳(メタデータ) (2022-10-25T21:43:44Z) - Multimarked Spatial Search by Continuous-Time Quantum Walk [0.0]
任意のグラフ上の連続時間量子ウォークによる空間探索の計算複雑性を決定するためのフレームワークについて述べる。
量子ウォークは、マークされた頂点の存在によって修正されたグラフの隣接行列に由来するハミルトン行列によって駆動される。
論文 参考訳(メタデータ) (2022-03-27T20:22:17Z) - The Exact Class of Graph Functions Generated by Graph Neural Networks [43.25172578943894]
グラフ関数と出力が同一のグラフニューラルネットワーク(GNN)?
本稿では,この疑問に完全に答え,GNNで表現可能なグラフ問題のクラスを特徴付ける。
この条件は2次的に多くの制約をチェックすることで効率よく検証できることを示す。
論文 参考訳(メタデータ) (2022-02-17T18:54:27Z) - A quantum searching model finding one of the edges of a subgraph in a
complete graph [0.0]
我々は,与えられた部分グラフのエッジの1つを完全グラフで探索する量子探索モデルを構築した。
モデルが任意の部分グラフ、すなわち完備グラフに対して有効であることを示す。
論文 参考訳(メタデータ) (2022-02-03T08:45:39Z) - A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
しきい値定理は、フォールトトレラント量子計算の理論における基本的な結果である。
振幅雑音を伴う耐故障性量子計算の最大長に対する指数的上限を証明した。
論文 参考訳(メタデータ) (2022-01-31T22:19:49Z) - Random Subgraph Detection Using Queries [45.55323995672117]
植込み高密度部分グラフ検出問題は、与えられた(ランダム)グラフに異常に密度の高い部分グラフが存在するかどうかをテストするタスクを指す。
任意の(おそらくランダム化される)アルゴリズムは、$mathsfQ = Omega(fracn2k2chi4(p||q)log2n)$アダプティブクエリを生成する必要がある。
我々は、$mathsfQ = O(fracn3) とすることで、高い確率で植込み部分グラフを検出する準多項式時間アルゴリズムを提案する。
論文 参考訳(メタデータ) (2021-10-02T07:41:17Z) - Spatial Search on Johnson Graphs by Continuous-Time Quantum Walk [0.0]
連続時間量子ウォークによるジョンソングラフ上の空間探索は、固定径毎に1ドル程度の成功確率を持つ下界の$pisqrtN/2$を達成することを示す。
この証明は数学的に厳密であり、他のグラフクラスにも利用できる。
論文 参考訳(メタデータ) (2021-08-04T12:16:24Z) - Continuous-time quantum walks in the presence of a quadratic
perturbation [55.41644538483948]
連続時間量子ウォークの特性を、$mathcalH=L + lambda L2$という形のハミルトン群で解決する。
低/高接続性および/または対称性を持つパラダイムモデルであるため、サイクル、完全、およびスターグラフを考える。
論文 参考訳(メタデータ) (2020-05-13T14:53:36Z) - Can graph properties have exponential quantum speedup? [5.101801159418223]
特に、(部分)グラフの性質に対して指数的スピードアップが可能かどうかを問うのは自然である。
この疑問に対する答えは入力モデルに強く依存していることを示す。
論文 参考訳(メタデータ) (2020-01-28T18:45:48Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。