Simon’s Algorithm and Finite-Field Recovery

The integer $2$ is greater than $1$. If a positive integer $d$ divides $2$, write $2=dq$ with positive integer $q$. If $d=1$ it is the first allowed divisor; if $d\mathrm{\ne }1$, then $d\ge 2$, which forces $q=1$ and $d=2$. Thus the only positive divisors are $1$ and $2$, so $2$ is prime by [F2].

Apply [F3] with $p=2$ using step 1.1. The carrier and both operations in [F1] are exactly those of $\mathbb{Z}\mathrm{/}2\mathbb{Z}$, so every field axiom supplied by that specialization holds for ${\mathbb{F}}_2$.

The coordinate operations are closed because each coordinate operation is an operation in ${\mathbb{F}}_2$ by [F1]. Each vector-space axiom in [F2] holds coordinate by coordinate by the corresponding field axiom in [F1]; coordinatewise equality then gives the vector identity. For $n=0$ there is only the empty tuple, and all coordinate identities hold vacuously.

For $i<n$, let $e_i$ have coordinate $1$ at $i$ and $0$ elsewhere. Every $x\in {\mathbb{F}}_2^n$ equals ${\sum }_{i<n}{x}_i{e}_i$ coordinatewise, so $B=\{e_i:i<n\}$ spans. The vectors $e_i$ are pairwise distinct because their $1$-coordinates differ. To verify that $B$ is independent in the subset sense of [F3], take any finite injective list $b:r\to B$ and coefficients $c_t\in {\mathbb{F}}_2$. If $r=0$, the independence implication is vacuous. Otherwise write $b_t=e_{i_t}$; injectivity and distinctness of the $e_i$ make the indices $i_t$ pairwise distinct. The coordinate $i_t$ of ${\sum }_{u<r}{c}_u{b}_u$ is then exactly $c_t$, so a zero sum forces every $c_t=0$. This also covers $n=0$, since then $B=\mathrm{\varnothing }$ admits no nonempty list. Thus $B$ is independent, and it is a basis by [F4]–[F5]. Its $n$ distinct vectors give dimension $n$.

By [F1] and [F2], $P_y\mathrm{\mid }z⟩={\delta }_{y,z}\mathrm{\mid }y⟩$; hence the $P_y$ are pairwise orthogonal self-adjoint idempotents and sum to the identity, as can be checked on every basis vector. For $z={\sum }_w{b}_w\mathrm{\mid }w⟩$, $⟨P_{y}z,z{⟩}_{\mathrm{r}\mathrm{o}\mathrm{o}\mathrm{t}}=\mathrm{\mid }{b}_y{\mathrm{\mid }}^2\ge 0$, so these projections are POVM effects by [F4]–[F5]. Also $⟨y,\psi {⟩}_{\mathrm{r}\mathrm{o}\mathrm{o}\mathrm{t}}=\overline{a_y}$, so $\rho P_y\mathrm{\mid }z⟩=0$ for $z\mathrm{\ne }y$ and $\rho P_y\mathrm{\mid }y⟩=\overline{a_y}\psi$. The coefficient of $\mathrm{\mid }y⟩$ in this last vector is $\mathrm{\mid }{a}_y{\mathrm{\mid }}^2$. Thus the only nonzero diagonal entry of $\rho P_y$ in this basis is $\mathrm{\mid }{a}_y{\mathrm{\mid }}^2$, and [F6] gives $\mathrm{tr}(\rho P_y)=\mathrm{\mid }{a}_y{\mathrm{\mid }}^2$.

The vector projector $\rho$ is a density operator by [F3]. The computational-basis projective measurement and its associated POVM law [F4]–[F5] therefore assign weight $\mathrm{tr}(\rho P_y)=\mathrm{\mid }{a}_y{\mathrm{\mid }}^2$ to outcome $y$. Since the basis is orthonormal and $\mathrm{\parallel }\psi \mathrm{\parallel }=1$, ${\sum }_y\mathrm{\mid }{a}_y{\mathrm{\mid }}^2=1$; each term is nonnegative. Hence the weights form a probability distribution.

