An Optimum Algorithm for Quantum Search
arXiv:2010.03949
Abstract
This paper discusses an improvement to Grover's algorithm for searches where target states are Hamming weight eigenstates and search space is not ordered. It is shown that under these conditions search efficiency depends on the smaller number of 0's and 1's, not the total length, of binary string of target state, and that Grover's algorithm can be improved whenever number of 0's and number 1's are not equal. In particular, improvement can be exponential when number of 0's or number of 1's is very small relative to binary string length. One interesting application is that Dicke state preparation, which in Grover's algorithm is P on average, can be made poly-efficient in all cases. For decision making process, this improvement won't improve computation efficiency, but can make implementation much simpler.
arXiv comment6 pages
References in corpus (8)
- Quantum algorithm for solving linear systems of equations
- Quantum Algorithms Revisited
- An approximate Fourier transform useful in quantum factoring
- An Exact Quantum Polynomial-Time Algorithm for Simon's Problem
- Neutrino Propagation in Matter
- Deterministic Preparation of Dicke States
- Generalized parity measurements
- Optimizing Quantum Search with a Binomial Version of Grover's Algorithm