Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Physical Review Research

Deterministic discrete-time quantum walk search on complete bipartite graphs

Fangjie Peng, Meng Li, Xiaoming Sun

Published Jul 9, 2024• 5 citations
Publisher

Abstract

Searching via quantum walk is a topic that has been extensively studied. Most previous results provide approximate solutions, while in this paper we prove an algorithm that can find a marked vertex certainly. We adopt the coined discrete-time quantum walk (DTQW) model with adjusted operators and prove that, on complete bipartite graphs, when parameters are set properly, coined DTQW can deterministically find a marked vertex, i.e., the success probability is exactly 1. Before this paper there have been results of an alternating continuous-time quantum walk method that achieve deterministic spatial search, but this paper provides a deterministic quantum spatial search result via DTQW, while maintaining a quadratic speedup compared to classical algorithms. We also provide the quantum circuit implementation. Published by the American Physical Society 2024

DOI
10.1103/physrevresearch.6.033042

Related papers

Universal approach to deterministic spatial search via alternating quantum walks

Qing‐Wen Wang, Ying Jiang, Shiguang Feng +1 more

Spatial search is an important problem in quantum computation, which aims to find a marked vertex on a graph. We propose a novel approach for designing deterministic quantum search algorithms on a variety of graphs via alternating quantum walks. Our approach is universal because it does not require an instance-specific analysis for different graphs. We highlight the flexibility of our approach by proving that for Johnson graphs, rook graphs, complete-square graphs and complete bipartite graphs, our quantum algorithms can find the marked vertex with $100\%$ success probability and achieve quadratic speedups over classical algorithms. This not only gives an alternative succinct way to prove the existing results, but also leads to new interesting findings on more general graphs.

arXiv:2307.16133•Jul 30, 2023•2 citations

Deterministic Search on Complete Bipartite Graphs by Continuous-Time Quantum Walk

Honghong Lin, Yun Shang

Abstract How to design deterministic spatial search algorithms is a difficult but important problem. This paper presents a deterministic search algorithm on complete bipartite graphs with optimal runtime scaling. Our algorithm adopts the simple form of alternating iterations of an oracle and a continuous-time quantum walk operator, which is a generalization of Grover's search algorithm. To address the case of the number of marked vertices being unknown, we construct a quantum counting algorithm based on the spectrum structure of the search operator. This is a non-trivial example of quantum counting for spatial search. To implement the continuous-time quantum walk operator, we perform Hamiltonian simulation in the quantum circuit model and simulate it on the IBM quantum computing platform Qiskit.

arXiv:2404.01640•Quantum Information and Computation•Oct 1, 2024•2 citations

Search algorithm on strongly regular graph by lackadaisical quantum walk

Fangjie Peng, Meng Li, Xiaoming Sun

Abstract Quantum walk is a widely used method in designing quantum algorithms. In this article, we consider the lackadaisical discrete-time quantum walk (DTQW) on strongly regular graphs (SRG). When there is a single marked vertex in a SRG, we prove that lackadaisical DTQW can find the marked vertex with asymptotic success probability 1, with a quadratic speedup compared to classical random walk. This paper deals with any parameter family of SRG and argues that, by adding self-loops with proper weights, the asymptotic success probability can reach 1. The running time and asymptotic success probability matches the result of continuous-time quantum walk, and improves the result of DTQW.

Journal of Physics A Mathematical and Theoretical•Mar 5, 2024•2 citations

Quantum Walk Search on Complete Multipartite Graph with Multiple Marked Vertices

Nan-Yow Chen, Meng Li, Xiaoming Sun

Quantum walk is a potent technique for building quantum algorithms. This paper examines the quantum walk search algorithm on complete multipartite graphs with multiple marked vertices, which has not been explored before. Two specific cases of complete multipartite graphs are probed in this paper, and in both cases, each set consists of an equal number of vertices. We employ the coined quantum walk model and achieve quadratic speedup with a constant probability of finding a marked vertex. Furthermore, we investigate the robust quantum walk of two cases and demonstrate that even with an unknown number of marked vertices, it is still possible to achieve a quadratic speedup compared to classical algorithms and the success probability oscillates within a small range close to 1. This work addresses the overcooking problem in quantum walk search algorithms on some complete multipartite graphs. We also provide the numerical simulation and circuit implementation of our quantum algorithm.

