Checkpoint: Simon’s Algorithm

This is your Simon's algorithm checkpoint. You will assemble the complete quantum circuit from scratch — superposition, oracle, and the Hadamard interference layer — and verify that the output satisfies the orthogonality constraint that characterises Simon's algorithm.

The algorithm in one picture

Simon's circuit for $n$ input qubits and $m$ output qubits looks like this (time flows left to right):

$\underbrace{H^{\otimes n}}_{\text{1. superpose}} \;\longrightarrow\; \underbrace{U_f}_{\text{2. oracle}} \;\longrightarrow\; \underbrace{H^{\otimes n}}_{\text{3. interfere}} \;\longrightarrow\; \text{measure input register}$

The three steps are the complete quantum part of the algorithm. After $O(n)$ repetitions, the measurement outcomes are fed into classical Gaussian elimination to recover the hidden string $s$ .

The instance you will implement

The circuit uses $n = 2$ input qubits (register A, qubits 0 and 1, qubit 0 is the most significant bit) and one output qubit (register B, qubit 2). The oracle computes

$f(x_0 x_1) = x_0,$

where $x_0$ is the MSB. Because $f$ ignores $x_1$ , it satisfies $f(x) = f(x \oplus s)$ for $s = 01_2$ : flipping only $x_1$ leaves the output unchanged. This is the Simon promise with hidden string $s = 01_2$ .

What the oracle does

The oracle $U_f$ acts on the 3-qubit register as

$U_f|x_0, x_1, y\rangle = |x_0, x_1, y \oplus f(x_0 x_1)\rangle = |x_0, x_1, y \oplus x_0\rangle.$

Copying a single bit with XOR is the definition of a CNOT: $\mathrm{CNOT}(0 \to 2)$ flips qubit 2 when qubit 0 is $|1\rangle$ and leaves it alone when qubit 0 is $|0\rangle$ .

Why interference selects orthogonal outcomes

After the oracle, the state is a superposition in which each value of $f$ appears paired with two input strings $x_0$ and $x_0 \oplus s$ . The second $H^{\otimes 2}$ layer applies the Walsh-Hadamard transform over $\mathbb{Z}_2^2$ ; the amplitudes of every outcome $y$ that does not satisfy $y \cdot s = 0 \pmod 2$ cancel by destructive interference.

For $s = 01_2$ the orthogonality condition is

$y \cdot s = y_0 \cdot 0 + y_1 \cdot 1 = y_1 = 0 \pmod 2,$

so only outcomes with $y_1 = 0$ survive. In the 3-qubit circuit the input register contributes bits $(q_0, q_1)$ and the output register contributes $q_2$ , so the allowed measurement strings are exactly $\{000, 001, 100, 101\}$ , each with probability $\tfrac{1}{4}$ .

You can verify this by algebra. After $H^{\otimes 2}$ the 3-qubit state is

$\frac{1}{2}\bigl(|000\rangle + |001\rangle + |100\rangle - |101\rangle\bigr).$

Each of the four basis states appears with amplitude $\pm\tfrac{1}{2}$ , giving probability $\left|\tfrac{1}{2}\right|^2 = \tfrac{1}{4}$ . The minus sign on $|101\rangle$ is a global relative phase between terms and does not shift any probability — all four outcomes are equally likely, and the outcomes $|010\rangle$ , $|011\rangle$ , $|110\rangle$ , $|111\rangle$ (those with $q_1 = 1$ ) have zero probability.

Try it

Implement the full Simon circuit for this oracle. The grader checks the probability distribution over all three qubits; the correct circuit puts equal weight ( $0.25$ each) on $|000\rangle$ , $|001\rangle$ , $|100\rangle$ , and $|101\rangle$ , with zero probability on all remaining basis states.

Run your code to see the quantum state.