論文の概要: Deterministic quantum search on all Laplacian integral graphs

• arxiv url: http://arxiv.org/abs/2506.21108v1
• Date: Thu, 26 Jun 2025 09:06:08 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-27 19:53:10.034564
• Title: Deterministic quantum search on all Laplacian integral graphs
• Title（参考訳）: すべてのラプラシア積分グラフ上の決定論的量子探索
• Authors: Guanzhong Li, Jingquan Luo, Shiguang Feng, Lvzhou Li,
• Abstract要約: 我々は、決定論的量子探索アルゴリズムを用いて、異なる、エレガントな量子空間探索手法を提案する。 この研究は、決定論的量子探索を可能にする最大のグラフのクラスを発見する。
• 参考スコア（独自算出の注目度）: 0.3124884279860061
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Searching for an unknown marked vertex on a given graph (also known as spatial search) is an extensively discussed topic in the area of quantum algorithms, with a plethora of results based on different quantum walk models and targeting various types of graphs. Most of these algorithms have a non-zero probability of failure. In recent years, there have been some efforts to design quantum spatial search algorithms with $100\%$ success probability. However, these works either only work for very special graphs or only for the case where there is only one marked vertex. In this work, we propose a different and elegant approach to quantum spatial search, obtaining deterministic quantum search algorithms that can find a marked vertex with certainty on any Laplacian integral graph with any predetermined proportion of marked vertices. Thus, this work discovers the largest class of graphs so far that allow deterministic quantum search, making it easy to design deterministic quantum search algorithms for many graphs, including the different graphs discussed in previous works, in a unified framework.
• Abstract（参考訳）: 与えられたグラフ上の未知のマーク付き頂点(空間探索とも呼ばれる)を探索することは、様々な量子ウォークモデルに基づいて様々な種類のグラフを対象とする、量子アルゴリズムの領域で広く議論されているトピックである。 これらのアルゴリズムのほとんどは、ゼロでない確率で失敗する。 近年、量子空間探索アルゴリズムを100\%の確率で設計する試みがいくつか行われている。 しかし、これらの研究は、非常に特別なグラフのためにのみ機能するか、または、マークされた頂点が1つしかない場合にのみ有効である。 本研究では,任意のラプラシア積分グラフ上で有意な頂点を求める決定論的量子探索アルゴリズムを,任意の有意な頂点の所定の割合で求めることができる,異なる,エレガントな量子空間探索手法を提案する。 このように、この研究は、決定論的量子探索を可能にする最大クラスのグラフを発見し、多くのグラフに対して決定論的量子探索アルゴリズムを設計しやすくする。

関連論文リスト

• Unifying quantum spatial search, state transfer and uniform sampling on graphs: simple and exact [2.871419116565751]
  本稿では,量子ウォークの交互化による新しい,簡潔なアルゴリズムフレームワークを提案する。 量子空間探索、状態移動、および大規模なグラフの均一サンプリングを統一する。 このアプローチは、グラフのラプラシア固有値集合の深さにのみ依存する簡潔な形式性を持っているため、簡単に利用できる。
  論文  参考訳（メタデータ） (2024-07-01T06:09:19Z)
• Universal approach to deterministic spatial search via alternating quantum walks [2.940962519388297]
  本稿では,量子ウォークを交互に組み合わせることで,様々なグラフ上で決定論的量子探索アルゴリズムを設計するための新しいアプローチを提案する。 我々のアプローチは、異なるグラフに対してインスタンス固有の分析を必要としないため、普遍的である。
  論文  参考訳（メタデータ） (2023-07-30T05:14:19Z)
• A Theoretical Analysis Of Nearest Neighbor Search On Approximate Near Neighbor Graph [51.880164098926166]
  グラフベースのアルゴリズムは、近隣探索(NN-Search)問題において最先端の性能を示す。 グラフベースのNN-Searchアルゴリズムには実践と理論のギャップがある。 低次元および高密度ベクトルに対する ANN-Graph 上の欲求探索による NN-Search の解法を理論的に保証する。
  論文  参考訳（メタデータ） (2023-03-10T21:18:34Z)
• Quantitative approach to Grover's quantum walk on graphs [62.997667081978825]
  グラフ上の連続時間量子ウォークに着目したGroverの探索アルゴリズムについて検討する。 関連する量子ウォークに便利なグラフトポロジーを見つける代わりに、グラフトポロジーを修正し、ラプラシアンを基礎とするグラフを変化させる。
  論文  参考訳（メタデータ） (2022-07-04T19:33:06Z)
• 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)
• Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
  我々は高密度サブグラフ発見のための新しい学習問題を導入する。 まず,確率の高いほぼ最適解を求めるエッジ時間アルゴリズムを提案する。 そして、理論的保証のあるよりスケーラブルなアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2020-06-24T11:37:33Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。