論文の概要: (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のさらなるアイデアを使用している。

関連論文リスト

• Implementation of Continuous-Time Quantum Walk on Sparse Graph [0.0]
  連続時間量子ウォーク(CTQW)は、量子コンピューティングにおいて重要な役割を果たす。 CTQWを効率的に実装する方法は難しい問題である。 本稿では,スパースグラフ上でのCTQWの実装について検討する。
  論文  参考訳（メタデータ） (2024-08-20T05:20:55Z)
• Exponential Quantum Advantage for Pathfinding in Regular Sunflower Graphs [5.173438526554426]
  隣接リストのオラクルによるパスフィンディング問題に対して指数的量子古典的分離を可能にするグラフのクラスを見つける。 通常のヒマワリグラフに$s$-$t$の経路を求めるのに有効な量子アルゴリズムを提供するが、古典的アルゴリズムは指数関数的な時間を要する。
  論文  参考訳（メタデータ） (2024-07-19T15:21:13Z)
• Quantum algorithms for Hopcroft's problem [45.45456673484445]
  計算幾何学の基本的な問題であるホップクロフト問題に対する量子アルゴリズムについて検討する。 この問題の古典的な複雑さはよく研究されており、最もよく知られているアルゴリズムは$O(n4/3)の時間で動作する。 我々の結果は、時間複雑性が$widetilde O(n5/6)$の2つの異なる量子アルゴリズムである。
  論文  参考訳（メタデータ） (2024-05-02T10:29:06Z)
• 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)
• 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 lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
  しきい値定理は、フォールトトレラント量子計算の理論における基本的な結果である。 振幅雑音を伴う耐故障性量子計算の最大長に対する指数的上限を証明した。
  論文  参考訳（メタデータ） (2022-01-31T22:19:49Z)
• 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)

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

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