Faster quantum searching with almost any diffusion operator
Avatar Tulsi · Physical Review A · 2015
Grover's search algorithm drives a quantum system from an initial state $|s\ensuremath{\rangle}$ to a desired final state $|t\ensuremath{\rangle}$ by using selective phase inversions of these two states. Earlier, we studied a generalization of Grover's algorithm that relaxes the assumption of the efficient implementation of ${I}_{s}$, the selective phase inversion of the initial state, also known as a diffusion operator. This assumption is known to become a serious handicap in cases of physical interest. Our general search algorithm works with almost any diffusion operator ${D}_{s}$ with the only restriction of having $|s\ensuremath{\rangle}$ as one of its eigenstates. The price that we pay for using any operator is an increase in the number of oracle queries by a factor of $O(B)$, where $B$ is a characteristic of the eigenspectrum of ${D}_{s}$ and can be large in some situations. Here we show that by using a quantum Fourier transform, we can regain the optimal query complexity of Grover's algorithm without losing the freedom of using any diffusion operator for quantum searching. However, the total number of operators required by the algorithm is still $O(B)$ times more than that of Grover's algorithm. So our algorithm offers an advantage only if the oracle operator is computationally more expensive than the diffusion operator, which is true in most search problems.