CHAPTER 10

Simon’s algorithm and hidden XOR structure

Learning goals. Follow a two-register oracle calculation, derive the orthogonality constraint, and recover a hidden string by binary linear algebra.

10.1 A stronger oracle separation

Simon’s promise is a nonzero string $s\in\{0,1\}^n$ and a function satisfying

$$f(x)=f(x')\quad\Longleftrightarrow\quad x'=x\ \text{or}\ x'=x\oplus s.$$

Every output therefore has exactly two preimages. An oracle computes f into a sufficiently large output register. The problem is to determine s. The function’s outputs need not have a useful numerical meaning; their equality structure matters.

With randomly labeled outputs, a classical randomized procedure generally needs on the order of $2^{n/2}$ queries to find a collision and hence recover s. The birthday scale arises because k samples contain about $k(k-1)/2$ pairs. Simon’s quantum procedure obtains useful linear constraints with polynomially many queries [14].

This is an oracle-model result. If an explicit function description exposes s directly, there may be an easier classical method. The laboratory intentionally exposes the small oracle table for education; it does not claim its own visible table is a hidden real-world problem.

10.2 Prepare, query, and condition

Start in $|0^n\rangle|0^m\rangle$, apply Hadamards to the first register, then query:

$$\frac1{\sqrt{2^n}}\sum_x|x\rangle|f(x)\rangle.$$

If the output register is measured and the value is f(z), the input collapses to

$$\frac{|z\rangle+|z\oplus s\rangle}{\sqrt2}.$$

We need not actually perform or retain this measurement. Tracing out the output register gives the same input measurement probabilities after later operations. The conditioned description is simply convenient for deriving them.

Apply $H^{\otimes n}$:

$$\frac1{\sqrt{2^{n+1}}} \sum_y\left[(-1)^{z\cdot y}+(-1)^{(z\oplus s)\cdot y}\right]|y\rangle.$$

Because $(z\oplus s)\cdot y=z\cdot y\oplus s\cdot y$, the amplitude factors as

$$\frac{(-1)^{z\cdot y}}{\sqrt{2^{n+1}}} \left[1+(-1)^{s\cdot y}\right].$$

If $s\cdot y=1$, the bracket is zero. If $s\cdot y=0$, it is two. Thus y is uniformly distributed among the $2^{n-1}$ strings orthogonal to s over the binary field. The unknown z affects only signs, not the measured probabilities.

10.3 Binary Gaussian elimination

Each run supplies one equation $y\cdot s=0$. Collect independent rows into a matrix Y and solve $Ys=0$ over $\mathbb F_2$, where addition and subtraction are XOR. Once the rank reaches n−1, the nullspace contains exactly $0^n$ and the promised nonzero s.

Worked example. Let n=3 and s=101. The valid measurement strings are 000, 010, 101, 111. Suppose we obtain 010 and 101. The equations are

$$s_1=0,\qquad s_0\oplus s_2=0.$$

The free variable $s_2=t$ gives $(s_0,s_1,s_2)=(t,0,t)$. Excluding the zero vector forces t=1, giving 101. The row 111 is the XOR of 010 and 101, so it adds no independent information.

After rank r has been collected in the $(n-1)$-dimensional valid subspace, the next random sample is independent with probability $1-2^{r-(n-1)}$. The expected sample count to reach full rank is the sum of the reciprocals of these probabilities. It is $(n-1)$ plus a bounded constant, hence O(n). The zero row and repeated rows are normal, not simulator failures.

10.4 A concrete reversible oracle

For the laboratory, define $f_s(x)=\min(x,x\oplus s)$ using the integer order of bit strings. This maps each XOR pair to the same label and has no other collisions. A reversible oracle XORs that label into its output register.

The simulator calculates the exact input marginal by grouping equal output labels and applying the Hadamard transform. It does not simply print the secret as an answer. The recovery display uses only the sampled equations; the known secret is available separately for checking the experiment.

10.5 Failure modes and interpretation

Noise can produce y values with $s\cdot y=1$. Naively demanding that every equation be exact may then leave no nonzero solution. Recovering a mask from noisy constraints becomes a statistical inference problem. The noiseless proof does not automatically supply a robust experimental algorithm.

The all-zero mask belongs to a different one-to-one promise case in common formulations. This laboratory restricts to the nonzero two-to-one case and rejects zero. A valid interface should explain a promise violation rather than return a confident but meaningless result.

Simon’s importance is structural: coherent queries convert a hidden symmetry into measurement constraints. Shor’s algorithm later uses a related idea with periodicity under ordinary modular arithmetic, but the transforms and classical reconstruction differ.

10.6 Exercises