論文の概要: Quantum Search on Bipartite Multigraphs
- arxiv url: http://arxiv.org/abs/2504.12586v1
- Date: Thu, 17 Apr 2025 02:05:16 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-04-18 14:35:34.016835
- Title: Quantum Search on Bipartite Multigraphs
- Title（参考訳）: バイパルタイト多グラフの量子探索
- Authors: Gustavo Alves Bezerra, Andris Ambainis, Renato Portugal,
- Abstract要約: 量子ウォークは、量子コンピューティングにおいてアルゴリズム的なスピードアップを達成するための強力なフレームワークを提供する。
本稿では,二部グラフの一般化である2-テセルブルグラフの量子探索アルゴリズムを提案する。
提案手法は,既存の量子ウォーク手法を一般化し,必要なクエリ数を2次的に高速化する。
- 参考スコア（独自算出の注目度）: 0.40964539027092906
- License:
- Abstract: Quantum walks provide a powerful framework for achieving algorithmic speedup in quantum computing. This paper presents a quantum search algorithm for 2-tessellable graphs, a generalization of bipartite graphs, achieving a quadratic speedup over classical Markov chain-based search methods. Our approach employs an adapted version of the Szegedy quantum walk model (adapted SzQW), which takes place on bipartite graphs, and an adapted version of Staggered Quantum Walks (Adapted StQW), which takes place on 2-tessellable graphs, with the goal of efficiently finding a marked vertex by querying an oracle. The Ambainis, Gily\'en, Jeffery, and Kokainis' algorithm (AGJK), which provides a quadratic speedup on balanced bipartite graphs, is used as a subroutine in our algorithm. Our approach generalizes existing quantum walk techniques and offers a quadratic speedup in the number of queries needed, demonstrating the utility of our adapted quantum walk models in a broader class of graphs.
- Abstract（参考訳）: 量子ウォークは、量子コンピューティングにおいてアルゴリズム的なスピードアップを達成するための強力なフレームワークを提供する。
本稿では,従来のマルコフ連鎖探索法よりも2段階の高速化を実現した2次元グラフの量子探索アルゴリズムを提案する。
提案手法では,二部グラフ上で発生するSzegedy量子ウォークモデル(適応SzQW)の適応バージョンと,2次元グラフ上で発生するStaggered Quantum Walks(適応StQW)の適応バージョンを用いて,オラクルをクエリすることでマークされた頂点を効率的に見つけることを目標としている。
Ambainis, Gily\'en, Jeffery, and Kokainis' algorithm (AGJK) はバランスの取れた二部グラフ上の二次的なスピードアップを提供するアルゴリズムであり、我々のアルゴリズムではサブルーチンとして使われている。
提案手法は,既存の量子ウォーク手法を一般化し,必要なクエリ数を2次的に高速化する。
関連論文リスト
- Quantum Search with the Signless Laplacian [0.0]
我々は、層状反強磁性材料で生じる可能性のある無サインラプラシアンを探索する。
いくつかのパラメータについて、ラプラシアンは3つのうち最速の探索アルゴリズムを出力し、より高速な量子アルゴリズムを開発するための新しいツールになり得ることを示唆している。
論文 参考訳（メタデータ） (2025-01-28T18:18:01Z) - Quantum Walk Search on Complete Multipartite Graph with Multiple Marked Vertices [7.922488341886121]
本稿では,完全多部グラフ上での量子ウォーク探索アルゴリズムについて検討する。
我々は、量子ウォークモデルを用いて、二次的なスピードアップを実現する。
また、量子アルゴリズムの数値シミュレーションと回路実装も提供する。
論文 参考訳（メタデータ） (2024-10-07T11:13:41Z) - Quantum Subroutine for Variance Estimation: Algorithmic Design and Applications [80.04533958880862]
量子コンピューティングは、アルゴリズムを設計する新しい方法の基礎となる。
どの場の量子スピードアップが達成できるかという新たな課題が生じる。
量子サブルーチンの設計は、従来のサブルーチンよりも効率的で、新しい強力な量子アルゴリズムに固い柱を向ける。
論文 参考訳（メタデータ） (2024-02-26T09:32:07Z) - Universal approach to deterministic spatial search via alternating
quantum walks [2.940962519388297]
本稿では,量子ウォークを交互に組み合わせることで,様々なグラフ上で決定論的量子探索アルゴリズムを設計するための新しいアプローチを提案する。
我々のアプローチは、異なるグラフに対してインスタンス固有の分析を必要としないため、普遍的である。
論文 参考訳（メタデータ） (2023-07-30T05:14:19Z) - Implementation of Continuous-Time Quantum Walks on Quantum Computers [0.0]
量子ウォークは、量子コンピュータ上で実装される興味深い候補である。
3つのグラフクラス上で連続時間量子ウォークに基づく探索アルゴリズムの進化演算子を実装する効率的な回路について述べる。
論文 参考訳（メタデータ） (2022-12-17T14:59:21Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。
我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。
絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
論文 参考訳（メタデータ） (2022-05-26T20:32:36Z) - From Quantum Graph Computing to Quantum Graph Learning: A Survey [86.8206129053725]
まず、量子力学とグラフ理論の相関関係について、量子コンピュータが有用な解を生成できることを示す。
本稿では,その実践性と適用性について,一般的なグラフ学習手法について概説する。
今後の研究の触媒として期待される量子グラフ学習のスナップショットを提供する。
論文 参考訳（メタデータ） (2022-02-19T02:56:47Z) - Benchmarking Small-Scale Quantum Devices on Computing Graph Edit
Distance [52.77024349608834]
グラフ編集距離(GED: Graph Edit Distance)は、2つのグラフ間の(異なる)相似性の度合いを測定する。
本稿では、GED計算における2つの量子アプローチの比較研究について述べる。
論文 参考訳（メタデータ） (2021-11-19T12:35:26Z) - 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) - Quantum walk-based search algorithms with multiple marked vertices [0.0]
量子ウォークは量子アルゴリズムを開発するための強力なツールである。
我々は、Szegedyの量子ウォークに基づく従来の解析手法を拡張した。
2次元格子とハイパーキューブ上の量子ウォークに基づく2つの例は、我々の方法の詳細を示している。
論文 参考訳（メタデータ） (2021-03-23T22:57:07Z) - Quantum walk processes in quantum devices [55.41644538483948]
グラフ上の量子ウォークを量子回路として表現する方法を研究する。
提案手法は,量子ウォークアルゴリズムを量子コンピュータ上で効率的に実装する方法である。
論文 参考訳（メタデータ） (2020-12-28T18:04:16Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。