arXiv:2410.04924•Oct 7, 2024•0 citations

Quantum walk search on the complete bipartite graph

Mason L. Rhodes, Thomas G. Wong

The coined quantum walk is a discretization of the Dirac equation of relativistic quantum mechanics, and it is the basis of many quantum algorithms. We investigate how it searches the complete bipartite graph of $N$ vertices for one of $k$ marked vertices with different initial states. We prove an intriguing dependence on the number of marked and unmarked vertices in each partite set. For example, when the graph is irregular and the initial state is the typical uniform superposition over the vertices, then the success probability can vary greatly from one time step to the next, even alternating between 0 and 1, so the precise time at which measurement occurs is crucial. When the initial state is a uniform superposition over the edges, however, the success probability evolves smoothly. As another example, if the complete bipartite graph is regular, then the two initial states are equivalent. Then if two marked vertices are in the same partite set, the success probability reaches $1/2$, but if they are in different partite sets, it instead reaches 1. This differs from the complete graph, which is the quantum walk formulation of Grover's algorithm, where the success probability with two marked vertices is $8/9$. This reveals a contrast to the continuous-time quantum walk, whose evolution is governed by Schr\"odinger's equation, which asymptotically searches the regular complete bipartite graph with any arrangement of marked vertices in the same manner as the complete graph.

arXiv:1812.06079•Physical Review A•Mar 1, 2019•31 citations

Robust Quantum Walk Search on Complete Multipartite Graph With Multiple Marked Vertices

Nan-Yow Chen, Meng Li, Xiaoming Sun

Quantum walks are a potent technique for building quantum algorithms. This paper examines the quantum walk search algorithm on complete multipartite graphs with multiple marked vertices, which has not been explored before. We employ the coined quantum walk model and achieve quadratic speedup with a constant probability of finding a marked vertex in two specific cases of complete multipartite graphs. Furthermore, we investigate the robust quantum walk of two cases and demonstrate that even with an unknown number of marked vertices, it is still possible to achieve a quadratic speedup compared to classical algorithms and the success probability oscillates within a small range close to 1. To establish this conclusion, we employ approximation and reduction methods to conduct theoretical analysis and proofs, and provide an intuitive demonstration through numerical simulations. This work addresses the overcooking problem in quantum walk search algorithms on some complete multipartite graphs and may offer insights for robust quantum search on broader graph structures. Finally, we design a circuit for the algorithm that future researchers can use to conduct experiments.

