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:2404.01640 · Quantum Information and Computation

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

Honghong Lin, Yun Shang

Published Oct 1, 2024• 2 citations
arXivHTMLPDF

Abstract

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.

DOI
10.2478/qic-2024-0001

Related papers

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

Efficient Circuit Implementations of Continuous-Time Quantum Walks for Quantum Search

Renato Portugal, Jalil Khatibi Moqadam

Quantum walks are a powerful framework for simulating complex quantum systems and designing quantum algorithms, particularly for spatial search on graphs, where the goal is to find a marked vertex efficiently. In this work, we present efficient quantum circuits that implement the evolution operator of continuous-time quantum-walk-based search algorithms for three graph families: complete graphs, complete bipartite graphs, and hypercubes. For complete and complete bipartite graphs, our circuits exactly implement the evolution operator. For hypercubes, we propose an approximate implementation that closely matches the exact evolution operator as the number of vertices increases. Our Qiskit simulations demonstrate that even for low-dimensional hypercubes, the algorithm effectively identifies the marked vertex. Furthermore, the approximate implementation developed for hypercubes can be extended to a broad class of graphs, enabling efficient quantum search in scenarios where exact implementations are impractical.

arXiv:2212.08889•Entropy•Apr 23, 2025•1 citation

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 spatial search using alternating quantum walks

S. Marsh, Jingbo B. Wang

This paper examines the performance of spatial search where the Grover diffusion operator is replaced by continuous-time quantum walks on a class of interdependent networks. We prove that, for a set of optimal quantum walk times and marked vertex phase shifts, a deterministic algorithm for structured spatial search is established that finds the marked vertex with 100% probability. This improves on the Childs and Goldstone spatial search algorithm on the same class of graphs, which we show can only amplify to 50% probability. Our method uses $\ensuremath{\lceil}\frac{\ensuremath{\pi}}{2\sqrt{2}}\sqrt{N}\ensuremath{\rceil}$ marked vertex phase shifts for an $N$-vertex graph, making it comparable to Grover's algorithm for an unstructured search. It is expected that this framework can be readily extended to deterministic spatial search on other families of graph structures.

arXiv:2104.03806•Physical Review A•Aug 24, 2021•15 citations

Quantum counting on the complete bipartite graph

Gustavo Alves Bezerra, Raqueline A. M. Santos, Renato Portugal

Quantum counting is a key quantum algorithm that aims to determine the number of marked elements in a database. This algorithm is based on the quantum phase estimation algorithm and uses the evolution operator of Grover’s algorithm because its nontrivial eigenvalues are dependent on the number of marked elements. Since Grover’s algorithm can be viewed as a quantum walk on a complete graph, a natural way to extend quantum counting is to use the evolution operator of quantum-walk-based search on noncomplete graphs instead of Grover’s operator. In this paper, we explore this extension by analyzing the coined quantum walk on the complete bipartite graph with an arbitrary number of marked vertices. We show that some eigenvalues of the evolution operator depend on the number of marked vertices and using this fact we show that the quantum phase estimation can be used to obtain the number of marked vertices. The time complexity for estimating the number of marked vertices in the bipartite graph with our algorithm equates closely with that of the original quantum counting algorithm.

arXiv:2311.10407•International Journal of Quantum Information•May 10, 2024•2 citations

Multimarked Spatial Search by Continuous-Time Quantum Walk

Pedro H. G. Lugão, Renato Portugal, Mohamed Sabri +1 more

The quantum-walk-based spatial search problem aims to find a marked vertex using a quantum walk on a graph with marked vertices. We describe a framework for determining the computational complexity of spatial search by continuous-time quantum walk on arbitrary graphs by providing a recipe for finding the optimal running time and the success probability of the algorithm. The quantum walk is driven by a Hamiltonian derived from the adjacency matrix of the graph modified by the presence of the marked vertices. The success of our framework depends on the knowledge of the eigenvalues and eigenvectors of the adjacency matrix. The spectrum of the Hamiltonian is subsequently obtained from the roots of the determinant of a real symmetric matrix M , the dimensions of which depend on the number of marked vertices. The eigenvectors are determined from a basis of the kernel of M . We show each step of the framework by solving the spatial searching problem on the Johnson graphs with a fixed diameter and with two marked vertices. Our calculations show that the optimal running time is \(O(\sqrt {N})\) with an asymptotic probability of 1+ o (1), where N is the number of vertices.

