Combining with Oracles

Amplitude amplification is most powerful when you supply your own oracle — a quantum circuit that recognizes a "good" answer by flipping a phase — and then wrap it with the standard diffuser. This separation of concerns is what makes the framework reusable: you write the problem-specific oracle once, and the amplification machinery does the rest.

Anatomy of one amplification round

A single amplification iteration for an $n$-qubit uniform superposition $|s\rangle = H^{\otimes n}|0^n\rangle$ consists of two steps applied in sequence after the initial superposition is created:

1. Oracle $U_f$: phase-flips every basis state $|x\rangle$ that satisfies the target predicate $f(x) = 1$, leaving all other states unchanged:

   $U_f|x\rangle = (-1)^{f(x)}|x\rangle.$

2. Diffuser $D$: reflects amplitudes about their mean, which boosts the amplitude of the phase-flipped state and suppresses the rest:

   $D = 2|s\rangle\langle s| - I = H^{\otimes n}(2|0^n\rangle\langle 0^n| - I)H^{\otimes n}.$

The composition $D\,U_f$ rotates the state toward the marked item by $2\theta$ per iteration, where $\sin\theta = \sqrt{M/N}$ and $M$ is the number of marked states out of $N = 2^n$.

Designing a custom oracle

The oracle for a specific target $|t\rangle$ must flip the phase of $|t\rangle$ and leave everything else unchanged. Because the CZ gate phase-flips $|11\rangle$, any single-basis-state oracle can be built by conjugating CZ with $X$ gates that map $|t\rangle$ to $|11\rangle$:

$U_{|t\rangle} = \Bigl(\bigotimes_{i:\,t_i=0} X_i\Bigr)\;CZ\;\Bigl(\bigotimes_{i:\,t_i=0} X_i\Bigr).$

The $X$ gates on the qubits that are $0$ in $|t\rangle$ flip those qubits to $1$, making $|t\rangle$ look like $|11\rangle$. The CZ then applies the $-1$ phase. The final $X$ gates restore the labels.

Example: oracle for $|01\rangle$ on two qubits

For the target $|01\rangle$ (qubit 0 is $0$, qubit 1 is $1$), only qubit 0 needs to be flipped before CZ can act:

$U_{|01\rangle} = (X \otimes I)\;CZ\;(X \otimes I).$

Verification: $|01\rangle \xrightarrow{X_0} |11\rangle \xrightarrow{CZ} -|11\rangle \xrightarrow{X_0} -|01\rangle$, while any other basis state is unaffected (for example, $|00\rangle \xrightarrow{X_0} |10\rangle \xrightarrow{CZ} |10\rangle \xrightarrow{X_0} |00\rangle$).

Putting it together: one Grover iteration on two qubits

For $N = 4$ ($n = 2$ qubits) and a single marked state ($M = 1$), the success probability starts at $p_0 = 1/4$ and $\sin\theta = 1/2$, so $\theta = \pi/6$. After one iteration the state is rotated by $2\theta = \pi/3$ from its starting angle of $\theta = \pi/6$, placing it at $3\theta = \pi/2$ — exactly on the marked state. The success probability becomes $\sin^2(\pi/2) = 1$: the measurement finds $|01\rangle$ with certainty.

The full two-qubit circuit is:

$H^{\otimes 2}\;\underbrace{(X_0\,CZ\,X_0)}_{\text{oracle for }|01\rangle}\;\underbrace{H^{\otimes 2}\,X^{\otimes 2}\,CZ\,X^{\otimes 2}\,H^{\otimes 2}}_{\text{diffuser}}.$

Try it

The starter code provides the uniform superposition and the standard two-qubit diffuser. Your task is to add the custom oracle that marks $|01\rangle$ in the space provided. The grader checks the output distribution, which should put all probability on $|01\rangle$.

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