論文の概要: Treasure Hunt in Anonymous Graphs with Quantum Pebbles by Oblivious Agents
- arxiv url: http://arxiv.org/abs/2509.02909v1
- Date: Wed, 03 Sep 2025 00:32:17 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-09-04 21:40:46.371607
- Title: Treasure Hunt in Anonymous Graphs with Quantum Pebbles by Oblivious Agents
- Title（参考訳）: 希少エージェントによる匿名グラフと量子Pebbleの宝探し
- Authors: Gaurav Gaur, Barun Gorain, Rishi Ranjan Singh, Daya Gaur,
- Abstract要約: 匿名グラフでは、エッジはポート番号で局所的にラベル付けされる。
エージェントは通常、彼らの探索を導くために、神託によって置かれた定型的な古典的な小石に頼っている。
匿名グラフの探索に量子小石を用いる方法を提案する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We investigate the problem of finding a static treasure in anonymous graphs using oblivious agents and introduce a novel approach that leverages quantum information. In anonymous graphs, vertices are unlabelled, indistinguishable, and edges are locally labelled with port numbers. Agents typically rely on stationary classical pebbles placed by an oracle to guide their search. However, this classical approach is constrained by limited information transmission and high traversal complexity. Classical pebbles are not sufficient for search if the agents are oblivious. We propose the first use of quantum pebbles for search in anonymous graphs. Quantum pebbles periodically emit qubits in a fixed quantum state. Each pebble encodes the port number to the next node using a unique quantum state. The agent determines the correct path by performing measurements in multiple bases, exploiting the probabilistic nature of quantum measurement to distinguish states. We show that this strategy enables an oblivious agent to locate the treasure in $D$ steps using $D$ quantum pebbles, where $D$ is the length of the shortest path between the starting point and the treasure. Moreover, only $O((\log D + \log \Delta)/(\log 1/\delta))$ measurements per node are required to ensure high success probability in a graph with maximum degree $\Delta$ where $\delta = \cos^2(\frac{\pi}{2\Delta})$. We propose the use of quantum information as a guidance mechanism in anonymous graph search. We demonstrate that quantum pebbles can not only emulate the functionality of classical pebbles but can do so with improved efficiency, offering a promising direction for future quantum-enhanced distributed algorithms.
- Abstract（参考訳）: 暗黙のエージェントを用いて匿名グラフに静的な宝物を見つけるという問題を調査し、量子情報を活用する新しいアプローチを導入する。
匿名グラフでは、頂点は階層化されず、識別不能であり、エッジはポート番号で局所的にラベル付けされる。
エージェントは通常、彼らの探索を導くために、神託によって置かれた定型的な古典的な小石に頼っている。
しかし、この古典的なアプローチは、限られた情報伝達と高いトラバースの複雑さによって制約されている。
古典的な小石は、エージェントが隠蔽されている場合、検索には不十分である。
匿名グラフの探索に量子小石を用いる方法を提案する。
量子小石は周期的に量子状態の量子ビットを放出する。
各小石は、ユニークな量子状態を用いてポート番号を次のノードに符号化する。
エージェントは、複数のベースで測定を行い、量子測定の確率的性質を利用して状態を区別することで正しい経路を決定する。
この戦略により、暗黙のエージェントが、開始点と宝物の間の最短経路の長さである$D$量子小石を用いて、$D$のステップで宝物を見つけることができることを示す。
さらに、$O(((\log D + \log \Delta)/(\log 1/\delta))$測定しか必要とせず、最大等級が$\Delta$であるグラフにおいて高い成功確率を確保する必要がある。
匿名グラフ探索における誘導機構として量子情報を用いる手法を提案する。
量子小石は古典的な小石の機能をエミュレートできるだけでなく、効率を向上し、将来の量子強化分散アルゴリズムに有望な方向性を提供する。
関連論文リスト
- High-dimensional graphs convolution for quantum walks photonic applications [41.94295877935867]
量子ウォークダイナミクスを保存する格子とハイパーサイクルの畳み込みの新しい手法を提案する。
我々の発見は、量子ウォークシミュレーションを量子デバイス上で使用するアルゴリズムに必要な膨大な量子ビットを節約するのに有用かもしれない。
論文 参考訳（メタデータ） (2025-07-21T18:28:34Z) - On the practicality of quantum sieving algorithms for the shortest vector problem [42.70026220176376]
格子ベースの暗号は、量子後暗号の主要な候補の1つである。
量子攻撃に対する暗号セキュリティは、最短ベクトル問題(SVP)のような格子問題に基づいている
SVPを解くための漸近的な量子スピードアップはGroverの探索に依存している。
論文 参考訳（メタデータ） (2024-10-17T16:54:41Z) - Generalized Hybrid Search and Applications to Blockchain and Hash
Function Security [50.16790546184646]
まず,ハイブリッド量子古典戦略を用いて,様々な探索問題を解くことの難しさについて検討する。
次に、ハイブリッド量子古典探索アルゴリズムを構築し、その成功確率を解析する。
論文 参考訳（メタデータ） (2023-11-07T04:59:02Z) - Tuning for Quantum Speedup in Directed Lackadaisical Quantum Walks [0.0]
量子ウォークは、量子アルゴリズムと情報処理タスクを設計するための重要なツールである。
歩行不足の場合、歩行者は何らかの確率で同じノードに留まることができる。
驚くべきことに、大きな$l$に対して量子的に誘導される大きなスピードアップが実現される。
論文 参考訳（メタデータ） (2022-11-11T12:38:11Z) - Improvement of quantum walk-based search algorithms in single marked
vertex graphs [0.0]
増幅増幅は通常、成功確率を増幅するために使用されるが、サッフル問題は続く。
本研究では,探索アルゴリズムの成功確率の向上とソッフル問題回避を両立できる一般化補間量子ウォークを定義する。
論文 参考訳（メタデータ） (2022-09-09T07:43:46Z) - Discrete Quantum Walks on the Symmetric Group [0.0]
量子ウォークでは、伝播は量子力学的規則によって制御され、ランダムウォークを量子状態へ一般化する。
本稿では,非可換フーリエ解析によるツールを用いた離散時間生成量子ウォーク(DTCQW)モデルについて検討する。
具体的には、対称群(sym$)が生成するケイリーグラフ上の DTCQW を適切な生成集合で特徴づけることに興味がある。
論文 参考訳（メタデータ） (2022-03-28T23:48:08Z) - Quadratic speedup for spatial search by continuous-time quantum walk [0.0]
連続時間量子ウォークは、空間探索として知られるグラフ内のマークされたノードの集合の中のノードを見つけるという根本的な問題に取り組むためのフレームワークを提供する。
連続時間量子ウォーク探索アルゴリズムでは,任意のノード数を持つグラフにおいて,従来のランダムウォークよりも2次的に高速なマークノードを見つけることができる。
論文 参考訳（メタデータ） (2021-12-23T17:57:49Z) - 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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。