Fixed-Point Quantum Search with an Optimal Number of Queries

Grover’s quantum search and its generalization, quantum amplitude amplification, provide a quadratic advantage over classical algorithms for a diverse set of tasks but are tricky to use without knowing beforehand what fraction $\lambda$ of the initial state is comprised of the target states. In contrast, fixed-point search algorithms need only a reliable lower bound on this fraction but, as a consequence, lose the very quadratic advantage that makes Grover’s algorithm so appealing. Here we provide the first version of amplitude amplification that achieves fixed-point behavior without sacrificing the quantum speedup. Our result incorporates an adjustable bound on the failure probability and, for a given number of oracle queries, guarantees that this bound is satisfied over the broadest possible range of $\lambda$.

Figure 1

A comparison of search algorithms, plotting the overlap $P_L$ of the target state with the output state versus the overlap $\lambda$ of the target state with the initial state. We weigh our fixed-point (FP) algorithm (thick solid) against the $\pi /3$ algorithm (dashed) for the task of achieving output success probability $P_L$ greater than $1-{\delta }^2=0.9$ for all $\lambda >{\lambda }_0$. The query complexities of the algorithms vary based on ${\lambda }_0$ (dotted vertical lines). For ${\lambda }_0=0.25$ (blue), our algorithm makes 4 queries while the $\pi /3$ algorithm makes 8. For ${\lambda }_0=0.03$ (red), our algorithm makes 12 queries while the $\pi /3$ algorithm makes 80. For comparison, also shown is Grover’s non-fixed-point (NFP) search with 8 queries (thin black). The width and error for our 4-query algorithm are labeled $w$ and $\delta$, respectively. Inset: we plot the query complexity against $\lambda$ for our algorithm with ${\delta }^2=0.1$ (solid), the $\pi /3$ algorithm (dashed), and non-fixed-point Grover’s (dotted). While our FP algorithm and Grover’s NFP algorithm scale as $L\sim 1/\sqrt{\lambda }$, the $\pi /3$ algorithm scales as $L\sim 1/\lambda$.

Figure 2

We provide a circuit for performing the generalized Grover iterate $G(\alpha ,\beta )$ up to a global phase. Here, $Z_{\theta }≔R_0(\theta )$ represents a rotation about the $z$ axis by angle $\theta$. The first part of the circuit, before the dotted line, performs $e^{-i\beta /2}{S}_t(\beta )$ and the second part performs $S_s(\alpha )$. One ancilla bit initialized as $|0⟩$ is required for both parts, but can be reused. The multiply-controlled not gates in the $S_s(\alpha )$ circuit do not pose a substantial overhead—they can be implemented with $\mathcal{O}(n^2)$ single qubit and cnot gates [17] or $\mathcal{O}(n)$ such gates and $\mathcal{O}(n)$ ancillas [18].