Boosting a Known Subroutine

Grover's search is a special case of a much more general technique: amplitude amplification. Any quantum subroutine $\mathcal{A}$ that succeeds with some probability $p = \sin^2\!\theta$ can be repeatedly amplified until $p$ approaches 1, using roughly $\lfloor\pi/(4\theta)\rfloor$ iterations — a quadratic speedup over classical repetition.

The Setup

Let $\mathcal{A}$ be a quantum circuit on $n$ qubits that transforms $|0\rangle^{\otimes n}$ into a state

$|\psi\rangle = \mathcal{A}|0\rangle = \sin\theta\,|\text{good}\rangle + \cos\theta\,|\text{bad}\rangle,$

where $|\text{good}\rangle$ is the subspace of "successful" computational outcomes and $|\text{bad}\rangle$ is its orthogonal complement. The success probability after a single run of $\mathcal{A}$ is

$p = \sin^2\!\theta.$

Amplitude amplification replaces repeated classical sampling with a unitary iteration that rotates the state inside the two-dimensional plane spanned by $|\text{good}\rangle$ and $|\text{bad}\rangle$.

One Amplification Iteration

A single iteration consists of two reflections:

1. Oracle $\mathcal{O}$: reflect about $|\text{bad}\rangle$ — phase-flip every "good" basis state by $-1$.

$\mathcal{O} = I - 2\,\Pi_{\text{good}},$

where $\Pi_{\text{good}}$ projects onto the good subspace.

2. Diffuser (reflection about $|\psi\rangle$):

$\mathcal{D} = \mathcal{A}\bigl(2|0\rangle\langle 0| - I\bigr)\mathcal{A}^\dagger.$

The composition $\mathcal{D}\,\mathcal{O}$ is a rotation by $2\theta$ in the good/bad plane. Starting at angle $\theta$ from $|\text{bad}\rangle$, after $k$ iterations the state is at angle $(2k+1)\theta$, giving success probability $\sin^2((2k+1)\theta)$.

A Concrete Example

Consider the 2-qubit subroutine

$\mathcal{A} = R_y(\pi/3) \otimes I,$

which acts only on qubit 0 and leaves qubit 1 in $|0\rangle$:

$\mathcal{A}|00\rangle = \cos\!\tfrac{\pi}{6}\,|00\rangle + \sin\!\tfrac{\pi}{6}\,|10\rangle = \frac{\sqrt{3}}{2}|00\rangle + \frac{1}{2}|10\rangle.$

Here $\sin\theta = \frac{1}{2}$, so $\theta = \pi/6$ and the initial success probability on $|10\rangle$ is $\frac{1}{4}$.

The oracle phase-flips $|10\rangle$. Because $|10\rangle$ has qubit 0 equal to 1 and qubit 1 equal to 0, we build it as: flip qubit 1 (X), apply $CZ$, flip qubit 1 back (X):

$\mathcal{O} = (I \otimes X)\,CZ\,(I \otimes X).$

The diffuser rebuilds $\mathcal{A}|00\rangle$ from the zero state:

$\mathcal{D}: \quad \mathcal{A}^\dagger,\quad 2|00\rangle\langle 00| - I,\quad \mathcal{A}.$

The phase-flip of $|00\rangle$ is: X on both qubits, then $CZ$, then X on both qubits.

After one full iteration the state becomes $-|10\rangle$, putting all probability on the good state $|10\rangle$.

Try it

The starter code applies the subroutine $\mathcal{A}$. Add the oracle that phase-flips the good state $|10\rangle$, then add the diffuser that reflects about $\mathcal{A}|00\rangle$. The grader checks the output distribution — it should put all probability on $|10\rangle$.

Sign in on the full site to ask questions and join the discussion.