Solving the Linear System

Simon's algorithm uses quantum parallelism to collect $n - 1$ linearly independent bitstring samples, each orthogonal (in $\mathbb{F}_2$) to a hidden string $s \in \{0,1\}^n \setminus \{0\}$. The quantum part is finished once those samples are in hand; the final step is purely classical: solve a small linear system over the two-element field $\mathbb{F}_2$.

The constraint each sample imposes

After one query, Simon's circuit produces a uniformly random $y \in \{0,1\}^n$ with the guarantee

$y \cdot s = \bigoplus_{i=0}^{n-1} y_i s_i = 0,$

where $\oplus$ is addition mod 2 and the bit indices run from 0 (least significant) to $n-1$. Equivalently, $y$ is orthogonal to $s$ over $\mathbb{F}_2$. Repeat the quantum circuit $n - 1$ times (re-running until the samples are linearly independent) and you have a full set of equations.

Gaussian elimination over $\mathbb{F}_2$

The system $Y s = 0$ with $Y \in \mathbb{F}_2^{(n-1) \times n}$ has a one-dimensional solution space when the oracle is balanced (i.e. $s \ne 0$). Standard Gaussian elimination works unchanged except all arithmetic is mod 2: no fractions, just XOR.

For $n$ qubits the algorithm runs in $O(n^2)$ time on a classical computer, so this post-processing adds no asymptotic cost to the overall exponential speedup over classical period finding.

A concrete 3-qubit example

Suppose $n = 3$ and the hidden string is $s = 101$ (decimal 5). The orthogonality condition becomes

$y_0 \cdot 1 \oplus y_1 \cdot 0 \oplus y_2 \cdot 1 = y_0 \oplus y_2 = 0,$

so a measurement $y$ is valid only when bits 0 and 2 agree. After two independent quantum measurements we obtain, for instance:

| Sample (binary) | Decimal | Check: $y \cdot 101$ | |-----------------|---------|-------------------------------| | $010$ | 2 | $0 \oplus 0 = 0$ ✓ | | $111$ | 7 | $1 \oplus 1 = 0$ ✓ |

Substituting $y^{(1)} = 010$ into the constraint gives $s_1 = 0$. Substituting $y^{(2)} = 111$ gives $s_0 \oplus s_2 = 0$, i.e. $s_0 = s_2$. With $s \ne 0$ the only solution is $s_0 = s_2 = 1$, confirming $s = 101 = 5$.

Try it

The starter code provides the two samples as integer bitvectors. Iterate over the $2^n - 1$ non-zero candidates and return the unique $s$ that is orthogonal to every sample.

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