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.
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 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.
Studies on Quantum Computing have been developed since the 1980s, motivating researches on quantum algorithms better than any classical algorithm possible. An example of such algorithms is Grover's algorithm, capable of finding k (marked) elements in an unordered database with N elements using O(N/k) steps. Grover's algorithm can be interpreted as a quantum walk in a complete graph (with loops) containing N vertices from which k are marked. This interpretation motivated search algorithms in other graphs -- complete bipartite graph, grid, and hypercube. Using Grover's algorithm's linear operator, the quantum counting algorithm estimates the value of k with an error of O(k) using O(N) steps. This work tackles the problem of using the quantum counting algorithm for estimating the value k of marked elements in other graphs; more specifically, the complete bipartite graph. It is concluded that for a particular case, running the proposed algorithm at most t times wields an estimation of k with an error of O(k) using O(tN) steps and success probability of at least (1−2−t)8/π2.
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.
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.
Testing graph completeness is a critical problem in computer science and network theory. Leveraging quantum computation, we present an efficient algorithm using the Szegedy quantum walk and quantum phase estimation (QPE). Our algorithm, which takes the number of nodes and the adjacency matrix as input, constructs a quantum walk operator and applies QPE to estimate its eigenvalues. These eigenvalues reveal the graph’s structural properties, enabling us to determine its completeness. We establish a relationship between the number of nodes in a complete graph and the number of marked nodes, optimizing the success probability and running time. The time complexity of our algorithm is O ( log 2 n ) , where n is the number of nodes of the graph. offering a clear quantum advantage over classical methods. This approach is useful in network structure analysis, evaluating classical routing algorithms, and assessing systems based on pairwise comparisons.
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.