論文の概要: Improvement of quantum walk-based search algorithms in single marked
vertex graphs
- arxiv url: http://arxiv.org/abs/2209.04162v1
- Date: Fri, 9 Sep 2022 07:43:46 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-27 05:28:52.175749
- Title: Improvement of quantum walk-based search algorithms in single marked
vertex graphs
- Title（参考訳）: 単一頂点グラフにおける量子ウォークに基づく探索アルゴリズムの改良
- Authors: Xinying Li, Yun Shang
- Abstract要約: 増幅増幅は通常、成功確率を増幅するために使用されるが、サッフル問題は続く。
本研究では,探索アルゴリズムの成功確率の向上とソッフル問題回避を両立できる一般化補間量子ウォークを定義する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Quantum walks are powerful tools for building quantum search algorithms or
quantum sampling algorithms named the construction of quantum stationary state.
However, the success probability of those algorithms are all far away from 1.
Amplitude amplification is usually used to amplify success probability, but the
souffl\'e problems follow. Only stop at the right step can we achieve a maximum
success probability. Otherwise, as the number of steps increases, the success
probability may decrease, which will cause troubles in practical application of
the algorithm when the optimal number of steps is not known.
In this work, we define generalized interpolated quantum walks, which can
both improve the success probability of search algorithms and avoid the
souffl\'e problems.
Then we combine generalized interpolation quantum walks with quantum
fast-forwarding. The combination both reduce the times of calling walk operator
of searching algorithm from $\Theta((\varepsilon^{-1})\sqrt{\Heg})$ to
$\Theta(\log(\varepsilon^{-1})\sqrt{\Heg})$ and reduces the number of ancilla
qubits required from $\Theta(\log(\varepsilon^{-1})+\log\sqrt{\Heg})$ to
$\Theta(\log\log(\varepsilon^{-1})+\log\sqrt{\Heg})$, and the souffle problem
is avoided while the success probability is improved, where $\varepsilon$
denotes the precision and $\Heg$ denotes the classical hitting time.
Besides, we show that our generalized interpolated quantum walks can be used
to improve the construction of quantum states corresponding to stationary
distributions as well.
Finally, we give an application that can be used to construct a slowly
evolving Markov chain sequence by applying generalized interpolated quantum
walks, which is the necessary premise in adiabatic stationary state
preparation.
- Abstract（参考訳）: 量子ウォーク(quantum walk)は、量子探索アルゴリズムや量子サンプリングアルゴリズムを構築するための強力なツールである。
しかし、これらのアルゴリズムの成功確率は1.1から遠く離れている。
振幅増幅は通常成功確率の増幅に使用されるが、suuffl\'e問題は従う。
正しいステップで停止するだけで、最大成功確率は達成できます。
そうでない場合、ステップ数が増加すると成功確率が減少し、最適なステップ数が分かっていない場合、アルゴリズムの実用的応用にトラブルが生じる。
本研究では,一般化された補間量子ウォークを定義し,探索アルゴリズムの成功確率を改善し,souffl\'e問題を回避する。
次に、一般化補間量子ウォークと量子高速フォワードを組み合わせる。
The combination both reduce the times of calling walk operator of searching algorithm from $\Theta((\varepsilon^{-1})\sqrt{\Heg})$ to $\Theta(\log(\varepsilon^{-1})\sqrt{\Heg})$ and reduces the number of ancilla qubits required from $\Theta(\log(\varepsilon^{-1})+\log\sqrt{\Heg})$ to $\Theta(\log\log(\varepsilon^{-1})+\log\sqrt{\Heg})$, and the souffle problem is avoided while the success probability is improved, where $\varepsilon$ denotes the precision and $\Heg$ denotes the classical hitting time.
さらに,我々の一般化された補間量子ウォークは定常分布に対応する量子状態の構築にも利用できることを示した。
最後に, 一般化された補間量子ウォークを適用することで, 緩やかに進化するマルコフ連鎖配列を構築するのに使用可能なアプリケーションを与える。
関連論文リスト
- On the practicality of quantum sieving algorithms for the shortest vector problem [42.70026220176376]
格子ベースの暗号は、量子後暗号の主要な候補の1つである。
量子攻撃に対する暗号セキュリティは、最短ベクトル問題(SVP)のような格子問題に基づいている
SVPを解くための漸近的な量子スピードアップはGroverの探索に依存している。
論文 参考訳（メタデータ） (2024-10-17T16:54:41Z) - Quantum algorithms for Hopcroft's problem [45.45456673484445]
計算幾何学の基本的な問題であるホップクロフト問題に対する量子アルゴリズムについて検討する。
この問題の古典的な複雑さはよく研究されており、最もよく知られているアルゴリズムは$O(n4/3)の時間で動作する。
我々の結果は、時間複雑性が$widetilde O(n5/6)$の2つの異なる量子アルゴリズムである。
論文 参考訳（メタデータ） (2024-05-02T10:29:06Z) - Quantum Algorithms for Sampling Log-Concave Distributions and Estimating
Normalizing Constants [8.453228628258778]
我々は,対数凹分布をサンプリングし,正規化定数を推定するための量子アルゴリズムを開発した。
我々はモンテカルロ法と量子ウォークの量子アナログを利用する。
また、正規化定数を推定するための1/epsilon1-o(1)$量子下界も証明する。
論文 参考訳（メタデータ） (2022-10-12T19:10:43Z) - Quantum Approximate Counting for Markov Chains and Application to
Collision Counting [0.0]
我々は,ブラザード,ホイヤー,タップ(ICALP 1998)によって開発された量子近似計数法を一般化し,マルコフ連鎖のマーク状態の数を推定する方法を示す。
これにより、Magniez、Nayak、Roland、Santhaによって確立された強力な"量子ウォークベースサーチ"フレームワークに基づいて、量子検索アルゴリズムから量子近似カウントアルゴリズムを構築することができる。
論文 参考訳（メタデータ） (2022-04-06T03:04:42Z) - 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) - 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) - Robust Quantum Walk Search Without Knowing the Number of Marked Vertices [0.2320417845168326]
既存の量子ウォークに基づく探索アルゴリズムは、サッフル問題に悩まされている。
量子スピードアップを犠牲にすることなくロバスト性を実現する新しい量子ウォークベースの探索フレームワークを提案する。
論文 参考訳（メタデータ） (2021-11-17T10:04:44Z) - On Applying the Lackadaisical Quantum Walk Algorithm to Search for
Multiple Solutions on Grids [63.75363908696257]
不足量子ウォーク(英: lackadaisical quantum walk)は、頂点が重量$l$の自己ループを持つグラフ構造を探索するために開発されたアルゴリズムである。
本稿では,グリッド上の複数解の探索に不連続な量子ウォークを適用した際の問題に対処する。
論文 参考訳（メタデータ） (2021-06-11T09:43:09Z) - Efficient Algorithms for Causal Order Discovery in Quantum Networks [44.356294905844834]
入力および出力システムへのブラックボックスアクセスを前提として,最初の効率的な量子因果順序探索アルゴリズムを開発した。
我々は、量子コムを用いて因果順序をモデル化し、我々のアルゴリズムは、与えられたプロセスと互換性のある入力と出力の順序を出力する。
我々のアルゴリズムは、量子通信ネットワークで利用可能な伝送経路を効率的に検出し、最適化する方法を提供する。
論文 参考訳（メタデータ） (2020-12-03T07:12:08Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。