Set $s=(1,0,\dots ,0)$, which is a nonzero $n$-bit string because $n\ge 1$. For every $x$, $x\oplus s\mathrm{\ne }x$ and $(x\oplus s)\oplus s=x$, so this involution partitions the $2^n$ addresses into disjoint two-element fibers; there are $2^{n-1}$ fibers.

The set of $m$-bit labels has $2^m$ elements: it has one empty word at width zero, and appending either $0$ or $1$ doubles the count at each additional bit. Since $m\ge n-1$, there are at least $2^{n-1}$ labels. Order the fibers by their least address and assign the first $2^{n-1}$ labels in lexicographic order; this constructs a total oracle satisfying the iff condition, so the promised family is nonempty.

The displayed iff condition makes the output fiber of $x$ exactly $\{x,x\oplus s\}$. Since $s\mathrm{\ne }0$, the two members are distinct. For any other nonzero period $t$, the point $x\oplus t$ is the unique other member of the fiber of $x$, so $x\oplus t=x\oplus s$ and cancellation gives $t=s$. This verifies the uniqueness clause in the Definition.

Choose the least coordinate $j<n$ with $s_j=1$, which exists by [F1]. For each $i\mathrm{\ne }j$, let $u^{(i)}$ have coordinate $1$ at $i$, coordinate $s_i$ at $j$, and zero elsewhere. Then $s\cdot u^{(i)}=s_i\oplus (s_j\wedge s_i)=s_i\oplus s_i=0$, so every $u^{(i)}$ belongs to $s^{\perp }$. When $n=1$, the index set $i\mathrm{\ne }j$ is empty.

For any $y\in s^{\perp }$, the equation $s\cdot y=0$ and $s_j=1$ give $y_j={⨁}_{i\mathrm{\ne }j}(s_i\wedge y_i)$; hence $y={\sum }_{i\mathrm{\ne }j}{y}_i{u}^{(i)}$, checking each coordinate. Conversely, distributing [F4] over the finite sum gives $s\cdot (\sum c_i{u}^{(i)})=\sum c_i(s\cdot u^{(i)})=0$, so the span equals $s^{\perp }$ and makes it a subspace by [F5] and [F7]. For any injective finite list $b_t=u^{(i_t)}$ from this set, the indices $i_t\mathrm{\ne }j$ are distinct, and coordinate $i_t$ of ${\sum }_r{c}_r{b}_r$ is exactly $c_t$. Thus a zero combination forces every coefficient to vanish; when the list is empty the condition is vacuous. The set is independent by [F6] and spans by [F7].

The independent spanning set from step 2.1 is a basis by [F8], and has exactly $n-1=d$ elements, so $\dim s^{\perp }=d$. Its coefficient map is bijective by the coordinate formula and independence, so $\mathrm{\mid }{s}^{\perp }\mathrm{\mid }=2^d$ because there are $2^d$ binary coefficient lists. For $n=1$, the empty list gives only $0$, and the same count is $2^0=1$.

For every nonzero $s$, the map $x\mapsto x\oplus s$ is a fixed-point-free involution, so its $2^n$ addresses split into $C=2^{n-1}$ two-element cosets. Since $m\ge n-1$, $L=2^m\ge C$, and the number of injections from a $C$-element set into an $L$-element set is $L(L-1)\cdots (L-C+1)>0$, the sample space is finite and nonempty.

Give every pair $(s,\lambda )$ weight $1\mathrm{/}((2^n-1)L(L-1)\cdots (L-C+1))$. There are exactly the denominator's many pairs, so the weights are nonnegative and sum to one by [F2]. Because the number of injections is constant for each $s$, the induced hidden mask is uniform and, conditional on it, every injection is equally likely.

If $x\oplus s=y$, the two addresses lie in the same coset and receive the same label. Conversely, if $f_{s,\lambda }(x)=f_{s,\lambda }(y)$, injectivity of $\lambda$ gives equal cosets, hence $y=x$ or $y=x\oplus s$. Since $s\mathrm{\ne }0$, this is exactly the Simon promise with unique hidden mask $s$.

