Generalized Grover’s Algorithm for Multiple Phase Inversion States

Grover’s algorithm is a quantum search algorithm that proceeds by repeated applications of the Grover operator and the Oracle until the state evolves to one of the target states. In the standard version of the algorithm, the Grover operator inverts the sign on only one state. Here we provide an exact solution to the problem of performing Grover’s search where the Grover operator inverts the sign on $N$ states. We show the underlying structure in terms of the eigenspectrum of the generalized Hamiltonian, and derive an appropriate initial state to perform the Grover evolution. This allows us to use the quantum phase estimation algorithm to solve the search problem in this generalized case, completely bypassing the Grover algorithm altogether. We obtain a time complexity of this case of $\sqrt{D/M^{\alpha }}$, where $D$ is the search space dimension, $M$ is the number of target states, and $\alpha \approx 1$, which is close to the optimal scaling.

Figure 1

(a) Interpretation of the generalized Grover evolution as Rabi oscillations between source $\mathcal{S}$ and target $\mathcal{T}$ subspaces. (b) Energy spectrum of the Grover Hamiltonian after diagonalization. States in the source and target sector appear in pairs with energy ${\epsilon }_n^{\pm }=1\pm |c_n|$. Unpaired states in $\mathcal{S}$ and $\mathcal{T}$ have an energy of 1, and all remaining states have energy 0. (c) Quantum circuit that produces a state in the target sector $\mathcal{T}$ for the generalized Grover algorithm. Here $U=e^{-iH}$, where $H$ is Eq. (1), $O$ is the oracle, $\mathcal{H}$ is a Hadamard gate, and ${\mathrm{QFT}}^{-1}$ is an inverse quantum Fourier transform. (d) Distribution of eigenvalues of the Grover Hamiltonian (1) for initial states of the form $|{\psi }_n⟩=\mathcal{H}|n⟩$ and $N=M=10$ and $D=2^5$. The average value of $|c_n|$ over all choices of initial state $c_{\mathrm{av}}$ is compared to the standard Grover scaling of $\sqrt{M/D}$ and the upper bound $\sqrt{MN/D}$.

Figure 2

(a) Time evolution with the generalized Grover Hamiltonian with various initial states chosen as $|{\psi }_n⟩$. (b) Time evolution choosing various initial state $|{\mathrm{\Psi }}_n(t=0)⟩$. (c) Evolving the various $|{\mathrm{\Psi }}_n(t=0)⟩$ using a gate based Grover iteration. One Grover iteration corresponds to the combined application of $G=e^{-i\pi P_{\mathcal{S}}}=1–2P_{\mathcal{S}}$ and $O=e^{-i\pi P_{\mathcal{T}}}=1–2P_{\mathcal{T}}$. For (a),(b),(c) $D=100$, $N=5$ source states, and $M=5$ target states. The source states $|{\psi }_n⟩$ are taken to be orthonormal random vectors. (d) Scaling of the average energy separation $c_{\mathrm{av}}$ for $M=N$, $D=2^5$, and averaged over random choices of $|{\psi }_n⟩=\mathcal{H}|n⟩$ (points). Scaling of the maximum $|c_n|$ ($\propto \sqrt{MN/D}$) and standard Grover result ($\propto \sqrt{M/D}$) are shown for comparison (dashed lines). A straight line fit of the points gives a slope of $\alpha /2\approx 0.45$.