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

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.