The Hadamard-character formula [F14] gives $H^{\otimes n}\mathrm{\mid }{0}^n⟩=2^{-n\mathrm{/}2}{\sum }_x\mathrm{\mid }x⟩$. Applying [F2] to this vector and the zero target produces the displayed joint vector $\mathrm{\Psi }$. Its $2^n$ orthogonal terms all have squared coefficient $2^{-n}$ by [F10]–[F11], so $\mathrm{\parallel }\mathrm{\Psi }\mathrm{\parallel }=1$ and $\mathrm{\mid }\mathrm{\Psi }⟩⟨\mathrm{\Psi }\mathrm{\mid }$ is a density operator by [F15].

For each $v$, the maps in [F3] have projectors $P_v$. By [F10]–[F11], computational basis vectors are orthonormal, so the $P_v$ are self-adjoint idempotents, pairwise orthogonal, and sum to the identity. Also $⟨P_{v}z,z⟩=⟨P_{v}z,P_{v}z⟩\ge 0$, so these projectors form a POVM by [F4]–[F5]. The nonnegative square root of each projector is itself by [F6]; hence [F7] makes the branch maps a valid instrument with the probabilities and conditional states of [F8].

Fix $v$ in the image and let $x_0$ be one preimage. Set $w_v:=2^{-n\mathrm{/}2}(\mathrm{\mid }{x}_0⟩+\mathrm{\mid }{x}_0\oplus s⟩)\otimes \mathrm{\mid }v⟩$. The post-query vector projected into branch $v$ is $2^{-n\mathrm{/}2}{\sum }_{x:f(x)=v}\mathrm{\mid }x⟩\mathrm{\mid }v⟩=w_v$ by [F1]. The two address basis vectors are distinct and orthonormal by [F1] and [F11].

The branch operator is the rank-one map $\mathrm{\mid }{w}_v⟩⟨w_v\mathrm{\mid }$ for the projected vector $w_v$ in step 1.3. In the product basis its only nonzero diagonal entries are the two squared coefficients $2^{-n}$, by [F12]–[F13]. Thus the branch probability is $\mathrm{tr}(\mathrm{\mid }{w}_v⟩⟨w_v\mathrm{\mid })=2^{1-n}$. An output outside the image has zero projected vector and therefore zero trace.

Dividing the projected vector in step 1.3 by its norm $2^{(1-n)\mathrm{/}2}$ gives the normalized conditional state in the Statement; it factors into an address vector and the fixed output basis vector $\mathrm{\mid }v⟩$. Its rank-one outer product is a density operator by [F15], and its probability is positive, so it is the conditional state in [F8]. There are exactly $2^{n-1}$ image values by the fiber partition in [F1], and their probabilities sum to one as required by [F9].

Swapping two rows or replacing a row by its XOR with another preserves both the homogeneous solution set and row space: each operation has an inverse of the same form, and the new row is a combination of old rows. Thus the rank and kernel of $Y$ are preserved by [F13] and [F9]. The loops visit $n$ columns and at most $n-1$ pivot rows, with finite row scans, so they terminate.

At each pivot the selected entry is $1$, earlier pivot columns are zero below it, and XORing the pivot row clears its column in every other row. At termination the pivot columns form an identity block and all remaining rows are zero. The nonzero rows are independent because their pivot columns form an identity matrix, and they span the row space because every other row is zero. By [F13], the pivot count equals $\mathrm{rank}(Y)$; step 1.1 preserves this rank from the input. The procedure returns FAIL precisely when this rank is below $n-1$.

If the pivot count is $n-1$, there is exactly one nonpivot column. Setting its coordinate to $1$ and solving each pivot equation gives a vector in the reduced system with that coordinate nonzero. By step 1.1, it lies in the kernel of the original $Y$ and is nonzero.

