論文の概要: On Applying the Lackadaisical Quantum Walk Algorithm to Search for
Multiple Solutions on Grids
- arxiv url: http://arxiv.org/abs/2106.06274v2
- Date: Mon, 9 Jan 2023 22:19:49 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-26 23:52:13.289809
- Title: On Applying the Lackadaisical Quantum Walk Algorithm to Search for
Multiple Solutions on Grids
- Title（参考訳）: 格子上の複数解探索へのラカダシカル量子ウォークアルゴリズムの適用について
- Authors: Jonathan H. A. de Carvalho, Luciano S. de Souza, Fernando M. de Paula
Neto, Tiago A. E. Ferreira
- Abstract要約: 不足量子ウォーク(英: lackadaisical quantum walk)は、頂点が重量$l$の自己ループを持つグラフ構造を探索するために開発されたアルゴリズムである。
本稿では,グリッド上の複数解の探索に不連続な量子ウォークを適用した際の問題に対処する。
- 参考スコア（独自算出の注目度）: 63.75363908696257
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Quantum computing promises to improve the information processing power to
levels unreachable by classical computation. Quantum walks are heading the
development of quantum algorithms for searching information on graphs more
efficiently than their classical counterparts. A quantum-walk-based algorithm
standing out in the literature is the lackadaisical quantum walk. The
lackadaisical quantum walk is an algorithm developed to search graph structures
whose vertices have a self-loop of weight $l$. This paper addresses several
issues related to applying the lackadaisical quantum walk to search for
multiple solutions on grids successfully. Firstly, we show that only one of the
two stopping conditions found in the literature is suitable for simulations. We
also demonstrate that the final success probability depends on both the space
density of solutions and the relative distance between solutions. Furthermore,
this work generalizes the lackadaisical quantum walk to search for multiple
solutions on grids of arbitrary dimensions. In addition, we propose an optimal
adjustment of the self-loop weight $l$ for such $d$-dimensional grids. It turns
out other fits of $l$ found in the literature are particular cases. Finally, we
observe a two-to-one relation between the steps of the lackadaisical quantum
walk and Grover's algorithm, which requires modifications in the stopping
condition. In conclusion, this work deals with practical issues one should
consider when applying the lackadaisical quantum walk, besides expanding the
technique to a broader range of search problems.
- Abstract（参考訳）: 量子コンピューティングは、古典的な計算では到達できないレベルまで情報処理能力を改善することを約束する。
量子ウォークは、従来のものよりも効率的にグラフ上の情報を探す量子アルゴリズムの開発に向かっている。
文献で目立つ量子ウォークに基づくアルゴリズムは、不十分な量子ウォークである。
不足量子ウォーク(英: lackadaisical quantum walk)は、頂点が重量$l$の自己ループを持つグラフ構造を探索するために開発されたアルゴリズムである。
本稿では,グリッド上の複数解の探索に不連続な量子ウォークを適用した際の問題に対処する。
まず,文献中の2つの停止条件のうち,1つだけがシミュレーションに適していることを示す。
また,最終的な成功確率は解の空間密度と解間の相対距離の両方に依存することを示した。
さらに、この研究は、任意の次元の格子上の複数の解を探すために、不足量子ウォークを一般化する。
さらに,そのような$d$次元格子に対する自己ループ重み$l$の最適調整を提案する。
文献にある他の$l$のフィットは、特定のケースであることがわかった。
最後に、不連続な量子ウォークのステップとGroverのアルゴリズムの2対1の関係を観察し、停止条件の変更を必要とする。
結論として,本研究は,不十分な量子ウォークを適用する際に考慮すべき実用的課題に対処し,その手法をより広い範囲の探索問題に拡張する。
関連論文リスト
- Discretized Quantum Exhaustive Search for Variational Quantum Algorithms [0.0]
現在利用可能な量子デバイスは、限られた量子ビットと高いレベルのノイズしか持たず、それらのデバイスで正確に解決できる問題のサイズを制限している。
我々は、変分量子アルゴリズム -- 離散化量子排他探索 -- を改善する新しい方法を提案する。
論文 参考訳（メタデータ） (2024-07-24T22:06:05Z) - Solving The Travelling Salesman Problem Using A Single Qubit [0.0]
トラベルセールスマン問題(TSP)はNP-ハード組合せ最適化問題として人気がある。
本稿では,量子並列性(quantum parallelism)の原理を導出し,単一量子ビットを用いて任意のTSPを解くアルゴリズムを提案する。
我々のアルゴリズムの基盤となるフレームワークは、古典的ブラキストクロンのアプローチの量子バージョンである。
論文 参考訳（メタデータ） (2024-07-24T12:06:37Z) - A Quantum Algorithm Based Heuristic to Hide Sensitive Itemsets [1.8419202109872088]
データ共有の文脈において、よく研究された問題を解決するための量子的アプローチを提案する。
本稿では, 量子アルゴリズムを用いて, この問題の解決方法を示すために, 小型データセットを用いた実験を行った。
論文 参考訳（メタデータ） (2024-02-12T20:44:46Z) - Quantum algorithms: A survey of applications and end-to-end complexities [90.05272647148196]
期待されている量子コンピュータの応用は、科学と産業にまたがる。
本稿では,量子アルゴリズムの応用分野について検討する。
私たちは、各領域における課題と機会を"エンドツーエンド"な方法で概説します。
論文 参考訳（メタデータ） (2023-10-04T17:53:55Z) - Making the cut: two methods for breaking down a quantum algorithm [0.0]
現在、ノイズの多い小規模量子ハードウェアの時代において、計算上の優位性に達する可能性のある量子アルゴリズムを見つけることは、依然として大きな課題である。
我々は、量子アルゴリズムを低い(クエリ)深さのラウンドに分解する2つの方法を特定し、特徴付ける。
最初の問題では並列化が最高のパフォーマンスを提供するのに対し、2番目はより良い選択であることを示す。
論文 参考訳（メタデータ） (2023-05-17T18:00:06Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳（メタデータ） (2022-12-06T22:01:49Z) - Complexity-Theoretic Limitations on Quantum Algorithms for Topological
Data Analysis [59.545114016224254]
トポロジカルデータ解析のための量子アルゴリズムは、古典的手法よりも指数関数的に有利である。
我々は、量子コンピュータにおいても、TDA(ベッチ数の推定)の中心的なタスクが難解であることを示します。
我々は、入力データが単純さの仕様として与えられると、指数的量子優位性を取り戻すことができると論じる。
論文 参考訳（メタデータ） (2022-09-28T17:53:25Z) - Benchmarking Small-Scale Quantum Devices on Computing Graph Edit
Distance [52.77024349608834]
グラフ編集距離(GED: Graph Edit Distance)は、2つのグラフ間の(異なる)相似性の度合いを測定する。
本稿では、GED計算における2つの量子アプローチの比較研究について述べる。
論文 参考訳（メタデータ） (2021-11-19T12:35:26Z) - Robust Quantum Walk Search Without Knowing the Number of Marked Vertices [0.2320417845168326]
既存の量子ウォークに基づく探索アルゴリズムは、サッフル問題に悩まされている。
量子スピードアップを犠牲にすることなくロバスト性を実現する新しい量子ウォークベースの探索フレームワークを提案する。
論文 参考訳（メタデータ） (2021-11-17T10:04:44Z) - Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
3次元形状と画像のマッチング問題は、NPハードな置換行列制約を持つ二次代入問題(QAP)としてしばしば定式化される。
本稿では,量子ハードウェア上での効率的な実行に適した制約のない問題として,いくつかのQAPの再構成を提案する。
提案アルゴリズムは、将来の量子コンピューティングアーキテクチャにおいて、より高次元にスケールする可能性がある。
論文 参考訳（メタデータ） (2021-07-08T17:59:55Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。