Two-qubit Grover search with N/M: build the oracle and check the result

What does one Grover iteration actually do?

Grover's algorithm searches for a marked input among N candidates. It needs two parts: an oracle that flips the sign of the marked state's amplitude, and a diffusion step that turns that sign difference into a probability difference. With two qubits there are N = 4 candidates, few enough to check every amplitude by hand.

This guide builds the circuit in N/M, predicts its output, then changes one part at a time. Everything runs in a local noiseless simulator; nothing here measures a physical quantum processor.

Run the circuit

Paste the following program into the Playground and run it with the local state-vector simulator:

module blog_grover2;
@seed(31);
fn main() {
  let q = qreg[2];
  sample 512 {
    H(q[0]);
    H(q[1]);
    CZ(q[0], q[1]);
    H(q[0]);
    H(q[1]);
    X(q[0]);
    X(q[1]);
    CZ(q[0], q[1]);
    X(q[0]);
    X(q[1]);
    H(q[0]);
    H(q[1]);
    let c0 = measure(q[0]);
    let c1 = measure(q[1]);
  }
  return q;
}

In the ideal model every one of the 512 shots returns 11. The seed makes sampling reproducible, although here there is no spread to reproduce: one outcome has probability 1.

Read the code

Outcomes in this article follow the Playground's display convention: q[0] is the rightmost digit. So 10 means q[1] = 1 and q[0] = 0, and running X(q[0]); alone shows 01. Other tools may order bits differently; check the convention before comparing 01 and 10.

The first two H gates create the uniform superposition: 00, 01, 10 and 11 each have amplitude 1/2.

CZ(q[0], q[1]) is the oracle. It multiplies the amplitude of 11 by −1 and leaves the other three unchanged. Every probability is still 1/4; only a relative phase has changed.

The next nine gates are the diffusion step. The X–CZ–X sandwich flips the sign of 00 alone, and the surrounding Hadamard layers turn that into a reflection about the uniform superposition. This is the standard inversion about the mean multiplied by −1, a global phase that does not change any measurement probability.

Why is one iteration enough? Write the starting state as cos θ times the uniform superposition of unmarked states plus sin θ times the marked state. With M = 1 marked state among N = 4, sin θ = √(M/N) = 1/2, so the marked state's initial amplitude is 1/2 and θ = π/6. Each Grover iteration rotates the state by 2θ in that two-dimensional plane, so after t iterations the marked-state probability is sin²((2t + 1)θ). For t = 1 this is sin²(π/2) = 1.

Inversion about the mean gives the same answer with plain arithmetic. After the oracle the amplitudes are 1/2, 1/2, 1/2 and −1/2, with mean 1/4. Reflecting each amplitude a about the mean, 2 · 1/4 − a, gives 0, 0, 0 and 1.

Change and predict

Write down your prediction before each run. Read the histogram and the pre-measurement probabilities, not the final-state readout: that shows the register after the last measurement collapsed it, so here it always reports a single outcome.

1. Mark a different state. Add X(q[0]); immediately before and immediately after the oracle's CZ, and leave the diffusion step unchanged. The X gates swap the roles of 0 and 1 on q[0], so the sign flip now lands on q[1] = 1, q[0] = 0, displayed as 10. One iteration returns 10 with probability 1. Wrapping the CZ with X(q[1]); instead marks 01, and wrapping both qubits marks 00.
2. Remove the diffusion step. Delete the nine gates between the oracle and the measurements. The oracle changes only a phase, invisible to a computational-basis measurement: all four outcomes stay at 1/4.
3. Apply two iterations. Repeat the oracle and the diffusion step once more before measuring. The rotation overshoots the target: sin²(5θ) = sin²(5π/6) = 1/4, and in fact all four outcomes return to 1/4. More iterations are not automatically better; for N = 4 with one marked state, one iteration is optimal.

What this does not show

The quadratic advantage concerns the number of oracle queries in unstructured search: on the order of √N queries, compared with the order of N a classical search needs. It is a statement about query count, not a general claim about running time.

The oracle here was written with the answer already known. CZ marks 11 because we chose 11. This is a toy example; a useful oracle must recognise solutions without containing them, and building that circuit is often the difficult part.

With two qubits there is no practical speedup. A classical program checks four candidates trivially.

The real cost also includes the oracle circuit and noise. On hardware, the oracle and diffusion gates accumulate errors, and circuit depth grows quickly with the number of qubits. None of that appears in this noiseless model.

Next steps and sources

• N/M algorithms: further algorithm circuits to explore.
• Build a Bell state with N/M: the two-qubit sampling and bit-order habits used here.
• N/M documentation: the gate reference, including H, X and CZ.
• Grover, "A fast quantum mechanical algorithm for database search" (1996): the original algorithm and its O(√N) step count.
• IBM Quantum Learning: Grover's algorithm, analysis: the rotation by 2θ and the sin²((2t + 1)θ) formula.
• IBM Quantum tutorial: Grover's algorithm: X-gate open controls, the optimal iteration count and two-qubit depth scaling.

The probabilities in this article describe the stated ideal circuit in a local noiseless simulation, not a hardware experiment.