An Optimized Quantum Maximum or Minimum Searching Algorithm and its Circuits
arXiv:1908.07943
Abstract
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, we propose an optimized quantum algorithm for searching maximum and minimum, based on DHA and the optimal quantum exact search algorithm. Furthermore, we provide the corresponding quantum circuits, together with three equivalent simplifications. In circumstances when we 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, our 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 our optimized maximum or minimum performs more efficiently compared with DHA. Our algorithm can serve as an important subroutine in various quantum algorithms which involves searching maximum or minimum.
References in corpus (17)
- Quantum Mechanics helps in searching for a needle in a haystack
- Elementary gates for quantum computation
- Supervised learning with quantum enhanced feature spaces
- Experimental One-Way Quantum Computing
- Demonstration of Two-Qubit Algorithms with a Superconducting Quantum Processor
- Demonstration of a small programmable quantum computer with atomic qubits
- Quantum computers can search rapidly by using almost any transformation
- Experimental Demonstration of Blind Quantum Computing
- Grover Algorithm with zero theoretical failure rate
- A Quantum Algorithm for Finding the Minimum
- Complete 3-Qubit Grover Search on a Programmable Quantum Computer
- A different kind of quantum search
- Implementation of Grover's Quantum Search Algorithm in a Scalable System
- On Arbitrary Phases in Quantum Amplitude Amplification
- Grover's Quantum Search Algorithm for an Arbitrary Initial Amplitude Distribution
- Analysis of Generalized Grover's Quantum Search Algorithms Using Recursion Equations
- Exactness of the Original Grover Search Algorithm