arXiv:2203.14384•ACM Transactions on Quantum Computing•Nov 27, 2024•5 citations
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.
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
Quantum walks are a powerful framework for simulating complex quantum systems and designing quantum algorithms, particularly for spatial search on graphs, where the goal is to find a marked vertex efficiently. In this work, we present efficient quantum circuits that implement the evolution operator of continuous-time quantum-walk-based search algorithms for three graph families: complete graphs, complete bipartite graphs, and hypercubes. For complete and complete bipartite graphs, our circuits exactly implement the evolution operator. For hypercubes, we propose an approximate implementation that closely matches the exact evolution operator as the number of vertices increases. Our Qiskit simulations demonstrate that even for low-dimensional hypercubes, the algorithm effectively identifies the marked vertex. Furthermore, the approximate implementation developed for hypercubes can be extended to a broad class of graphs, enabling efficient quantum search in scenarios where exact implementations are impractical.
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.
This paper examines the performance of spatial search where the Grover diffusion operator is replaced by continuous-time quantum walks on a class of interdependent networks. We prove that, for a set of optimal quantum walk times and marked vertex phase shifts, a deterministic algorithm for structured spatial search is established that finds the marked vertex with 100% probability. This improves on the Childs and Goldstone spatial search algorithm on the same class of graphs, which we show can only amplify to 50% probability. Our method uses $\ensuremath{\lceil}\frac{\ensuremath{\pi}}{2\sqrt{2}}\sqrt{N}\ensuremath{\rceil}$ marked vertex phase shifts for an NNN-vertex graph, making it comparable to Grover's algorithm for an unstructured search. It is expected that this framework can be readily extended to deterministic spatial search on other families of graph structures.
Quantum counting is a key quantum algorithm that aims to determine the number of marked elements in a database. This algorithm is based on the quantum phase estimation algorithm and uses the evolution operator of Grover’s algorithm because its nontrivial eigenvalues are dependent on the number of marked elements. Since Grover’s algorithm can be viewed as a quantum walk on a complete graph, a natural way to extend quantum counting is to use the evolution operator of quantum-walk-based search on noncomplete graphs instead of Grover’s operator. In this paper, we explore this extension by analyzing the coined quantum walk on the complete bipartite graph with an arbitrary number of marked vertices. We show that some eigenvalues of the evolution operator depend on the number of marked vertices and using this fact we show that the quantum phase estimation can be used to obtain the number of marked vertices. The time complexity for estimating the number of marked vertices in the bipartite graph with our algorithm equates closely with that of the original quantum counting algorithm.
The quantum-walk-based spatial search problem aims to find a marked vertex using a quantum walk on a graph with marked vertices. We describe a framework for determining the computational complexity of spatial search by continuous-time quantum walk on arbitrary graphs by providing a recipe for finding the optimal running time and the success probability of the algorithm. The quantum walk is driven by a Hamiltonian derived from the adjacency matrix of the graph modified by the presence of the marked vertices. The success of our framework depends on the knowledge of the eigenvalues and eigenvectors of the adjacency matrix. The spectrum of the Hamiltonian is subsequently obtained from the roots of the determinant of a real symmetric matrix M , the dimensions of which depend on the number of marked vertices. The eigenvectors are determined from a basis of the kernel of M . We show each step of the framework by solving the spatial searching problem on the Johnson graphs with a fixed diameter and with two marked vertices. Our calculations show that the optimal running time is O(N)O(\sqrt {N})O(N​) with an asymptotic probability of 1+ o (1), where N is the number of vertices.