Current Status and Prospects of Quantum Search Algorithm: Grover’s Algorithm

Grant Eberle, Gonzalo E. Ordonez

Yulun Wang, Predrag Krstić

In order to understand the bounds of utilization of Grover's search algorithm for large unstructured data in the presence of quantum computer noise, we undertake a series of simulations by inflicting various types of noise, modeled by the IBM qiskit. We apply three forms of Grover's algorithm: (i) the standard one, with 4--10 qubits; (ii) a recently published modified Grover's algorithm, set to reduce the circuit depth; and (iii) the algorithms in (i) and (ii) with multicontrol Toffoli's gates modified by the addition of an ancilla qubit. Based on these simulations, we find the upper bound of noise for these cases, establish its dependence on the quantum depth of the circuit, and provide comparison among them. By extrapolation of the fitted thresholds, we predict what would be the typical gate error bounds when applying Grover's algorithms for the search of data in a data set as large as 32 000.

Kyoichi Okamoto, Osamu Watanabe

WEI Jia,NI Ming,ZHOU Ming,JIANG Wenbing

To explore the implementation status of multi-bit quantum algorithm in quantum chips and simulators,Grover search algorithm,quantum random walk algorithm and quantum Fourier transform algorithm are run on IBM quantum chips and simulators respectively.For 2 bit Grover search algorithm and 2 bit quantum random walk algorithm,the influence of measurement times on operation results is analyzed and the maximum number of simulation times is selected to compare the operation results of quantum chip and simulator.A 5 bit quantum Fourier transform algorithm and a 3 bit Grover search algorithm are designed and run,and the IBM Q simulator is used to simulate the maximum number of times respectively.Experimental results show that the quantum chip test results are not optimized with the increase of the number of measurements,and the accuracy of the simulation results is obviously better than that of the quantum chip.

Tony Hey

The basic ideas of quantum computation are introduced by a brief discussion of Bennett (1973, 1982) and Fredkin's (1982, 1997) ideas of reversible computation. After some remarks about Deutsch's (1985) pioneering work on quantum complexity and Shor's (1996) factorisation algorithm, quantum logic gates, qubits and registers are discussed. The role of quantum entanglement is stressed and Grover's (1997) quantum search algorithm described in detail. The paper ends with a review of the current experimental status of quantum computers.

H. Sun, Z. Shi, S. Chen +5 more

Grover's algorithm relies on the superposition and interference of quantum mechanics, which is more efficient than classical computing in specific tasks such as searching an unsorted database. Due to the high complexity of quantum mechanics, the correctness of quantum algorithms is difficult to guarantee through traditional simulation methods. By contrast, the fundamental concepts and mathematical structure of Grover's algorithm can be formalized into logical expressions and verified by higher-order logical reasoning. In this paper, we formally model and verify Grover's algorithm in the HOL Light theorem prover. We focus on proving key properties such as the unitarity of its oracle and diffusion operators, the monotonicity of the success probability with respect to the number of iterations, and an exact expression for the optimal iteration count. By analyzing a concrete application to integer factorization, we demonstrate the practicality and prospects of our work.