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
• Authors: Pulak Ranjan Giri,
• 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

• 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)
• 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)
• 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.