Whenever $\mathrm{rank}(Y)=n-1$, the associated map has rank $n-1$ by [F10] and domain dimension $n$ by [F8]; rank-nullity [F3] gives a one-dimensional kernel. A basis of that kernel has one vector $u$, so every vector is $cu$ by [F11]; [F12] gives $c\in \{0,1\}$, hence $u$ is its unique nonzero vector. The algorithm's output from step 3.1 is therefore the unique nonzero kernel vector. In the Simon case, every row has dot product zero with $s$, so [F5] and [F9] give $s\in \ker Y$, and [F4] gives $s\mathrm{\ne }0$; thus the output is $s$.

Store the $n-1$ rows consecutively on an input work tape. To find pivots, a multitape machine may scan the whole $O(n^2)$-bit matrix once for each of at most $n$ columns; this costs $O(n^3)$ transitions including head movement. For each of at most $n-1$ pivots, copy its $n$ bits to a work tape, then scan each of at most $n-2$ other rows and XOR the copied pivot row into it when required; each scan and row update costs $O(n)$ transitions, so all row operations cost $O(n^3)$. Swaps, pivot bookkeeping, and back-substitution require at most $O(n^3)$ further transitions under the same scan representation. The finite-alphabet multitape convention [F7] therefore gives the stated $O(n^3)$ classical bit cost.

Assume, for contradiction, that $q\le \lfloor \sqrt{N}\mathrm{/}4\rfloor$. Put $S=N-1$ and $B=\left(\genfrac{}{}{0px}{}{q}{2}\right)$.

Fix one finite random tape, making the algorithm deterministic. Repeated addresses can be answered from the earlier reply and removed without changing the output, so the resulting at most $q$ queries are distinct.

The assumption in step 1.1 gives $B\le q^2\mathrm{/}2\le N\mathrm{/}32$. Hence $S-B\ge 31N\mathrm{/}32-1>0$, since $N=2^n\ge 256$.

Consider a collision-free transcript of $t\le q$ queries. A mask is inconsistent with it only if it is the XOR difference of a pair of queried addresses, so at most $\left(\genfrac{}{}{0px}{}{t}{2}\right)\le B$ masks are excluded and at least $S-B$ remain. For each remaining $s$, the queried addresses lie in distinct $s$-cosets. Write $(L{)}_t=L(L-1)\cdots (L-t+1)$, where $L=2^m$ and $C=2^{n-1}$. For a specified ordered list of $t$ distinct replies, the number of injections extending those assignments is $(L-t{)}_{C-t}$ out of $(L{)}_C$ total injections, giving likelihood $1\mathrm{/}(L{)}_t$, independent of $s$. Because the deterministic query addresses are functions of earlier replies, the transcript has the same likelihood for every consistent mask. The posterior on those masks is therefore uniform.

At the $j$th fresh query, a collision with a previous address $x_i$ requires $s=x_j\oplus x_i$. There are at most $j-1$ candidate masks, and after any collision-free transcript at least $S-B$ masks remain equally likely by step 3.1. Thus the probability that the first collision occurs at query $j$ is at most $(j-1)\mathrm{/}(S-B)$. Summing over $j=2,\dots ,q$ bounds the total collision probability by ${\sum }_{j=2}^q(j-1)\mathrm{/}(S-B)=B\mathrm{/}(S-B)$.

On a collision-free transcript, the deterministic final guess is correct with probability at most $1\mathrm{/}(S-B)$, since at least that many masks remain equally likely. On transcripts with a collision, success is at most one. Therefore average success under [F1] is at most $B\mathrm{/}(S-B)+1\mathrm{/}(S-B)=(B+1)\mathrm{/}(S-B)$.

By steps 1.1 and 2.2, with $S-B>0$, $(B+1)\mathrm{/}(S-B)\le (N\mathrm{/}32+1)\mathrm{/}(31N\mathrm{/}32-1)<2\mathrm{/}3$. The strict inequality is equivalent to $5<59N\mathrm{/}32$, which holds because $N\ge 256$. Thus every fixed random tape has average success strictly below $2\mathrm{/}3$ under the finite oracle distribution.

