論文の概要: On the optimality of spatial search by continuous-time quantum walk
- arxiv url: http://arxiv.org/abs/2004.12686v1
- Date: Mon, 27 Apr 2020 10:05:55 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-22 00:21:33.625202
- Title: On the optimality of spatial search by continuous-time quantum walk
- Title（参考訳）: 連続時間量子ウォークによる空間探索の最適性について
- Authors: Shantanav Chakraborty, Leonardo Novo, J\'er\'emie Roland
- Abstract要約: 我々は、この量子探索アルゴリズムの性能を予測するハミルトン運動のスペクトル特性に依存する一般表現を導出する。
例えば、スペクトルギャップが$n-1/2$よりもかなり大きいハミルトニアンの予測は有効である。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: One of the most important algorithmic applications of quantum walks is to
solve spatial search problems. A widely used quantum algorithm for this
problem, introduced by Childs and Goldstone [Phys. Rev. A 70, 022314 (2004)],
finds a marked node on a graph of $n$ nodes via a continuous-time quantum walk.
This algorithm is said to be optimal if it can find any of the nodes in
$O(\sqrt{n})$ time. However, given a graph, no general conditions for the
optimality of the algorithm are known and previous works demonstrating optimal
quantum search for certain graphs required an instance-specific analysis. In
fact, the demonstration of necessary and sufficient conditions a graph must
fulfill for quantum search to be optimal has been a long-standing open problem.
In this work, we make significant progress towards solving this problem. We
derive general expressions, depending on the spectral properties of the
Hamiltonian driving the walk, that predict the performance of this quantum
search algorithm provided certain spectral conditions are fulfilled. Our
predictions are valid, for example, for (normalized) Hamiltonians whose
spectral gap is considerably larger than $n^{-1/2}$. This allows us to derive
necessary and sufficient conditions for optimal quantum search in this regime,
as well as provide new examples of graphs where quantum search is sub-optimal.
In addition, by extending this analysis, we are also able to show the
optimality of quantum search for certain graphs with very small spectral gaps,
such as graphs that can be efficiently partitioned into clusters. Our results
imply that, to the best of our knowledge, all prior results analytically
demonstrating the optimality of this algorithm for specific graphs can be
recovered from our general results.
- Abstract（参考訳）: 量子ウォークの最も重要なアルゴリズム応用の1つは、空間探索問題を解くことである。
childs and goldstone [phys. rev. a 70, 022314 (2004)]によって紹介されたこの問題に対する広く使われている量子アルゴリズムは、連続時間量子ウォークによってn$ノードのグラフ上にマークされたノードを見つける。
このアルゴリズムは、任意のノードを$o(\sqrt{n})$ timeで見つけることができる場合に最適であると言われている。
しかし、グラフが与えられたとき、アルゴリズムの最適性に関する一般的な条件は知られておらず、あるグラフに対する最適な量子探索を示す以前の研究は、インスタンス固有の分析を必要とした。
実際、グラフが最適な量子探索のために満たさなければならない必要十分条件の実証は、長年の未解決問題であった。
本研究では,この問題の解決に向けて大きな進歩を遂げる。
我々は、特定のスペクトル条件が満たされれば、この量子探索アルゴリズムの性能を予測するハミルトニアン駆動のスペクトル特性に依存する一般表現を導出する。
例えば、スペクトルギャップが$n^{-1/2}$よりもかなり大きい(正規化された)ハミルトニアンの予測は有効である。
これにより、この状態における最適量子探索に必要な十分条件を導出することができ、また、量子探索が準最適であるグラフの新しい例を提供することができる。
さらに,この解析を拡張することにより,クラスタに効率的に分割可能なグラフなど,非常に小さなスペクトルギャップを持つあるグラフに対する量子探索の最適性を示すことができる。
以上の結果から,本アルゴリズムのグラフに対する最適性を解析的に証明したすべての先行結果が,我々の一般的な結果から回収できることが示唆された。
関連論文リスト
- Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている
SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。
この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
論文 参考訳（メタデータ） (2024-08-14T19:04:13Z) - Quantum Algorithm for Testing Graph Completeness [0.0]
グラフ完全性をテストすることは、コンピュータ科学とネットワーク理論において重要な問題である。
Szegedy量子ウォークと量子位相推定(QPE)を用いた効率的なアルゴリズムを提案する。
このアプローチは、ネットワーク構造解析、古典的なルーティングアルゴリズムの評価、ペア比較に基づくシステム評価に有用である。
論文 参考訳（メタデータ） (2024-07-29T14:56:25Z) - An Analysis of Quantum Annealing Algorithms for Solving the Maximum Clique Problem [49.1574468325115]
我々は、QUBO問題として表されるグラフ上の最大傾きを見つける量子D波アンナーの能力を解析する。
本稿では, 相補的な最大独立集合問題に対する分解アルゴリズムと, ノード数, 傾き数, 密度, 接続率, 解サイズの他のノード数に対する比を制御するグラフ生成アルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-06-11T04:40:05Z) - Generalized quantum Arimoto-Blahut algorithm and its application to
quantum information bottleneck [55.22418739014892]
量子アリーモト・ブラフトアルゴリズムをRamakrishnanらにより一般化する。
3つの量子系を持つ量子情報ボトルネックに対して,我々のアルゴリズムを適用した。
数値解析により,我々のアルゴリズムはアルゴリズムよりも優れていることが示された。
論文 参考訳（メタデータ） (2023-11-19T00:06:11Z) - Universal approach to deterministic spatial search via alternating
quantum walks [2.940962519388297]
本稿では,量子ウォークを交互に組み合わせることで,様々なグラフ上で決定論的量子探索アルゴリズムを設計するための新しいアプローチを提案する。
我々のアプローチは、異なるグラフに対してインスタンス固有の分析を必要としないため、普遍的である。
論文 参考訳（メタデータ） (2023-07-30T05:14:19Z) - Quantitative approach to Grover's quantum walk on graphs [62.997667081978825]
グラフ上の連続時間量子ウォークに着目したGroverの探索アルゴリズムについて検討する。
関連する量子ウォークに便利なグラフトポロジーを見つける代わりに、グラフトポロジーを修正し、ラプラシアンを基礎とするグラフを変化させる。
論文 参考訳（メタデータ） (2022-07-04T19:33:06Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。
我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。
絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
論文 参考訳（メタデータ） (2022-05-26T20:32:36Z) - Quantifying Grover speed-ups beyond asymptotic analysis [0.0]
古典的なエミュレーションと、すべての定数を含む詳細な複雑性境界を組み合わせたアプローチを考える。
本手法を古典的アルゴリズムの単純量子スピードアップに適用し,よく研究されたMAX-$k$-SAT最適化問題を解く。
これは、2つの重要な量子サブルーチンの期待と最悪のケースの複雑さに厳密な境界(全定数を含む)を必要とする。
論文 参考訳（メタデータ） (2022-03-09T19:00:00Z) - Quadratic speedup for spatial search by continuous-time quantum walk [0.0]
連続時間量子ウォークは、空間探索として知られるグラフ内のマークされたノードの集合の中のノードを見つけるという根本的な問題に取り組むためのフレームワークを提供する。
連続時間量子ウォーク探索アルゴリズムでは,任意のノード数を持つグラフにおいて,従来のランダムウォークよりも2次的に高速なマークノードを見つけることができる。
論文 参考訳（メタデータ） (2021-12-23T17:57:49Z) - 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) - Transition Probabilities in Generalized Quantum Search Hamiltonian
Evolutions [0.0]
本研究では、連続時間量子探索問題において、ソース状態からターゲット状態への遷移確率を計算するために必要な計算面について検討する。
最小探索時間の観点からは、よく知られたFarhi-Gutmannアナログ量子探索アルゴリズムよりも優れていることが分かる。
論文 参考訳（メタデータ） (2020-02-06T13:16:37Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。