Simon’s Algorithm

Simon’s algorithm finds a hidden XOR period by collecting random linear equations. A coherent query correlates each input with its function value; a Hadamard transform then returns a word orthogonal to the period. Repeating this experiment and solving the equations over $\mathbb F_2$ recovers the hidden word.

For the promise defined below, including the possibility of an injective function, the fixed-error quantum query complexity is $\Theta(n)$, compared with $\Theta(2^{n/2})$ classical value queries. One query produces a sample, not usually the answer. The comparison counts oracle calls and excludes building the oracle and implementing its gates.

Helpful background. Quantum oracles defines coherent value access. Linear maps explains kernels and rank; here all row operations use arithmetic modulo two. Query complexity distinguishes exact, zero-error and bounded-error query caps.

The hidden XOR-period promise

Let

$$n\ge1, \qquad G=\mathbb F_2^n, \qquad N=|G|=2^n, \qquad s\in G,$$

where addition in $G$ is bitwise XOR. Define $H_s=\{0,s\}$. The oracle is selected from the family of functions $f:G\to G$ satisfying

$$f(x)=f(x') \quad\Longleftrightarrow\quad x\mathbin\oplus x'\in H_s.$$

The biconditional is the promise. It says not merely that $s$ is a period but that there are no other collisions. The required search output is the complete word $s$; the associated decision problem asks whether $s=0^n$.

The promise includes two branches. If $s=0^n$, then $H_s=\{0\}$ and $f$ is injective. If $s\ne0^n$, the fibers are exactly the two-element cosets

$$x+H_s=\{x,x\mathbin\oplus s\},$$

so $f$ is exactly two-to-one. The mask is unique: the fiber of $f(0)$ is $H_s$, and equality of two promised functions’ collision relations would force their fibers at zero, hence their masks, to agree.

Some textbook presentations promise $s\ne0$ from the outset. That restricted problem is useful for deriving the sampling pattern, but it omits the injective branch and cannot by itself justify an injective-versus-two-to-one decision claim. This page retains the unified promise throughout.

One coherent value query

The supplied oracle acts on an $n$-qubit address and an $n$-qubit value register:

$$O_f|x,z\rangle=|x,z\oplus f(x)\rangle.$$

For every $x$, XOR by $f(x)$ is a permutation and its own inverse, so this specifies a unitary on the complete space. A classical query returns the full $n$-bit value $f(x)$.

One sample uses the following steps:

1. Prepare $|0^n\rangle_X|0^n\rangle_Z$ and apply $H^{\otimes n}$ to $X$.
2. Apply $O_f$ once.
3. Apply $H^{\otimes n}$ to $X$, then measure $X$ to obtain $y$.

The value register may be measured after the query, or left unmeasured and discarded. Both choices give the same marginal distribution for $y$. It starts in zero, unlike the one-qubit minus-state target used in the preceding Boolean algorithms.

Conditional coset states and the address marginal

After address preparation and one value query, the joint state is

$$|\Psi_f\rangle = \frac1{\sqrt N}\sum_{x\in G}|x,f(x)\rangle.$$

For $s\ne0$, measuring $Z$ and obtaining the value $f(t)$ leaves

$$|t+H_s\rangle = \frac{|t\rangle+|t\mathbin\oplus s\rangle}{\sqrt2}$$

in the address register. The probability of each distinct oracle value is $2/N$, and the representative $t$ is irrelevant up to its coset. In the injective branch, measuring $Z$ leaves a single basis state $|t\rangle$.

The output measurement is optional. If $Z$ is ignored, the probability of measuring $y$ after the final Hadamards is

$$\begin{aligned} p(y) &= \left\langle y\middle| H^{\otimes n}\operatorname{Tr}_Z \bigl(|\Psi_f\rangle\langle\Psi_f|\bigr) H^{\otimes n} \middle|y\right\rangle\\ &= \frac1{N^2} \sum_{\substack{x,x'\\ f(x)=f(x')}} (-1)^{(x\oplus x')\cdot y}. \end{aligned}$$

Only equal-output pairs survive the partial trace. For a nonzero mask, each $x$ contributes the two differences $0$ and $s$, giving

$$p(y) = \frac1N\left[1+(-1)^{s\cdot y}\right].$$

This equals $2/N$ when $s\cdot y=0$ and zero otherwise. For $s=0$, only $x=x'$ survives, so $p(y)=1/N$ for every $y$. Measuring the value register reveals a convenient conditional coset state; it does not create the period relation or change the address marginal.

Fourier samples orthogonal to the period

The $n$-fold Hadamard transform is the Fourier transform over the product group $(\mathbb Z_2)^n$:

$$H^{\otimes n}|x\rangle = \frac1{\sqrt N} \sum_{y\in G}(-1)^{x\cdot y}|y\rangle, \qquad x\cdot y=\bigoplus_{j=1}^n x_jy_j.$$

Applying it to a nontrivial coset state gives

$$\begin{aligned} H^{\otimes n}|t+H_s\rangle &= \frac1{\sqrt{2N}}\sum_y \left[ (-1)^{t\cdot y} +(-1)^{(t\oplus s)\cdot y} \right]|y\rangle\\ &= \frac1{\sqrt{2N}}\sum_y (-1)^{t\cdot y} \left[1+(-1)^{s\cdot y}\right]|y\rangle\\ &= \sqrt{\frac2N} \sum_{y:s\cdot y=0} (-1)^{t\cdot y}|y\rangle. \end{aligned}$$

Character cancellation removes every $y$ with $s\cdot y=1$. Define the annihilator

$$H_s^\perp = \{y\in G:y\cdot h=0\text{ for every }h\in H_s\}.$$

Both promise branches are then summarized by

$$\Pr(Y=y) = \begin{cases} |H_s|/N,&y\in H_s^\perp,\\ 0,&y\notin H_s^\perp. \end{cases}$$

For $s\ne0$, $H_s^\perp=s^\perp$ has dimension $n-1$ and contains $N/2$ words, each with probability $2/N$. For $s=0$, it is all of $G$ and each word has probability $1/N$. Each sample supplies one homogeneous binary equation $y\cdot s=0$; it does not normally determine $s$ by itself.

The transform here is not the cyclic $F_{2^n}$ circuit used in number-theoretic phase and period estimation. The distinction is structural: $(\mathbb Z_2)^n$ has binary characters implemented by independent Hadamards.

A three-bit example with $s=101$: $f(x_1x_2x_3)=(x_2,x_1\oplus x_3,0)$. Each input pair shares one value. Fourier sampling gives $y=000,010,101,111$, each with probability $1/4$; all satisfy $y\cdot101=0$. The zero sample is allowed and adds no equation.

Binary rank and candidate verification

Place retained samples into a binary matrix

$$M= \begin{pmatrix} y_1^{\mathsf T}\\ \vdots\\ y_m^{\mathsf T} \end{pmatrix}.$$

For a nonzero mask, every row lies in $s^\perp$. Once $\operatorname{rank}M=n-1$, the nullspace is the two-element set $\{0,t\}$ for a unique nonzero word $t$. Under the nonzero branch alone, $t=s$. Under the unified promise, the injective branch can also happen to produce a rank-$(n-1)$ matrix, so the candidate must be checked:

$$\widehat s= \begin{cases} t,&f(0^n)=f(t),\\ 0^n,&f(0^n)\ne f(t). \end{cases}$$

The biconditional promise makes this decisive. Equality for nonzero $t$ means $t=s$; inequality rules out $t$ and therefore identifies the injective branch once the sample span has codimension at most one.

If $m\ge d$ vectors are sampled independently and uniformly from a $d$-dimensional binary space, the probability of spanning it is

$$P_{d,m} = \prod_{r=0}^{d-1}\left(1-2^{r-m}\right).$$

For $m<d$, spanning is impossible; for $d=0$, the empty product is one. One way to derive the displayed formula is to transpose the $m$ samples into a $d\times m$ matrix. Its first row must avoid the zero span, its second must avoid a one-dimensional span, and so on. The failure probability obeys

$$\begin{aligned} 1-P_{d,m} &\le \sum_{r=0}^{d-1}2^{r-m} = 2^{d-m}-2^{-m} <2^{d-m}. \end{aligned}$$

When the current span has rank $r<d$, a fresh sample increases the rank with probability $1-2^{r-d}$. Summing the corresponding geometric waiting times gives

$$\begin{aligned} \mathbb E T_d &= \sum_{r=0}^{d-1}\frac1{1-2^{r-d}}\\ &= d+\sum_{k=1}^{d}\frac1{2^k-1} <d+1.607. \end{aligned}$$

These are exact sampling laws. Row reduction must still be performed over $\mathbb F_2$, not over the real numbers, and a verifier call remains part of the executable algorithm.

Expected stopping, query caps and exact algorithms

Different stopping conventions support different complexity claims.

Expected stopping. Repeatedly sample until the row rank reaches $n-1$, compute the nonzero null vector, and verify it. In the nonzero branch the expected sample count is below $n+0.607$ because $d=n-1$; the two verifier calls give an always-correct expected $O(n)$-query procedure. In the injective branch, this rule also reaches rank $n-1$ in finite expected time and the verifier returns zero. It has no deterministic query cap.

Fixed-cap zero error. Take $m=n$ Fourier samples. Return zero immediately at rank $n$; at rank $n-1$, verify the unique nonzero null vector; below rank $n-1$, return ?. For a nonzero mask, the failure bound with $d=n-1$ is below $1/2$. For the injective branch, dependence among the first $n-1$ samples has probability at most

$$\sum_{r=0}^{n-2}2^{r-n} = \frac12-2^{-n},$$

so the inconclusive probability is also below $1/2$. The deterministic cap is $n+2$ value queries.

Fixed-cap bounded error. Take $m=n+1$ samples, use the same rank and verifier rules, and return zero on an unresolved lower-rank outcome. The injective branch is always correct. In the nonzero branch the failure probability is below

$$2^{(n-1)-(n+1)}=\frac14.$$

The cap is $n+3$ queries, already below the conventional $1/3$ error threshold.

A separate exact algorithm. The random-rank loop is not an exact fixed-cap algorithm. Brassard and Høyer gave a separate construction that forces a new independent annihilator element, or certifies that none remains, using exact amplification; their formulation includes the trivial subgroup, and their Section 4.3 reduces the total number of function evaluations to $O(n)$. Cai and Qiu later supplied another optimal exact ordinary-oracle construction for the restricted nonzero-mask problem. It must not be applied silently to the $s=0$ branch. Together with the transparent zero-error and bounded-error procedures, the applicable upper bounds are $O(n)$.

For the associated injective-versus-two-to-one decision problem, Koiran, Nesme, and Portier proved, for sufficiently large $n$,

$$T(n) \ge \frac{n+2+\log_2(2-4\varepsilon)}8 \qquad (0\le\varepsilon<1/2).$$

A full-mask search procedure also solves the decision problem. For zero error, replacing an inconclusive result of probability at most $1/2$ by an independent fair decision bit produces error at most $1/4$, so the lower bound transfers under the fixed-cap convention. Consequently, for every fixed $\varepsilon<1/2$,

$$\begin{aligned} Q_E(\operatorname{Simon}_n)&=\Theta(n)=\Theta(\log N),\\ Q_0(\operatorname{Simon}_n)&=\Theta(n)=\Theta(\log N),\\ Q_\varepsilon(\operatorname{Simon}_n)&=\Theta(n)=\Theta(\log N). \end{aligned}$$

The equality is asymptotic. The explicit $n+2$ and $n+3$ caps above belong to the transparent verifier-based procedures, not to the cited exact construction’s optimized constants.

Classical collisions and difference covers

A classical query returns one complete value $f(x)$. Under a nonzero mask, the first observed collision identifies it:

$$f(x)=f(x'), \qquad x\ne x', \quad\Longrightarrow\quad s=x\mathbin\oplus x'.$$

An exact deterministic schedule follows from a difference cover. Write $n=a+b$ with $a=\lfloor n/2\rfloor$ and query every address in

$$A=\{(u,0^b):u\in\mathbb F_2^a\}, \qquad B=\{(0^a,v):v\in\mathbb F_2^b\}.$$

Their intersection is $\{0^n\}$. Every nonzero $s=(u,v)$ equals $(u,0^b)\oplus(0^a,v)$, so a hidden mask forces a collision among the queried addresses. No collision proves the injective branch. Hence

$$D(\operatorname{Simon}_n) \le 2^{\lfloor n/2\rfloor} +2^{\lceil n/2\rceil} -1.$$

Conversely, $q$ queried addresses determine at most $\binom q2$ nonzero pairwise XOR differences. If some nonzero word is missing, an injective transcript can be completed either as an injective oracle or as a two-to-one oracle with that hidden mask, so an exact algorithm cannot distinguish them. Therefore

$$\binom q2\ge N-1, \qquad D(\operatorname{Simon}_n) \ge \left\lceil \frac{1+\sqrt{8N-7}}2 \right\rceil.$$

Random queries give the matched bounded-error upper bound. For a fixed nonzero mask, the domain is partitioned into $N/2$ pairs. Sampling $q\le N/2$ distinct addresses without seeing both members of any pair has probability

$$p_{\mathrm{miss}}(N,q) = \frac{2^q\binom{N/2}{q}}{\binom Nq}.$$

The numerator chooses $q$ distinct pairs and one endpoint from each. Choosing $q=\Theta(\sqrt N)$ makes the miss probability a fixed constant below one; a collision returns its XOR difference, while no collision returns zero.

For a lower bound, mix a uniformly random injective oracle with equal probability against an oracle with a uniformly random nonzero mask and random distinct fiber labels. Until a collision, their distinct output transcripts can be coupled. The queried addresses expose at most $\binom q2$ candidate masks, so any depth-$q$ deterministic decision tree has distributional success at most

$$\frac12+\frac{\binom q2}{2(N-1)}.$$

Yao’s minimax principle then gives $\Omega(\sqrt N)$ randomized query complexity for the associated decision task at every fixed error below $1/2$. Any full-mask search algorithm decides whether $s=0^n$, so the lower bound transfers to search. A randomized fixed-cap procedure at $\varepsilon=0$ cannot use random coins to evade the exact worst-case difference-cover requirement. Thus, for every fixed $0\le\varepsilon<1/2$,

$$\begin{aligned} D(\operatorname{Simon}_n)&=\Theta(2^{n/2})=\Theta(\sqrt N),\\ R_\varepsilon(\operatorname{Simon}_n) &=\Theta(2^{n/2})=\Theta(\sqrt N). \end{aligned}$$

Four-bit worked calculations

Input pairs and the recovered mask

Take $n=4$, $s=1011$, and, with $x_1$ the most significant bit,

$$f(x_1x_2x_3x_4) = (x_2,\ x_1\oplus x_3,\ x_1\oplus x_4,\ 0).$$

Its kernel is $\{0000,1011\}$, and exhaustive evaluation gives:

Inputs	Output
0000, 1011	0000
0001, 1010	0010
0010, 1001	0100
0011, 1000	0110
0100, 1111	1000
0101, 1110	1010
0110, 1101	1100
0111, 1100	1110

The exact Fourier support is

0000  0011  0100  0111  1001  1010  1101  1110

with probability $1/8$ on every listed word and zero elsewhere. The independent rows 0011, 0100, and 1001 have nullspace $\{0000,1011\}$.

How many samples or classical queries?

For a three-dimensional sample space, exact enumeration of all $8^m$ ordered sequences gives:

$m$	Fraction spanning	$P_{3,m}$
3	$168/512$	$21/64$
4	$2520/4096$	$315/512$
5	$26040/32768$	$3255/4096$

The expected spanning time is

$$\mathbb E T_3 = \frac87+\frac43+2 = \frac{94}{21}.$$

For $q=4,5,6$ uniformly selected distinct addresses at $N=16$,

$$p_{\mathrm{miss}}(16,4)=\frac8{13}, \qquad p_{\mathrm{miss}}(16,5)=\frac{16}{39}, \qquad p_{\mathrm{miss}}(16,6)=\frac{32}{143}.$$

The six-query collision probability is therefore $111/143>2/3$. Exact recovery needs six queries as well: the pair-count lower bound gives $\binom q2\ge15$, and

$$C=\{0000,1000,0100,0010,0001,1111\}$$

has every nonzero four-bit word among its fifteen pairwise XOR differences. Thus $D(\operatorname{Simon}_4)=6$. For $s=1011$, the cover contains the colliding pair 0100 and 1111.

Gate costs and the hidden-subgroup viewpoint

Each Fourier sample needs one query, $2n$ visible qubits, $2n$ Hadamards and measurement of the $n$ address qubits. Registers must be reinitialized before the next sample. With $O(n)$ rows, straightforward binary elimination uses $O(n^3)$ bit operations and $O(n^2)$ memory. The verifier adds at most two value queries; oracle workspace and implementation costs remain additional.

The exponential query comparison is a worst-case result over the promised family. The linear function in the worked example has a transparent description: if that description is available, a classical algorithm can inspect its kernel directly. It is not then restricted to learning through unknown function values. Similarly, an ordinary classical API does not automatically supply the coherent oracle required by the quantum algorithm.

The group is $(\mathbb Z_2)^n$, and the hidden subgroup is $H_s=\{0,s\}$. Coset sampling followed by Fourier sampling extracts characters trivial on that subgroup. This viewpoint helped motivate later algorithms, including Shor’s algorithm, whose cyclic period finding and number-theoretic reductions need their own analysis. Simon’s oracle lower bound does not become a classical factoring lower bound or prove BQP $\ne$ BPP; see quantum complexity classes.

The ideal sample equations and the verifier rely on the full collision promise. With noisy or off-promise data, a null vector alone does not establish a period. A noise model and a suitable statistical recovery procedure must replace the exact reasoning.

Exercises

Uniqueness and the two promise branches

Prove that the mask $s$ is unique. Then derive the injective branch for $s=0$ and the exact two-to-one coset structure for $s\ne0$.

Solution

The fiber of $f(0)$ is

$$\{x:f(x)=f(0)\} = \{x:x\oplus0\in\{0,s\}\} = \{0,s\}.$$

If the same collision relation had masks $s$ and $t$, these fibers would obey $\{0,s\}=\{0,t\}$, hence $s=t$. When $s=0$, equality of outputs implies $x\oplus x'=0$ and therefore $x=x'$, so $f$ is injective. When $s\ne0$, each $x$ shares its value exactly with $x\oplus s$, and the two addresses are distinct. The fibers are therefore the two-element cosets of $\{0,s\}$.

Full-space action and optional measurement

Show that $O_f$ is unitary on the whole computational basis. Starting from $|\Psi_f\rangle$, derive the address distribution without measuring the value register and compare it with the conditional-coset derivation.

Solution

For each fixed $x$, the map $z\mapsto z\oplus f(x)$ is a permutation and its own inverse. The full basis map is therefore a permutation, so $O_f$ is unitary and $O_f^\dagger=O_f$.

Tracing out $Z$ gives

$$\rho_X = \frac1N \sum_{\substack{x,x'\\f(x)=f(x')}}|x\rangle\langle x'|.$$

After $H^{\otimes n}$,

$$p(y) = \frac1{N^2} \sum_{\substack{x,x'\\f(x)=f(x')}} (-1)^{(x\oplus x')\cdot y}.$$

For $s\ne0$, each $x$ has equal-output partners $x$ and $x\oplus s$, so $p(y)=N^{-1}[1+(-1)^{s\cdot y}]$. This is $2/N$ on $s^\perp$ and zero elsewhere, exactly the distribution obtained by first conditioning on any coset state. For $s=0$, only diagonal pairs remain and $p(y)=1/N$.

Character cancellation

Derive the Hadamard transform of $|t+H_s\rangle$ and prove that the result is uniform on $H_s^\perp$. Include the $s=0$ branch.

Solution

For $s\ne0$,

$$\begin{aligned} H^{\otimes n}|t+H_s\rangle &= \frac1{\sqrt{2N}}\sum_y (-1)^{t\cdot y} \left[1+(-1)^{s\cdot y}\right]|y\rangle\\ &= \sqrt{\frac2N} \sum_{y:s\cdot y=0} (-1)^{t\cdot y}|y\rangle. \end{aligned}$$

There are $N/2$ supported words and every squared amplitude is $2/N$, so the distribution is normalized and uniform. If $s=0$, a measured output selects one basis state $|t\rangle$ because $f$ is injective. Its Hadamard transform has amplitude magnitude $1/\sqrt N$ at every $y$, which is the same rule with $H_0^\perp=G$ and $|H_0|=1$.

Recover the four-bit mask

For the displayed $n=4$ function, reproduce all fibers, the eight-point Fourier support, and the nullspace of rows 0011, 0100, and 1001.

Solution

Evaluating the four output coordinates gives the eight pairs in the worked example, each separated by

$$1011.$$

The equal-output character sum is

$$\sum_{\substack{x,x'\\f(x)=f(x')}} (-1)^{(x\oplus x')\cdot y} = 16\left[1+(-1)^{1011\cdot y}\right],$$

so it is $32$ on words orthogonal to 1011 and zero otherwise. Dividing by $N^2=256$ gives probability $1/8$ on

0000  0011  0100  0111  1001  1010  1101  1110

The three chosen equations are independent. Solving them over $\mathbb F_2$ leaves one free bit and gives precisely $t=0000$ or $t=1011$.

Rank probability and expected stopping

Derive $P_{d,m}$, its failure bound, and $\mathbb E T_d$. Evaluate the three probabilities and the expected time for $d=3$, and explain why the row reduction must use binary arithmetic.

Solution

A $d\times m$ binary matrix has full row rank when its ordered rows successively avoid spans of sizes $1,2,\ldots,2^{d-1}$. Out of $2^m$ possible rows at each step,

$$P_{d,m} = \prod_{r=0}^{d-1}\frac{2^m-2^r}{2^m} = \prod_{r=0}^{d-1}(1-2^{r-m}).$$

A union bound over the failed independence steps gives

$$1-P_{d,m} \le \sum_{r=0}^{d-1}2^{r-m} <2^{d-m}.$$

At rank $r$, the probability of increasing rank is $1-2^{r-d}$, so

$$\mathbb E T_d = \sum_{r=0}^{d-1}\frac1{1-2^{r-d}} = d+\sum_{k=1}^d\frac1{2^k-1}.$$

For $d=3$, the products give $21/64$, $315/512$, and $3255/4096$ at $m=3,4,5$, while

$$\mathbb E T_3 = \frac87+\frac43+2 = \frac{94}{21}.$$

This is the finite-field instance of the kernel, image, rank, and rank–nullity language developed in Mathematical Toolkit Linear Maps. The present exercise specializes that structure to row reduction over $\mathbb F_2$.

The birthday comparator

Derive the exact no-collision probability for $q$ distinct random addresses and explain why it gives an $O(\sqrt N)$ bounded-error algorithm.

Solution

For fixed nonzero $s$, the $N$ addresses form $N/2$ disjoint pairs. A collision-free $q$-subset chooses $q$ of those pairs and one of two endpoints in each, so the number of favorable subsets is $2^q\binom{N/2}{q}$. Dividing by all $\binom Nq$ subsets gives

$$p_{\mathrm{miss}}(N,q) = \frac{2^q\binom{N/2}{q}}{\binom Nq}.$$

Equivalently,

$$p_{\mathrm{miss}}(N,q) = \prod_{j=0}^{q-1}\frac{N-2j}{N-j}.$$

For $q=c\sqrt N$, its logarithm is bounded above by

$$-\sum_{j=0}^{q-1}\frac{j}{N-j} = -\Theta(c^2),$$

so a sufficiently large constant $c$ makes the miss probability at most any fixed error. A collision reveals $s$; without one the procedure returns zero.

Deterministic lower and upper bounds

Prove the pairwise-difference lower bound and split-subspace upper bound. Then establish $D(\operatorname{Simon}_4)=6$.

Solution

With $q$ queried addresses, at most $\binom q2$ nonzero XOR differences have been exposed. If this is less than $N-1$, some nonzero $s$ is absent, and a collision-free transcript is compatible with both an injective oracle and a promised oracle having mask $s$. Thus

$$\binom q2\ge N-1.$$

For the upper bound, query

$$A=\mathbb F_2^{\lfloor n/2\rfloor}\times\{0\}, \qquad B=\{0\}\times\mathbb F_2^{\lceil n/2\rceil}.$$

Every $s=(u,v)$ is the difference of $(u,0)\in A$ and $(0,v)\in B$, and the union has $2^{\lfloor n/2\rfloor}+2^{\lceil n/2\rceil}-1$ elements.

At $n=4$, the lower bound requires $\binom q2\ge15$, hence $q\ge6$. The set

$$\{0000,1000,0100,0010,0001,1111\}$$

has six elements and fifteen distinct nonzero pairwise XOR differences, so it attains the bound. Therefore $D(\operatorname{Simon}_4)=6$.

Why verification needs enough independent equations

In the three-bit example from the figure, suppose the only independent sample is $y=010$. List the possible null words. If you test $t=001$ and find $f(t)\ne f(000)$, may you conclude that the function is injective?

Solution

The equation is $s_2=0$, so the nullspace contains $000,001,100,101$. Testing $t=001$ gives $f(001)=010\ne000=f(000)$, although the true period is $101$. This excludes only the tested candidate. Once the row rank is $n-1$, there is just one nonzero null word and a failed test excludes every nonzero period allowed by the samples. Below that rank, other candidates remain. Conversely, under the promise, any nonzero $t$ with $f(t)=f(0)$ establishes the period immediately, regardless of the sample rank.

References

• G. Brassard and P. Høyer, “An Exact Quantum Polynomial-Time Algorithm for Simon’s Problem,” Proceedings of the Fifth Israeli Symposium on Theory of Computing and Systems, 12–23 (1997), doi:10.1109/ISTCS.1997.595153.
• G. Cai and D. Qiu, “Optimal Separation in Exact Query Complexities for Simon’s Problem,” Journal of Computer and System Sciences 97, 83–93 (2018), doi:10.1016/j.jcss.2018.05.001.
• A. M. Childs and W. van Dam, “Quantum Algorithms for Algebraic Problems,” Reviews of Modern Physics 82, 1–52 (2010), doi:10.1103/RevModPhys.82.1.
• P. Koiran, V. Nesme, and N. Portier, “A Quantum Lower Bound for the Query Complexity of Simon’s Problem,” Automata, Languages and Programming, LNCS 3580, 1287–1298 (2005), doi:10.1007/11523468_104.
• A. Nayak, “Deterministic Algorithms for the Hidden Subgroup Problem,” Quantum Information and Computation 22, 755–769 (2022), doi:10.26421/QIC22.9-10-3.
• M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information, 10th Anniversary Edition, Cambridge University Press (2010), doi:10.1017/CBO9780511976667.
• D. R. Simon, “On the Power of Quantum Computation,” Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 116–123 (1994), doi:10.1109/SFCS.1994.365701.
• D. R. Simon, “On the Power of Quantum Computation,” SIAM Journal on Computing 26, 1474–1483 (1997), doi:10.1137/S0097539796298637.