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

arXiv:2410.04924

Quantum Walk Search on Complete Multipartite Graph with Multiple Marked Vertices

Nan-Yow Chen, Meng Li, Xiaoming Sun

Published Oct 7, 2024• 0 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.2410.04924

Related papers

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

Fixed-point Quantum Walk Search.

Lvzhou Li, Yongzhen Xu, Zhang Delong

n this paper, we consider the problem of searching a marked vertex in a graph based on quantum walks. A very large body of research exists on this issue, from both theoretical and experimental studies, yet the existing quantum walk-based search algorithms require knowing exactly how many marked vertices there are before starting the search process. In addition, even if the precise knowledge of the number of marked vertices is known, the success probability of these algorithms could shrink dramatically when the number of search steps is greater than the right one. For avoiding these defects, in this paper we present a new quantum walk-based search algorithm which need not know any prior information about the marked vertices, but still keeps a quadratic speedup over classical ones and ensures that the error is bounded by a tunable parameter $\epsilon$. More specifically, for an $N$-vertex complete bipartite graph with marked vertices but without knowing the number of marked vertices, if the number of search steps $h$ satisfies $h \geq \ln(\frac{2}{\sqrt{\epsilon}})\sqrt{N}$, then the algorithm will output a marked vertex with probability at least $ 1-\epsilon$ for any given $\epsilon\in (0,1]$. This feature leads to quantum search algorithms with stronger robustness and a wider scope of application.

•Nov 17, 2021•0 citations

Quantum-walk-based search algorithms with multiple marked vertices

Gustavo Alves Bezerra, Pedro H. G. Lugão, Renato Portugal

The quantum walk is a powerful tool to develop quantum algorithms, which usually are based on searching for a vertex in a graph with multiple marked vertices, with Ambainis's quantum algorithm for solving the element distinctness problem being the most shining example. In this work, we address the problem of calculating analytical expressions of the time complexity of finding a marked vertex using quantum-walk-based search algorithms with multiple marked vertices on arbitrary graphs, extending previous analytical methods based on Szegedy's quantum walk, which can be applied only to bipartite graphs. Two examples based on the coined quantum walk on two-dimensional lattices and hypercubes show the details of our method.

arXiv:2103.12878•Physical Review A•Jun 1, 2021•22 citations

Quadratic speedup for finding marked vertices by Quantum walks

Andris Ambainis, András Gilyén, Stacey Jeffery +1 more

A quantum walk algorithm can detect the presence of a marked vertex on a graph quadratically faster than the corresponding random walk algorithm (Szegedy, FOCS 2004). However, quantum algorithms that actually find a marked element quadratically faster than a classical random walk were only known for the special case when the marked set consists of just a single vertex, or in the case of some specific graphs. We present a new quantum algorithm for finding a marked vertex in any graph, with any set of marked vertices, that is (up to a log factor) quadratically faster than the corresponding classical random walk, resolving a question that had been open for 15 years.

arXiv:1903.07493•ACM Symposium on Theory of Computing (STOC)•Jun 7, 2020•45 citations

Robust quantum walk search without knowing the number of marked vertices

Yongzhen Xu, Delong Zhang, Lvzhou Li

There has been a very large body of research on searching a marked vertex on a graph based on quantum walks, and Grover's algorithm can be regarded as a quantum walk-based search algorithm on a special graph. However, the existing quantum walk-based search algorithms suffer severely from the souffl\'e problem, which mainly means that the success probability of finding a marked vertex could shrink dramatically, even to zero, when the number of search steps is greater than the right one, thus heavily reducing the robustness and practicability of the algorithm. Surprisingly, while the souffl\'e problem of Grover's algorithm has attracted enough attention, how to address this problem for general quantum walk-based search algorithms is missing in the literature. Here we initiate the study of overcoming the souffl\'e problem for quantum walk-based search algorithms by presenting a quantum walk-based search framework that achieves robustness without sacrificing the quantum speedup. In this framework, for any adjustable parameter $\ensuremath{\epsilon}$, the quantum algorithm can find a marked vertex on an $N$-vertex complete bipartite graph with probability at least $1\ensuremath{-}\ensuremath{\epsilon}$, whenever the number of search steps $h$ satisfies $h\ensuremath{\ge}ln(\frac{2}{\sqrt{\ensuremath{\epsilon}}})\sqrt{N}+1$. Note that the algorithm need not know the exact number of marked vertices. Consequently, we obtain quantum search algorithms with stronger robustness and practicability.

