Simon rank test correctness and linear query cost

By the factorwise tensor rule [F5], $H^{\otimes n}\mathrm{\mid }x⟩=N^{-1\mathrm{/}2}{\sum }_{y\in V_n}(-1{)}^{x\cdot y}\mathrm{\mid }y⟩$. In particular the first Hadamards prepare $N^{-1\mathrm{/}2}{\sum }_{x\in V_n}\mathrm{\mid }x,0^n⟩$. After one query the state is $\mathrm{\mid }{\psi }_f⟩=N^{-1\mathrm{/}2}{\sum }_{x\in V_n}\mathrm{\mid }x,f(x)⟩\mathrm{.}$ For each function-register result $z$ in the image of $f$, [F4] gives probability $\mathrm{\mid }{f}^{-1}(z)\mathrm{\mid }\mathrm{/}N$ and the conditional input superposition that is uniform on that fiber.

If $f$ is YES, every fiber is a singleton $\{x\}$. The conditional input state is $\mathrm{\mid }x⟩$, and the second Hadamards give amplitude $N^{-1\mathrm{/}2}(-1{)}^{x\cdot y}$ at every $y\in V_n$. By the first-register instrument law [F4], its squared modulus is the conditional output probability $1\mathrm{/}N$, independent of the measured function-register value; hence the unconditional sample is uniform on $V_n$.

If $f$ is NO with mask $s\mathrm{\ne }0$, a positive-probability fiber has the form $\{x,x\oplus s\}$. Its conditional input state is $(\mathrm{\mid }x⟩+\mathrm{\mid }x\oplus s⟩)\mathrm{/}\sqrt{2}$. After the second Hadamards the amplitude at $y$ is $\frac{(-1{)}^{x\cdot y}}{\sqrt{2N}}(1+(-1{)}^{s\cdot y})\mathrm{.}$ It is zero when $s\cdot y=1$ and has squared modulus $2\mathrm{/}N$ when $s\cdot y=0$. By [F4], these squared moduli are the conditional output probabilities. Pairing $y$ with $y\oplus e_j$ for a coordinate $j$ with $s_j=1$ shows that exactly $N\mathrm{/}2$ strings lie in $s^{\perp }$. The conditional law is therefore uniform on $s^{\perp }$ and independent of the measured fiber label, so the unconditional law is the same.

In the NO case every sample lies in $s^{\perp }$, which is proper because $e_j\mathrm{\notin }{s}^{\perp }$ when $s_j=1$. The span of the samples is proper, so its rank is less than $n$ and the algorithm rejects. The elimination procedure preserves row span under row swaps and row XORs; at termination its nonzero rows have distinct pivot columns and are linearly independent. They still span the original rows, so the pivot count is the matrix rank. At most $n$ pivots each inspect and update $O(n+2)$ rows of $n$ bits, giving $O(n^3)$ bit operations.

Each run reinitializes both registers and uses no earlier outcome as an input. Thus the conditional law of the next sample given any previous transcript is the same one-run law; induction on the number of runs gives the product law, and [F7] identifies the coordinates as independent. In the YES case each sample is uniform on $V_n$ by step 2.1. Their matrix has rank below $n$ exactly when some nonzero $t\in V_n$ satisfies $t\cdot y_j=0$ for every row $j$: Gaussian elimination uses invertible row operations and produces fewer than $n$ pivot columns, so a free variable can be set to $1$ and the pivot variables solved backwards to give a nonzero solution of the homogeneous system. Conversely, if such a $t$ exists, every row lies in its kernel; a coordinate vector $e_k$ with $t_k=1$ is outside that kernel, so the rows cannot span $V_n$.

Fix $t\mathrm{\ne }0$ and choose $k$ with $t_k=1$. The involution $y\mapsto y\oplus e_k$ pairs vectors with opposite values of $t\cdot y$, so a uniform sample satisfies $t\cdot y=0$ with probability $1\mathrm{/}2$. Independence gives probability $2^{-m}$ that all $m$ samples are orthogonal to $t$. Pointwise, the indicator of the union over the $N-1$ nonzero $t$ is at most the sum of their indicators; summing over the finite probability space yields $\mathrm{Pr}[\mathrm{rank}<n]\le (N-1)2^{-m}=(2^n-1)2^{-(n+2)}<\frac{1}{4}\mathrm{.}$ Each of the $m=n+2$ runs in [F2] makes one oracle call, applies two layers of $n$ ordinary Hadamard gates, and performs two finite register readouts. Thus the totals are $n+2$ queries, $2n(n+2)$ Hadamard gates, and $2(n+2)$ readouts; step 3.1 gives the classical elimination cost.