Multi-target quantum walk search on Johnson graph

• URL: http://arxiv.org/abs/2510.04424v1
• Date: Mon, 06 Oct 2025 01:29:05 GMT
• Title: Multi-target quantum walk search on Johnson graph
• Abstract summary: We show that only $mathcalC_g$ coin can search for multiple target vertices on the Johnson graph with a very high success probability.<n>A comparison based on the numerical analysis of the performance of the $mathcalC_g$ coin operator shows that only $mathcalC_g$ coin can search for multiple target vertices with a very high success probability.
• Score: 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.

Related papers

• Low-rank Updates in Slowly Time-varying Graphs for Spatial-Temporal Signal Interpolation [36.25340747048208]
  A crucial assumption in graph signal processing (GSP) is the existence of an underlying graph that captures the pairwise similarities between nodes.<n>For spatial-temporal data in which node-to-node similarities evolve over time, a static spatial graph is insufficient.<n>We model the graph changes in two consecutive adjacency matrices $P = W(2) - W(1)$ across time as a low-rank matrix.
  arXiv  Detail & Related papers  (2026-06-22T23:33:33Z)
• Efficient Exact Resistance Distance Computation on Small-Treewidth Graphs: a Labelling Approach [37.498311835613045]
  shortest-path distance computation achieves remarkable efficiency on small-treewidth graphs.<n>We propose treeindex, a novel index method that constructs a resistance distance labelling of size $O(n cdot h_mathcalG)$ in $O(n cdot h_mathcalG2 cdot d_max$.<n>Our labelling supports exact single-pair queries in $O(h_mathcalG)$ time and single-source queries in $O(n cdot h_math
  arXiv  Detail & Related papers  (2025-09-05T14:14:36Z)
• Spectral Gaps with Quantum Counting Queries and Oblivious State Preparation [47.600794349481966]
  In this work, we present a quantum algorithm which approximates values up to additive error $epsilonDelta_k$ using a logarithmic number of qubits.<n>A key technical step in the analysis is the preparation of a suitable random initial state, which ultimately allows us to efficiently count the number of eigenvalues that are smaller than a threshold.
  arXiv  Detail & Related papers  (2025-08-28T17:04:18Z)
• Quantum walk search by Grover search on coin space [0.0]
  Lackadaisical quantum walk can search for target vertices on graphs without the help of any additional amplitude amplification technique.<n>We propose a modified coin for the lackadaisical quantum walk search.
  arXiv  Detail & Related papers  (2025-03-06T02:30:37Z)
• Quantum walk search on a two-dimensional grid with extra edges [0.0]
  Quantum walk has been successfully used to search for targets on graphs with vertices identified as elements of a database.<n>We show that the optimal time complexity of $mathcalO(sqrtN/M)$ with constant success probability can be achieved for quantum search on a two-dimensional periodic grid with long-range edges.
  arXiv  Detail & Related papers  (2025-03-06T02:11:02Z)
• Provably Extending PageRank-based Local Clustering Algorithm to Weighted Directed Graphs with Self-Loops and to Hypergraphs [40.215737469808026]
  This work focuses on graph local clustering, which has broad applications beyond graphs because of the internal connectivities within various modalities.<n>We extend the non-approximating Andersen-Chung-Lang ("ACL") algorithm beyond discrete graphs and generalize its quadratic optimality to a wider range of graphs.<n>We theoretically prove that, under two mild conditions, both algorithms can identify a quadratically optimal local cluster in terms of conductance with at least 1/2 probability.
  arXiv  Detail & Related papers  (2024-12-04T03:56:14Z)
• Monogamy of Entanglement Bounds and Improved Approximation Algorithms for Qudit Hamiltonians [37.96754147111215]
  We prove new monogamy of entanglement bounds for two-local qudit Hamiltonians of rank-one projectors without one-local terms.<n>In particular, we certify the ground state energy in terms of the maximum matching of the underlying interaction graph via low-degree sum-of-squares.
  arXiv  Detail & Related papers  (2024-10-21T00:10:51Z)
• Graph Unfolding and Sampling for Transitory Video Summarization via Gershgorin Disc Alignment [48.137527345353625]
  User-generated videos (UGVs) uploaded from mobile phones to social media sites like YouTube and TikTok are short and non-repetitive. We summarize a transitory UGV into several discs in linear time via fast graph sampling based on Gershgorin disc alignment (GDA) We show that our algorithm achieves comparable or better video summarization performance compared to state-of-the-art methods, at a substantially reduced complexity.
  arXiv  Detail & Related papers  (2024-08-03T20:08:02Z)
• Moments, Random Walks, and Limits for Spectrum Approximation [40.43008834125277]
  We show that there are distributions on $[-1,1]$ that cannot be approximated to accuracy $epsilon$ in Wasserstein-1 distance. No algorithm can compute an $epsilon$-accurate approximation to the spectrum of a normalized graph adjacency matrix with constant probability.
  arXiv  Detail & Related papers  (2023-07-02T05:03:38Z)
• Fast Maximum $k$-Plex Algorithms Parameterized by Small Degeneracy Gaps [30.06993761032835]
  The maximum $k$-plex problem is important but computationally challenging in applications such as graph mining and community detection. We present an exact algorithm parameterized by $g_k(G)$, which has the worst-case running time in the size of the input graph and exponential in $g_k(G)$. We further extend our discussion to an even smaller parameter $cg_k(G)$, the gap between the community-degeneracy bound and the size of the maximum $k$-plex.
  arXiv  Detail & Related papers  (2023-06-23T01:28:24Z)
• Online Learning with Adversaries: A Differential-Inclusion Analysis [52.43460995467893]
  We introduce an observation-matrix-based framework for fully asynchronous online Federated Learning with adversaries. Our main result is that the proposed algorithm almost surely converges to the desired mean $mu.$ We derive this convergence using a novel differential-inclusion-based two-timescale analysis.
  arXiv  Detail & Related papers  (2023-04-04T04:32:29Z)
• On the Unlikelihood of D-Separation [69.62839677485087]
  We provide analytic evidence that on large graphs, d-separation is a rare phenomenon, even when guaranteed to exist. For the PC Algorithm, while it is known that its worst-case guarantees fail on non-sparse graphs, we show that the same is true for the average case. For UniformSGS, while it is known that the running time is exponential for existing edges, we show that in the average case, that is the expected running time for most non-existing edges as well.
  arXiv  Detail & Related papers  (2023-03-10T00:11:18Z)
• Improved High-Probability Regret for Adversarial Bandits with Time-Varying Feedback Graphs [62.52390282012508]
  We study high-probability regret bounds for adversarial $K$-armed bandits with time-varying feedback graphs over $T$ rounds. We develop an algorithm that achieves the optimal regret $widetildemathcalO((sum_t=1Talpha_t)1/2+max_tin[T]alpha_t]$ with high probability. We also develop the first algorithm that achieves the optimal high-probability regret bound for weakly observable graphs.
  arXiv  Detail & Related papers  (2022-10-04T04:36:15Z)
• Collaborative likelihood-ratio estimation over graphs [55.98760097296213]
  Graph-based Relative Unconstrained Least-squares Importance Fitting (GRULSIF) We develop this idea in a concrete non-parametric method that we call Graph-based Relative Unconstrained Least-squares Importance Fitting (GRULSIF) We derive convergence rates for our collaborative approach that highlights the role played by variables such as the number of available observations per node, the size of the graph, and how accurately the graph structure encodes the similarity between tasks.
  arXiv  Detail & Related papers  (2022-05-28T15:37:03Z)
• Fast Computation of Generalized Eigenvectors for Manifold Graph Embedding [38.902986549367434]
  We leverage existing fast extreme eigenvector computation algorithms for speedy execution. Our embedding is among the fastest in the literature, while producing the best clustering performance for manifold graphs.
  arXiv  Detail & Related papers  (2021-12-15T03:45:39Z)
• Spatial Search on Johnson Graphs by Discrete-Time Quantum Walk [0.0]
  We address the spatial search problem on Johnson graphs using the coined quantum walk model. For every fixed diameter, the success probability is $1/2$ after taking $pisqrt N/(2sqrt 2)$ steps. We have shown that, for every fixed diameter, the success probability is $1/2$ after taking $pisqrt N/ (2sqrt)$ steps.
  arXiv  Detail & Related papers  (2021-12-07T15:00:07Z)
• Random Subgraph Detection Using Queries [29.192695995340653]
  The planted densest subgraph detection problem refers to the task of testing whether in a given (random) graph there is a subgraph that is unusually dense. In this paper, we consider a natural variant of the above problem, where one can only observe a relatively small part of the graph using adaptive edge queries. For this model, we determine the number of queries necessary and sufficient (accompanied with a quasi-polynomial optimal algorithm) for detecting the presence of the planted subgraph.
  arXiv  Detail & Related papers  (2021-10-02T07:41:17Z)
• Lackadaisical quantum walk in the hypercube to search for multiple marked vertices [0.0]
  In this article, we experimentally address several problems related to quantum walk in the hypercube with self-loops. We show that, in the case where neighbors are marked, the probability of success increases to close to $1$.
  arXiv  Detail & Related papers  (2021-08-20T23:19:55Z)
• Spatial Search on Johnson Graphs by Continuous-Time Quantum Walk [0.0]
  We show that spatial search on Johnson graphs by continuous-time quantum walk achieves the lower bound $pisqrtN/2$ with success probability $1$ally for every fixed diameter. The proof is mathematically rigorous and can be used for other graph classes.
  arXiv  Detail & Related papers  (2021-08-04T12:16:24Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.