論文の概要: Unstructured Search by Random and Quantum Walk
- arxiv url: http://arxiv.org/abs/2011.14533v2
- Date: Mon, 18 Oct 2021 15:20:55 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-22 14:54:56.112833
- Title: Unstructured Search by Random and Quantum Walk
- Title（参考訳）: ランダムと量子ウォークによる非構造探索
- Authors: Thomas G. Wong
- Abstract要約: ソートされていない$N$要素のリストのエントリを探すと、古典的なコンピュータのオラクルに$O(N)$クエリーを取るのが有名である。
離散的かつ連続的なランダムウォークと量子ウォークがこの問題をいかに解決するかを導出する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The task of finding an entry in an unsorted list of $N$ elements famously
takes $O(N)$ queries to an oracle for a classical computer and $O(\sqrt{N})$
queries for a quantum computer using Grover's algorithm. Reformulated as a
spatial search problem, this corresponds to searching the complete graph, or
all-to-all network, for a marked vertex by querying an oracle. In this
tutorial, we derive how discrete- and continuous-time (classical) random walks
and quantum walks solve this problem in a thorough and pedagogical manner,
providing an accessible introduction to how random and quantum walks can be
used to search spatial regions. Some of the results are already known, but many
are new. For large $N$, the random walks converge to the same evolution, both
taking $N \ln(1/\epsilon)$ time to reach a success probability of $1-\epsilon$.
In contrast, the discrete-time quantum walk asymptotically takes
$\pi\sqrt{N}/2\sqrt{2}$ timesteps to reach a success probability of $1/2$,
while the continuous-time quantum walk takes $\pi\sqrt{N}/2$ time to reach a
success probability of $1$.
- Abstract（参考訳）: n$要素の未分類リストにあるエントリを見つけるタスクは、古典的なコンピュータのoracleへの$o(n)$クエリとgroverのアルゴリズムを使った量子コンピュータの$o(\sqrt{n})$クエリである。
空間探索問題として再編成されたこの手法は、全グラフ(全対全ネットワーク)をオラクルに問い合わせることで有意な頂点を探索することに対応する。
このチュートリアルでは、離散的および連続的(古典的)ランダムウォークと量子ウォークが、この問題を徹底的かつ教育的な方法でどのように解決するかを導出し、ランダムウォークと量子ウォークが空間領域の探索にどのように利用できるかを説明する。
結果のいくつかはすでに知られているが、新しいものも多い。
大きな$N$の場合、ランダムウォークは同じ進化に収束し、どちらも$N \ln(1/\epsilon)$時間で1-\epsilon$の成功確率に達する。
対照的に、離散時間量子ウォークは漸近的に$\pi\sqrt{n}/2\sqrt{2}$で成功確率は$/2$、連続時間量子ウォークは$\pi\sqrt{n}/2$で成功確率は$$$である。
関連論文リスト
- Quantum spatial search with multiple excitations [0.28675177318965045]
我々は、$n$スピンの$k$-励起部分空間における連続時間量子ウォークが、時間$O(sqrtn)$の忠実さでマークされた$k$のバイナリ文字列を決定することができることを示した。
数値的には、このアルゴリズムは1/ralpha$で崩壊し、$r$はスピン間距離、$alpha$は現在のイオントラップシステムで容易に利用可能である。
論文 参考訳（メタデータ） (2024-10-08T11:53:57Z) - Quantum Speedups for Bayesian Network Structure Learning [0.0]
ノードが$n$のネットワークの場合、最も高速な既知のアルゴリズムは、最悪の場合は$O(cn)$で実行され、20年で改善はない。
近年の量子コンピューティングの発展に触発されて、BNSLが量子スピードアップを認めているかどうかを問う。
我々は、$c leq 1.817$と$c leq 1.982$の2つのアルゴリズムを与える。
論文 参考訳（メタデータ） (2023-05-31T09:15:28Z) - On the average-case complexity of learning output distributions of
quantum circuits [55.37943886895049]
統計的クエリモデルでは,ブロックワークランダムな量子回路の出力分布の学習は平均ケースハードであることが示されている。
この学習モデルは、ほとんどの一般的な学習アルゴリズムの抽象的な計算モデルとして広く利用されている。
論文 参考訳（メタデータ） (2023-05-09T20:53:27Z) - Spacetime-Efficient Low-Depth Quantum State Preparation with
Applications [93.56766264306764]
任意の量子状態を作成するための新しい決定論的手法は、以前の方法よりも少ない量子資源を必要とすることを示す。
我々は、量子機械学習、ハミルトンシミュレーション、方程式の線形系を解くことなど、この能力が役立ついくつかのアプリケーションを強調した。
論文 参考訳（メタデータ） (2023-03-03T18:23:20Z) - Mind the gap: Achieving a super-Grover quantum speedup by jumping to the
end [114.3957763744719]
本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。
このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。
また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
論文 参考訳（メタデータ） (2022-12-03T02:45:23Z) - Improvement of quantum walk-based search algorithms in single marked
vertex graphs [0.0]
増幅増幅は通常、成功確率を増幅するために使用されるが、サッフル問題は続く。
本研究では,探索アルゴリズムの成功確率の向上とソッフル問題回避を両立できる一般化補間量子ウォークを定義する。
論文 参考訳（メタデータ） (2022-09-09T07:43:46Z) - Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。
異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。
我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
論文 参考訳（メタデータ） (2022-06-07T18:00:01Z) - Quadratic speedup for spatial search by continuous-time quantum walk [0.0]
連続時間量子ウォークは、空間探索として知られるグラフ内のマークされたノードの集合の中のノードを見つけるという根本的な問題に取り組むためのフレームワークを提供する。
連続時間量子ウォーク探索アルゴリズムでは,任意のノード数を持つグラフにおいて,従来のランダムウォークよりも2次的に高速なマークノードを見つけることができる。
論文 参考訳（メタデータ） (2021-12-23T17:57:49Z) - Random quantum circuits transform local noise into global white noise [118.18170052022323]
低忠実度状態におけるノイズランダム量子回路の測定結果の分布について検討する。
十分に弱くユニタリな局所雑音に対して、一般的なノイズ回路インスタンスの出力分布$p_textnoisy$間の相関(線形クロスエントロピーベンチマークで測定)は指数関数的に減少する。
ノイズが不整合であれば、出力分布は、正確に同じ速度で均一分布の$p_textunif$に近づく。
論文 参考訳（メタデータ） (2021-11-29T19:26:28Z) - Quantum Time-Space Tradeoff for Finding Multiple Collision Pairs [0.0]
ランダム関数 $f : [N] rightarrow [N]$ の衝突対を量子コンピュータを用いて探索する。
利用可能なメモリのサイズが制限された場合、関数に対するクエリの数は大幅に増加しなければなりません。
論文 参考訳（メタデータ） (2020-02-20T18:48:51Z) - Quantum Coupon Collector [62.58209964224025]
我々は、$k$-要素集合$Ssubseteq[n]$が、その要素の一様重ね合わせ$|Srangleからいかに効率的に学習できるかを研究する。
我々は、$k$と$n$ごとに必要となる量子サンプルの数に厳密な制限を与え、効率的な量子学習アルゴリズムを与える。
論文 参考訳（メタデータ） (2020-02-18T16:14:55Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。