Averaging over the algorithm's finite random tapes keeps its average success below $2\mathrm{/}3$. But success at least $2\mathrm{/}3$ on every promised function implies average success at least $2\mathrm{/}3$ under [F1], since every function in that distribution is promised. This contradiction proves $q>\lfloor \sqrt{N}\mathrm{/}4\rfloor$ and hence the stated $\mathrm{\Omega }(2^{n\mathrm{/}2})$ lower bound.

Apply [F2] to the two terms in [F1]. The amplitude at $y$ is $2^{-(n+1)\mathrm{/}2}((-1{)}^{x_0\cdot y}+(-1{)}^{(x_0\oplus s)\cdot y})\mathrm{.}$ By [F3], $(x_0\oplus s)\cdot y=(x_0\cdot y)\oplus (s\cdot y)$.

If $s\cdot y=1$, the two signs in step 1.1 are opposites and the amplitude is zero. If $s\cdot y=0$, they agree and the amplitude is $2^{-(n-1)\mathrm{/}2}(-1{)}^{x_0\cdot y}$. Thus its squared modulus is $2^{-(n-1)}$ on every allowed $y$ and zero otherwise.

There are $2^{n-1}$ allowed strings by [F6]. The vector after the final Hadamards has squared norm $2^{n-1}{2}^{-(n-1)}=1$ by step 2.1 and orthonormality [F7]. This also covers $n=1$, when the only allowed string is $0$.

The measured vector is unit by step 3.1, so [F5] gives probability $2^{-(n-1)}$ for each allowed string and zero for every disallowed string. These weights sum to one; the phase depends on $x_0$ but the probabilities do not. Thus every fresh execution has the same uniform sample law regardless of the observed coset.

By [F1], each accepted row was outside the span of its predecessors. In a zero linear combination, if the last nonzero coefficient were $1$, that row would be a combination of its predecessors, contradicting acceptance; since the only nonzero scalar is $1$, this proves inductively that the accepted list is independent by [F6]. It spans $V_k$ by [F7], hence is a basis by [F8]. The coefficient map from ${\mathbb{F}}_2^k$ to $V_k$ is injective by independence and surjective by span; [F4] gives $2^k$ possible coefficient lists, so $\mathrm{\mid }{V}_k\mathrm{\mid }=2^k$.

By [F2]–[F3], samples are uniform on the $2^d$ elements of $s^{\perp }$, and [F1] gives $V_k\subseteq s^{\perp }$. Exactly $2^k$ lie in $V_k$ by step 1.1, so the probability the next sample is accepted is $(2^d-2^k)\mathrm{/}{2}^d=1-2^{k-d}=p_k$, while the failure probability is $q_k=2^{k-d}\le 1\mathrm{/}2$.

Condition on any rank-$k$ history and use the finite $r$-sample continuation experiment. Let $A_{k,r}$ be the event that every one of those $r$ samples lies in the current span $V_k$. On this event the span remains $V_k$ throughout; by freshness, each conditional failure probability is $q_k$, so multiplying the finite conditional probabilities gives $\mathrm{Pr}(A_{k,r})=q_k^r$. For $r=0$, $A_{k,0}$ is the whole one-outcome empty continuation and has probability $1=q_k^0$.

For each finite horizon $M$, the explicitly defined $W_{k,M}$ is a function on the finite experiment by [F9]–[F10]. For every $0\le j<M$, the event $\{W_{k,M}>j\}$ is the event $A_{k,j}$ after projection to its first $j$ samples, so $W_{k,M}={\sum }_{j=0}^{M-1}{\mathbf{1}}_{A_{k,j}}$. The expectation definition [F11] and step 3.1 give $\mathbb{E}[W_{k,M}]={\sum }_{j=0}^{M-1}{q}_k^j$. Since $0\le q_k\le 1\mathrm{/}2$, [F12] bounds these partial sums by $1\mathrm{/}(1-q_k)=1\mathrm{/}{p}_k\le 2$.