論文の概要: Multi-target quantum walk search on Johnson graph
- arxiv url: http://arxiv.org/abs/2510.04424v1
- Date: Mon, 06 Oct 2025 01:29:05 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-10-07 16:52:59.64186
- Title: Multi-target quantum walk search on Johnson graph
- Title（参考訳）: ジョンソングラフ上のマルチターゲット量子ウォーク探索
- Authors: Pulak Ranjan Giri,
- Abstract要約: 非常に高い確率でジョンソングラフ上の複数の目標頂点を探索できるのは$mathcalC_g$コインだけです。
また,$mathcalC_g$のコイン演算子の性能に関する数値解析から,$mathcalC_g$のコイン演算子だけが高い確率で複数のターゲット頂点を探索できることを示す。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: The discrete-time quantum walk on the Johnson graph $J(n,k)$ is a useful tool for performing target vertex searches with high success probability. This graph is defined by $n$ distinct elements, with vertices being all the \(\binom{n}{k}\) $k$-element subsets and two vertices are connected by an edge if they differ exactly by one element. However, most works in the literature focus solely on the search for a single target vertex on the Johnson graph. In this article, we utilize lackadaisical quantum walk--a form of discrete-time coined quantum walk with a wighted self-loop at each vertex of the graph--along with our recently proposed modified coin operator, $\mathcal{C}_g$, to find multiple target vertices on the Johnson graph $J(n,k)$ for various values of $k$. Additionally, a comparison based on the numerical analysis of the performance of the $\mathcal{C}_g$ coin operator in searching for multiple target vertices on the Johnson graph, against various other frequently used coin operators by the discrete-time quantum walk search algorithms, shows that only $\mathcal{C}_g$ coin can search for multiple target vertices with a very high success probability in all the scenarios discussed in this article, outperforming other widely used coin operators in the literature.
- Abstract（参考訳）: Johnson グラフ $J(n,k)$ 上の離散時間量子ウォークは、高い成功確率でターゲット頂点探索を行うのに有用なツールである。
このグラフは$n$異なる元で定義され、頂点はすべての \(\binom{n}{k}\) $k$-要素部分集合であり、2つの頂点は1つの元によって正確に異なる場合、エッジで連結される。
しかし、文献におけるほとんどの研究は、ジョンソングラフ上の単一のターゲット頂点の探索にのみ焦点をあてている。
本稿では、このグラフの各頂点に弱自己ループを持つ離散時間量子ウォークの形式である不連続量子ウォークを用い、最近提案した修正コイン演算子 $\mathcal{C}_g$ とともに、ジョンソングラフ $J(n,k)$ の様々な値に対して複数の目標頂点を求める。
さらに、離散時間量子ウォークサーチアルゴリズムにより、ジョンソングラフ上の複数の目標頂点を探索する$\mathcal{C}_g$のコイン演算子の性能の数値解析に基づいて、$\mathcal{C}_g$のコイン演算子だけが、この論文で議論された全てのシナリオにおいて非常に高い確率で複数の目標頂点を探索し、他の広く使われているコイン演算子よりも優れていることを示す。
関連論文リスト
- Spectral Gaps with Quantum Counting Queries and Oblivious State Preparation [47.600794349481966]
本研究では、量子ビットの対数数を用いて、加算誤差$epsilonDelta_k$まで値を近似する量子アルゴリズムを提案する。
この分析における重要な技術的ステップは、適切なランダム初期状態の準備であり、最終的には閾値よりも小さい固有値の数を効率的に数えることができる。
論文 参考訳（メタデータ） (2025-08-28T17:04:18Z) - Quantum walk search by Grover search on coin space [0.0]
ラカダシカル量子ウォークは、追加の振幅増幅技術の助けなしに、グラフ上のターゲット頂点を探索することができる。
本稿では,不必要な量子ウォーク探索のための修正コインを提案する。
論文 参考訳（メタデータ） (2025-03-06T02:30:37Z) - Quantum walk search on a two-dimensional grid with extra edges [0.0]
量子ウォークは、データベースの要素として識別された頂点を持つグラフ上のターゲットの探索に成功している。
我々は,長距離エッジを持つ2次元周期格子上の量子探索において,一定の成功確率を持つ$mathcalO(sqrtN/M)$の最適時間複雑性が達成可能であることを示す。
論文 参考訳（メタデータ） (2025-03-06T02:11:02Z) - Online Learning with Adversaries: A Differential-Inclusion Analysis [52.43460995467893]
我々は,完全に非同期なオンラインフェデレート学習のための観察行列ベースのフレームワークを提案する。
我々の主な結果は、提案アルゴリズムがほぼ確実に所望の平均$mu.$に収束することである。
新たな差分包摂型2時間スケール解析を用いて,この収束を導出する。
論文 参考訳（メタデータ） (2023-04-04T04:32:29Z) - Collaborative likelihood-ratio estimation over graphs [55.98760097296213]
グラフに基づく相対的制約のない最小二乗重要度フィッティング(GRULSIF)
我々はこの考え方を、グラフベースの相対的非制約最小二乗重要度フィッティング(GRULSIF)と呼ばれる具体的な非パラメトリック手法で開発する。
我々は、ノード当たりの観測回数、グラフのサイズ、およびグラフ構造がタスク間の類似性をどの程度正確にエンコードしているかといった変数が果たす役割を強調する、協調的なアプローチの収束率を導出する。
論文 参考訳（メタデータ） (2022-05-28T15:37:03Z) - Spatial Search on Johnson Graphs by Discrete-Time Quantum Walk [0.0]
本稿では、ジョンソングラフ上の空間探索問題に量子ウォークモデルを用いて対処する。
すべての固定径に対して、成功確率は、$pisqrt N/(2sqrt 2)$ steps を取った後に1/2$である。
すべての固定径に対して、成功確率は$pisqrt N/ (2sqrt)$ ステップを踏んだ後に1/2$であることを示した。
論文 参考訳（メタデータ） (2021-12-07T15:00:07Z) - Random Subgraph Detection Using Queries [29.192695995340653]
植込み高密度部分グラフ検出問題は、与えられた(ランダム)グラフに異常に密度の高い部分グラフが存在するかどうかをテストするタスクを指す。
本稿では,適応的なエッジクエリを用いてグラフの比較的小さな部分のみを観測できる,上記の問題の自然な変形について考察する。
このモデルでは,植込み部分グラフの存在を検出するのに必要なクエリ数と十分なクエリ数(準多項式最適アルゴリズムを伴う)を決定する。
論文 参考訳（メタデータ） (2021-10-02T07:41:17Z) - Lackadaisical quantum walk in the hypercube to search for multiple
marked vertices [0.0]
本稿では,自己ループを用いたハイパーキューブにおける量子ウォーキングに関するいくつかの問題を実験的に解決する。
隣人がマークされている場合、成功の確率は1ドル近くになる。
論文 参考訳（メタデータ） (2021-08-20T23:19:55Z) - Spatial Search on Johnson Graphs by Continuous-Time Quantum Walk [0.0]
連続時間量子ウォークによるジョンソングラフ上の空間探索は、固定径毎に1ドル程度の成功確率を持つ下界の$pisqrtN/2$を達成することを示す。
この証明は数学的に厳密であり、他のグラフクラスにも利用できる。
論文 参考訳（メタデータ） (2021-08-04T12:16:24Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。