IEEE Transactions on Quantum Engineering•Jan 1, 2026•1 citation
Searching via quantum walk is a topic that has been extensively studied. Most previous results provide approximate solutions, while in this paper we prove an algorithm that can find a marked vertex certainly. We adopt the coined discrete-time quantum walk (DTQW) model with adjusted operators and prove that, on complete bipartite graphs, when parameters are set properly, coined DTQW can deterministically find a marked vertex, i.e., the success probability is exactly 1. Before this paper there have been results of an alternating continuous-time quantum walk method that achieve deterministic spatial search, but this paper provides a deterministic quantum spatial search result via DTQW, while maintaining a quadratic speedup compared to classical algorithms. We also provide the quantum circuit implementation. Published by the American Physical Society 2024
Spatial search is an important problem in quantum computation, which aims to find a marked vertex on a graph. We propose a novel approach for designing deterministic quantum search algorithms on a variety of graphs via alternating quantum walks. Our approach is universal because it does not require an instance-specific analysis for different graphs. We highlight the flexibility of our approach by proving that for Johnson graphs, rook graphs, complete-square graphs and complete bipartite graphs, our quantum algorithms can find the marked vertex with 100%100\%100% success probability and achieve quadratic speedups over classical algorithms. This not only gives an alternative succinct way to prove the existing results, but also leads to new interesting findings on more general graphs.
Abstract How to design deterministic spatial search algorithms is a difficult but important problem. This paper presents a deterministic search algorithm on complete bipartite graphs with optimal runtime scaling. Our algorithm adopts the simple form of alternating iterations of an oracle and a continuous-time quantum walk operator, which is a generalization of Grover's search algorithm. To address the case of the number of marked vertices being unknown, we construct a quantum counting algorithm based on the spectrum structure of the search operator. This is a non-trivial example of quantum counting for spatial search. To implement the continuous-time quantum walk operator, we perform Hamiltonian simulation in the quantum circuit model and simulate it on the IBM quantum computing platform Qiskit.
Abstract Quantum walk is a widely used method in designing quantum algorithms. In this article, we consider the lackadaisical discrete-time quantum walk (DTQW) on strongly regular graphs (SRG). When there is a single marked vertex in a SRG, we prove that lackadaisical DTQW can find the marked vertex with asymptotic success probability 1, with a quadratic speedup compared to classical random walk. This paper deals with any parameter family of SRG and argues that, by adding self-loops with proper weights, the asymptotic success probability can reach 1. The running time and asymptotic success probability matches the result of continuous-time quantum walk, and improves the result of DTQW.
Quantum walk is a potent technique for building quantum algorithms. This paper examines the quantum walk search algorithm on complete multipartite graphs with multiple marked vertices, which has not been explored before. Two specific cases of complete multipartite graphs are probed in this paper, and in both cases, each set consists of an equal number of vertices. We employ the coined quantum walk model and achieve quadratic speedup with a constant probability of finding a marked vertex. Furthermore, we investigate the robust quantum walk of two cases and demonstrate that even with an unknown number of marked vertices, it is still possible to achieve a quadratic speedup compared to classical algorithms and the success probability oscillates within a small range close to 1. This work addresses the overcooking problem in quantum walk search algorithms on some complete multipartite graphs. We also provide the numerical simulation and circuit implementation of our quantum algorithm.
The coined quantum walk is a discretization of the Dirac equation of relativistic quantum mechanics, and it is the basis of many quantum algorithms. We investigate how it searches the complete bipartite graph of NNN vertices for one of kkk marked vertices with different initial states. We prove an intriguing dependence on the number of marked and unmarked vertices in each partite set. For example, when the graph is irregular and the initial state is the typical uniform superposition over the vertices, then the success probability can vary greatly from one time step to the next, even alternating between 0 and 1, so the precise time at which measurement occurs is crucial. When the initial state is a uniform superposition over the edges, however, the success probability evolves smoothly. As another example, if the complete bipartite graph is regular, then the two initial states are equivalent. Then if two marked vertices are in the same partite set, the success probability reaches 1/21/21/2, but if they are in different partite sets, it instead reaches 1. This differs from the complete graph, which is the quantum walk formulation of Grover's algorithm, where the success probability with two marked vertices is 8/98/98/9. This reveals a contrast to the continuous-time quantum walk, whose evolution is governed by Schr\"odinger's equation, which asymptotically searches the regular complete bipartite graph with any arrangement of marked vertices in the same manner as the complete graph.
Quantum walks are a potent technique for building quantum algorithms. This paper examines the quantum walk search algorithm on complete multipartite graphs with multiple marked vertices, which has not been explored before. We employ the coined quantum walk model and achieve quadratic speedup with a constant probability of finding a marked vertex in two specific cases of complete multipartite graphs. Furthermore, we investigate the robust quantum walk of two cases and demonstrate that even with an unknown number of marked vertices, it is still possible to achieve a quadratic speedup compared to classical algorithms and the success probability oscillates within a small range close to 1. To establish this conclusion, we employ approximation and reduction methods to conduct theoretical analysis and proofs, and provide an intuitive demonstration through numerical simulations. This work addresses the overcooking problem in quantum walk search algorithms on some complete multipartite graphs and may offer insights for robust quantum search on broader graph structures. Finally, we design a circuit for the algorithm that future researchers can use to conduct experiments.