Finding a maximum or minimum is a fundamental building block in many mathematical models. Compared with classical algorithms, Durr, Hoyer’s quantum algorithm (DHA) achieves quadratic speed. However, its key step, the quantum exponential searching algorithm (QESA), which is based on Grover algorithm, is not a sure-success algorithm.
Meanwhile, quantum circuits encounter the gate decomposition problem due to variation of the scale of data. In this paper, researchers propose an optimized quantum algorithm for searching maximum and minimum, based on DHA and the optimal quantum exact search algorithm. Furthermore, they provide the corresponding quantum circuits, together with three equivalent simplifications. In circumstances when they can exactly estimate the ratio of the number of solutions M and the searched space N, our method can improve the successful probability close to 100%. Furthermore, compared with DHA, their algorithm shows an advantage in complexity with large databases and in the gate complexity of constructing oracles. Experiments have been executed on an IBM superconducting processor with two qubits, and a practical problem of finding the minimum from Titanic passengers’ age was numerically simulated. Both showed that their optimized maximum or minimum performs more efficiently compared with DHA. Their algorithm can serve as an important subroutine in various quantum algorithms which involves searching maximum or minimum. (Quantum Physics)
