How the quantum search algorithm works

Christoph Dürr, xb b b

Ahmed Younes, Jon Rowe, Julian Francis Miller

In this paper we will present a quantum algorithm which works very efficiently in case of multiple matches within the search space and in the case of few matches, the algorithm performs classically. This allows us to propose a hybrid quantum search engine that integrates Grover's algorithm and the proposed algorithm here to have general performance better that any pure classical or quantum search algorithm.

Uwe Schöning, Randall J. Pruim

Guanzhong Li, Jingquan Luo, Shiguang Feng +1 more

Abstract Searching for an unknown marked vertex on a given graph (also known as spatial search) is an extensively discussed topic in the area of quantum algorithms, with a plethora of results based on different quantum walk models and targeting various types of graphs. Most of these algorithms have a non‐zero probability of failure. In recent years, there have been some efforts to design quantum spatial search algorithms with success probability. However, these works either only work for very special graphs or only for the case where there is only one marked vertex. In this work, a different and elegant approach to quantum spatial search is proposed, obtaining deterministic quantum search algorithms that can find a marked vertex with certainty on any Laplacian integral graph with any predetermined proportion of marked vertices. Thus, this work discovers the largest class of graphs that allow deterministic quantum search, making it easy to design deterministic quantum search algorithms for many graphs, subsuming different graphs discussed in previous works, in a unified framework.

Jingfu Zhang, Zhi-Heng Lu

By studying the diffusion operator in Grover’s quantum search algorithm, we find an analogy between quantum searching and classical, elastic two-body collisions. We exploit this mathematical analogy using a thought experiment involving multiple collisions between two bodies to help illuminate why Grover’s quantum search algorithm works. Related issues are discussed.

Pulak Ranjan Giri, V. E. Korepin