Fixed-Point Amplification

Standard amplitude amplification is a rotation in a two-dimensional subspace. It steps the state vector toward the target subspace by a fixed angle $2\theta$ on every iteration, where $\sin\theta = \sqrt{p}$ and $p$ is the initial success probability. When the number of iterations is chosen to be exactly $j^* = \lfloor \tfrac{\pi}{4\theta} \rceil$ the state lands almost perfectly on the target — but if you apply even one extra iteration, the rotation continues and the probability starts to fall. This is the over-rotation problem.

Why over-rotation matters

Suppose you do not know $p$ precisely, so you cannot compute $j^*$ exactly. Or suppose $p$ varies across instances of your problem. Then naive amplification can over-shoot: the state rotates past the target, and the success probability after amplification can be lower than before it. For a concrete example, start with $p = 1/4$ (so $\theta = \pi/6$ , since $\sin(\pi/6) = 1/2$ and $\sin^2(\pi/6) = 1/4$ ). One iteration of Grover reaches $p = 1$ — the optimal outcome — while applying a second iteration returns $p$ back to $1/4$ : the over-rotation has undone all the gain.

The failure mode is illustrated by the rotation formula. After $k$ iterations the success probability is

$P(k) = \sin^2\!\big((2k+1)\theta\big).$

This oscillates: it hits 1 when $(2k+1)\theta = \tfrac{\pi}{2}$ , then falls back to 0 when $(2k+1)\theta = \pi$ , then rises again, and so on. Every peak corresponds to a lucky choice of $k$ ; every trough to over-rotation.

The fixed-point idea

A fixed-point amplification scheme replaces the constant-angle rotation with a sequence of rotations whose angles are tuned so that the cumulative effect converges monotonically to the target, regardless of $p$ . The probability increases with every additional iteration — it never overshoots and falls back.

The key insight (Yoder, Low, and Chuang, 2014) is to use a sequence of phase values $\phi_1, \phi_2, \ldots$ in the reflection operators rather than fixing them at $\pi$ . In standard Grover both reflections use phase $\pi$ :

$Q = -\mathcal{A}\,R_0\,\mathcal{A}^\dagger\,R_\chi,$

where $R_\chi$ flips the phase of target states and $R_0$ flips the phase of $|0\rangle^{\otimes n}$ . Fixed-point amplification generalises this to phase-parameterised reflections:

$R_\chi(\phi) = I - (1 - e^{i\phi})\Pi_\chi, \qquad R_0(\phi) = I - (1 - e^{i\phi})|0\rangle\langle 0|,$

and sets the phases according to a Chebyshev-based schedule so that the total rotation angle accumulates from the left and saturates near $\tfrac{\pi}{2}$ regardless of the starting angle $\theta$ .

Query complexity

Standard Grover achieves the optimal $O(1/\sqrt{p})$ query complexity but is not fixed-point. Yoder et al. showed that fixed-point quantum search can achieve the same asymptotic query complexity — $O(1/\sqrt{p})$ — while also being fixed-point. The optimal schedule requires $2k - 1$ queries for a depth- $k$ scheme. The success probability is monotonically non-decreasing in $k$ by construction, and to reduce the failure probability below $\varepsilon$ requires

$k = O\!\left(\frac{\log(1/\varepsilon)}{\sqrt{p}}\right)$

total oracle queries — the same $O(1/\sqrt{p})$ asymptotic scaling as standard amplitude amplification. In practice, even the depth-1 scheme ( $k = 1$ ) already coincides with standard Grover, and the depth-2 scheme eliminates the first over-rotation peak.

Intuition: comparing the two approaches

| | Standard AA | Fixed-Point AA | |---|---|---| | Angle per step | constant $2\theta$ | varies by step | | Success probability | oscillates | monotonically non-decreasing | | Requires knowing $p$ ? | yes (to stop at $j^*$ ) | no | | Query complexity | $O(1/\sqrt{p})$ | $O(1/\sqrt{p})$ | | Phase values | all equal to $\pi$ | Chebyshev schedule |

The table shows the trade-off: fixed-point amplification sacrifices the simplicity of a single repeated operator in exchange for robustness to unknown or varying success probabilities.

Connection to phase estimation

Fixed-point amplification is especially useful as a primitive inside algorithms that call amplitude amplification as a subroutine, such as quantum counting and amplitude estimation. In those settings the outer algorithm does not control exactly how many amplification steps are taken, so a scheme that converges without knowing when to stop is far more composable. Amplitude estimation (the next lesson) will use exactly this property.