arXiv:2111.09012•Physical Review A•Nov 14, 2022•16 citations

Deterministic discrete-time quantum walk search on complete bipartite graphs

Fangjie Peng, Meng Li, Xiaoming Sun

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

Physical Review Research•Jul 9, 2024•5 citations
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.
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.
n this paper, we consider the problem of searching a marked vertex in a graph based on quantum walks. A very large body of research exists on this issue, from both theoretical and experimental studies, yet the existing quantum walk-based search algorithms require knowing exactly how many marked vertices there are before starting the search process. In addition, even if the precise knowledge of the number of marked vertices is known, the success probability of these algorithms could shrink dramatically when the number of search steps is greater than the right one. For avoiding these defects, in this paper we present a new quantum walk-based search algorithm which need not know any prior information about the marked vertices, but still keeps a quadratic speedup over classical ones and ensures that the error is bounded by a tunable parameter ϵ\epsilonϵ. More specifically, for an NNN-vertex complete bipartite graph with marked vertices but without knowing the number of marked vertices, if the number of search steps hhh satisfies h≥ln⁡(2ϵ)Nh \geq \ln(\frac{2}{\sqrt{\epsilon}})\sqrt{N}h≥ln(ϵ​2​)N​, then the algorithm will output a marked vertex with probability at least $ 1-\epsilon$ for any given ϵ∈(0,1]\epsilon\in (0,1]ϵ∈(0,1]. This feature leads to quantum search algorithms with stronger robustness and a wider scope of application.
The quantum walk is a powerful tool to develop quantum algorithms, which usually are based on searching for a vertex in a graph with multiple marked vertices, with Ambainis's quantum algorithm for solving the element distinctness problem being the most shining example. In this work, we address the problem of calculating analytical expressions of the time complexity of finding a marked vertex using quantum-walk-based search algorithms with multiple marked vertices on arbitrary graphs, extending previous analytical methods based on Szegedy's quantum walk, which can be applied only to bipartite graphs. Two examples based on the coined quantum walk on two-dimensional lattices and hypercubes show the details of our method.
A quantum walk algorithm can detect the presence of a marked vertex on a graph quadratically faster than the corresponding random walk algorithm (Szegedy, FOCS 2004). However, quantum algorithms that actually find a marked element quadratically faster than a classical random walk were only known for the special case when the marked set consists of just a single vertex, or in the case of some specific graphs. We present a new quantum algorithm for finding a marked vertex in any graph, with any set of marked vertices, that is (up to a log factor) quadratically faster than the corresponding classical random walk, resolving a question that had been open for 15 years.
There has been a very large body of research on searching a marked vertex on a graph based on quantum walks, and Grover's algorithm can be regarded as a quantum walk-based search algorithm on a special graph. However, the existing quantum walk-based search algorithms suffer severely from the souffl\'e problem, which mainly means that the success probability of finding a marked vertex could shrink dramatically, even to zero, when the number of search steps is greater than the right one, thus heavily reducing the robustness and practicability of the algorithm. Surprisingly, while the souffl\'e problem of Grover's algorithm has attracted enough attention, how to address this problem for general quantum walk-based search algorithms is missing in the literature. Here we initiate the study of overcoming the souffl\'e problem for quantum walk-based search algorithms by presenting a quantum walk-based search framework that achieves robustness without sacrificing the quantum speedup. In this framework, for any adjustable parameter $\ensuremath{\epsilon}$, the quantum algorithm can find a marked vertex on an NNN-vertex complete bipartite graph with probability at least $1\ensuremath{-}\ensuremath{\epsilon}$, whenever the number of search steps hhh satisfies $h\ensuremath{\ge}ln(\frac{2}{\sqrt{\ensuremath{\epsilon}}})\sqrt{N}+1$. Note that the algorithm need not know the exact number of marked vertices. Consequently, we obtain quantum search algorithms with stronger robustness and practicability.
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