Postprocessing for speeding up general quantum search algorithms

Abstract

A general quantum search algorithm aims to evolve a quantum system from a known source state $|s\ensuremath{\rangle}$ to an unknown target state $|t\ensuremath{\rangle}$. It uses a diffusion operator ${D}_{s}$ that has the source state as one of its eigenstates and ${I}_{t}$, where ${I}_{\ensuremath{\psi}}$ denotes the selective phase inversion of the $|\ensuremath{\psi}\ensuremath{\rangle}$ state. It evolves $|s\ensuremath{\rangle}$ to a particular state $|w\ensuremath{\rangle}$, which we will call the $w$ state, in $O(B/\ensuremath{\alpha})$ time steps, where $\ensuremath{\alpha}$ is $|\ensuremath{\langle}t|s\ensuremath{\rangle}|$ and $B$ is a characteristic of the diffusion operator. Measuring the $w$ state gives the target state with a success probability of $O(1/{B}^{2})$, and $O({B}^{2})$ applications of the algorithm can boost it from $O(1/{B}^{2})$ to $O(1)$, making the total time complexity $O({B}^{3}/\ensuremath{\alpha})$. In the special case of Grover's algorithm, ${D}_{s}$ is ${I}_{s}$ and $B$ is very close to 1. A more efficient way to boost the success probability is quantum amplitude amplification provided we can efficiently implement ${I}_{w}$. Such an efficient implementation is not known so far. In this paper, we present an efficient algorithm to approximate selective phase inversions of the unknown eigenstates of an operator using a phase estimation algorithm. This algorithm is used to efficiently approximate ${I}_{w}$, which reduces the time complexity of general algorithm to $O(B/\ensuremath{\alpha})$. Although $O(B/\ensuremath{\alpha})$ algorithms are known to exist, our algorithm offers physical implementation advantages.