Simon's problem

In the computational complexity theory and quantum computing, Simon's problem is a computational problem that can be solved exponentially faster on a quantum computer than on a classical (or traditional) computer. Although the problem itself is of little practical value, it can be proved that a quantum algorithm can solve this problem exponentially faster than any known classical algorithm.[1]

The problem is set in the model of decision tree complexity or query complexity and was conceived by Daniel Simon in 1994.[2] Simon exhibited a quantum algorithm, usually called Simon's algorithm, that solves the problem exponentially faster than any deterministic or probabilistic classical algorithm, requiring exponentially less computation time (or more precisely, queries) than the best classical probabilistic algorithm.

This problem yields an oracle separation[clarification needed] between the complexity classes BPP and BQP, unlike the separation provided by the Deutsch–Jozsa algorithm, which separates P and EQP.

Simon's algorithm was also the inspiration for Shor's algorithm[citation needed]. Both problems are special cases of the Abelian hidden subgroup problem, which is now known to have efficient quantum algorithms.

Problem description

Given a function (implemented by a black box or oracle) ${\displaystyle f:\{0,1\}^{n}\rightarrow \{0,1\}^{n}}$, promised to satisfy the property that, for some ${\displaystyle s\in \{0,1\}^{n}}$, we have, for all ${\displaystyle x,y\in \{0,1\}^{n}}$,

${\displaystyle f(x)=f(y)}$ if and only if ${\displaystyle x\oplus y\in \{0^{n},s\}}$

In the case ${\displaystyle x\oplus y=0^{n}}$, then ${\displaystyle f}$ is required to be a one-to-one function (otherwise it is a two-to-one function, that is, two inputs map to the same output). Note that ${\displaystyle x\oplus y=0^{n}}$ if and only if ${\displaystyle x=y}$.

So, in other words, ${\displaystyle f}$ is a function such that ${\displaystyle f(x)=f(x\oplus s)}$, for all ${\displaystyle x\in \{0,1\}^{n}}$ and given some fixed and unknown ${\displaystyle s\in \{0,1\}^{n}}$.

The problem is to find ${\displaystyle s}$.

Example

For example, if ${\displaystyle n=3}$, then the following function is an example of a function that satisfies the required and just mentioned property:

${\displaystyle x}$ ${\displaystyle f(x)}$
000 101
001 010
010 000
011 110
100 000
101 110
110 101
111 010

In this case, ${\displaystyle s=110}$ (i.e. the solution). It can easily be verified that every output of ${\displaystyle f}$ occurs twice, and the two input strings corresponding to any one given output have bitwise XOR equal to ${\displaystyle s=110}$. For example, the input strings ${\displaystyle 010}$ and ${\displaystyle 100}$ are both mapped (by ${\displaystyle f}$) to the same output string ${\displaystyle 000}$. If we XOR ${\displaystyle 010}$ and ${\displaystyle 100}$ we obtain ${\displaystyle s}$, that is

${\displaystyle 010\oplus 100=110=s}$.

Note that, in this example, the function ${\displaystyle f}$ is indeed a two-to-one function.

Problem hardness

Intuitively, this is a very hard problem to solve in a "classical" way, even if one uses randomness and accepts a small probability of error. The intuition behind the hardness is reasonably simple: if you want to solve the problem classically, you need to find two different inputs ${\displaystyle x}$ and ${\displaystyle y}$ for which ${\displaystyle f(x)=f(y)}$. There is not necessarily any structure in the function ${\displaystyle f}$ that would help us to find two such inputs: more specifically, we can discover something about ${\displaystyle f}$ (or what it does) only when, for two different inputs, we obtain the same output. In any case, we would need to guess ${\displaystyle \Omega ({\sqrt {2^{n}}})}$ different inputs before being likely to find a pair on which ${\displaystyle f}$ takes the same output.

Overview of Simon's algorithm

Idea

The high-level idea behind Simon's algorithm is to "probe" (or "sample") a quantum circuit (see the picture below) "enough times" to find ${\displaystyle n-1}$ (linearly independent) n-bit strings, that is

${\displaystyle y_{1},y_{2},\dots ,y_{n-1}\in \{0,1\}^{n},}$

such that the following equations are satisfied

{\displaystyle \left\{{\begin{aligned}y_{1}\cdot s&=0\\y_{2}\cdot s&=0\\&\,\,\,\vdots \\y_{n-1}\cdot s&=0\end{aligned}}\right.}

where ${\displaystyle y_{i}\cdot s=y_{i1}s_{1}+y_{i2}s_{2}+\dots +y_{in}s_{n}}$, and ${\displaystyle y_{ij},s_{j}\in \{0,1\}}$, for ${\displaystyle i=1,\dots ,n-1}$ and for ${\displaystyle j=1,\dots ,n}$.

So, this linear system contains ${\displaystyle n-1}$ linear equations in ${\displaystyle n}$ unknowns (i.e. the bits of ${\displaystyle s\in \{0,1\}^{n}}$), and the goal is to solve it to obtain ${\displaystyle s}$. Note that ${\displaystyle s}$ is fixed for a given function ${\displaystyle f}$. Note also that we may not find a (unique) solution.

Simon's quantum circuit

Quantum circuit representing/implementing Simon's algorithm

The quantum circuit (see the picture) is the implementation (and visualization) of the quantum part of Simon's algorithm.

A quantum state of all zeros is first prepared (this can easily be done). Half of this state is then transformed using a Hadamard transform. The result is then fed into an "oracle" (or "black box"), which knows how to compute ${\displaystyle f}$. After that, part of the output produced by the "oracle" is transformed using another Hadamard transform. Finally, a measurement on the overall resulting quantum state is performed. It is during this measurement that we retrieve the n-bit strings, ${\displaystyle y_{1},y_{2},\dots ,y_{n-1}\in \{0,1\}^{n}}$, mentioned in the previous sub-section.

Simon's algorithm can be thought of as an iterative algorithm (which makes use of a quantum circuit) followed by a (possibly) "classical" algorithm to find the solution to a linear system of equations.

Simon's algorithm

In this section, each part of Simon's algorithm is explained (in detail). It may be useful to look at the picture of Simon's quantum circuit above while reading each of the following sub-sections.

Input

Simon's algorithm starts with the input ${\displaystyle |0^{n}\rangle \otimes |0^{n}\rangle =|0^{n}\rangle |0^{n}\rangle }$, where ${\displaystyle |0^{n}\rangle }$ is the quantum state with ${\displaystyle n}$ zeros.

(The symbol ${\displaystyle \otimes }$ is the typical symbol used to represent the tensor product. To not clutter the notation, the symbol ${\displaystyle \otimes }$ is sometimes omitted: for example, in the previous sentence, ${\displaystyle |0^{n}\rangle \otimes |0^{n}\rangle }$ is equivalent to ${\displaystyle |0^{n}\rangle |0^{n}\rangle }$. In this article, it is (often) used to remove ambiguity or to avoid confusion.)

Example

So, for example, if ${\displaystyle n=2}$, then the initial input is

${\displaystyle |0^{2}\rangle \otimes |0^{2}\rangle =|00\rangle \otimes |00\rangle =(|0\rangle \otimes |0\rangle )\otimes (|0\rangle \otimes |0\rangle )=|0\rangle \otimes |0\rangle \otimes |0\rangle \otimes |0\rangle =|0000\rangle }$.

After that, the input (as described in the previous sub-section) is transformed using a Hadamard transform. Specifically, the Hadamard transform ${\displaystyle H^{\otimes n}}$ (note that the tensor product can also be applied to matrices) is applied to the first ${\displaystyle n}$ qubits, that is, to the "partial" state ${\displaystyle |0^{n}\rangle }$, so that the composite state after this operation is

${\displaystyle |\Psi \rangle =\left(H^{\otimes n}|0^{n}\rangle \right)\otimes |0^{n}\rangle =\left(\sum _{x\in \{0,1\}^{n}}{\frac {1}{\sqrt {2^{n}}}}\left|x\right\rangle \right)\otimes \left|0^{n}\right\rangle =\left({\frac {1}{\sqrt {2^{n}}}}\sum _{x\in \{0,1\}^{n}}\left|x\right\rangle \right)\otimes \left|0^{n}\right\rangle ={\frac {1}{2^{\frac {n}{2}}}}\sum _{x\in \{0,1\}^{n}}\left(\left|x\right\rangle \otimes \left|0^{n}\right\rangle \right)}$

where ${\displaystyle x\in \{0,1\}^{n}}$ denotes any n-bit string (i.e. the summation is over any n-bit string). The term ${\displaystyle {\frac {1}{\sqrt {2^{n}}}}}$ can be factored out of the summation because it does not depend on ${\displaystyle x}$ (i.e. it is a constant with respect to ${\displaystyle x}$). Note that ${\displaystyle {\frac {1}{\sqrt {2^{n}}}}={\frac {1}{2^{\frac {n}{2}}}}}$.

Example

Suppose (again) ${\displaystyle n=2}$, then the input is ${\displaystyle |0000\rangle }$ and the Hadamard transform ${\displaystyle H^{\otimes 2}}$ is

${\displaystyle H^{\otimes 2}={\frac {1}{\sqrt {2}}}{\begin{bmatrix}1&1\\1&-1\end{bmatrix}}\otimes {\frac {1}{\sqrt {2}}}{\begin{bmatrix}1&1\\1&-1\end{bmatrix}}={\frac {1}{\sqrt {2}}}{\begin{bmatrix}{\frac {1}{\sqrt {2}}}{\begin{bmatrix}1&1\\1&-1\end{bmatrix}}&{\frac {1}{\sqrt {2}}}{\begin{bmatrix}1&1\\1&-1\end{bmatrix}}\\{\frac {1}{\sqrt {2}}}{\begin{bmatrix}1&1\\1&-1\end{bmatrix}}&-\left({\frac {1}{\sqrt {2}}}{\begin{bmatrix}1&1\\1&-1\end{bmatrix}}\right)\end{bmatrix}}={\frac {1}{2}}{\begin{bmatrix}1&1&1&1\\1&-1&1&-1\\1&1&-1&-1\\1&-1&-1&1\end{bmatrix}}}$

If we now apply ${\displaystyle H^{\otimes 2}}$ to the first ${\displaystyle |00\rangle }$, i.e. to the state

${\displaystyle |00\rangle ={\begin{bmatrix}1\\0\\0\\0\end{bmatrix}}}$

we obtain

{\displaystyle {\begin{aligned}H^{\otimes 2}|00\rangle &={\frac {1}{2}}{\begin{bmatrix}1&1&1&1\\1&-1&1&-1\\1&1&-1&-1\\1&-1&-1&1\end{bmatrix}}{\begin{bmatrix}1\\0\\0\\0\end{bmatrix}}={\frac {1}{2}}{\begin{bmatrix}1\\1\\1\\1\end{bmatrix}}\\[6pt]&={\frac {1}{2}}\left({\begin{bmatrix}1\\0\\0\\0\end{bmatrix}}+{\begin{bmatrix}0\\1\\0\\0\end{bmatrix}}+{\begin{bmatrix}0\\0\\1\\0\end{bmatrix}}+{\begin{bmatrix}0\\0\\0\\1\end{bmatrix}}\right)={\frac {1}{2}}\left(|00\rangle +|01\rangle +|10\rangle +|11\rangle \right)={\frac {1}{2^{2/2}}}\sum _{x\in \{0,1\}^{2}}\left|x\right\rangle \end{aligned}}}

To obtain the final composite quantum state, we can now tensor product ${\displaystyle H^{\otimes 2}|00\rangle }$ with ${\displaystyle |00\rangle }$, that is

{\displaystyle {\begin{aligned}\left(H^{\otimes 2}|00\rangle \right)\otimes |00\rangle &=\left({\frac {1}{2}}\sum _{x\in \{0,1\}^{2}}\left|x\right\rangle \right)\otimes |00\rangle ={\frac {1}{2}}\left(|00\rangle +|01\rangle +|10\rangle +|11\rangle \right)\otimes |00\rangle \\[6pt]&={\frac {1}{2}}\left(|00\rangle \otimes |00\rangle +|01\rangle \otimes |00\rangle +|10\rangle \otimes |00\rangle +|11\rangle \otimes |00\rangle \right)={\frac {1}{2}}\sum _{x\in \{0,1\}^{2}}\left(\left|x\right\rangle \otimes |00\rangle \right).\end{aligned}}}

Oracle

We then call the oracle or black-box (${\displaystyle U_{f}}$ in the picture above) to compute the function ${\displaystyle f}$ on the transformed input ${\displaystyle |\Psi \rangle ={\frac {1}{2^{n/2}}}\sum _{x\in \{0,1\}^{n}}\left(\left|x\right\rangle \otimes \left|0^{n}\right\rangle \right)}$, to obtain the state

${\displaystyle |\Psi \rangle '={\frac {1}{2^{n/2}}}\sum _{x\in \{0,1\}^{n}}\left(\left|x\right\rangle \otimes \left|f(x)\right\rangle \right)}$

We then apply the Hadamard transform ${\displaystyle H^{\otimes n}}$ to the states of the first ${\displaystyle n}$ qubits of the state ${\displaystyle |\Psi \rangle '}$, to obtain

{\displaystyle {\begin{aligned}|\Psi \rangle ''&={\frac {1}{2^{n/2}}}\sum _{x\in \{0,1\}^{n}}\left(\left(H^{\otimes n}\left|x\right\rangle \right)\otimes \left|f(x)\right\rangle \right)\\[4pt]&={\frac {1}{2^{n/2}}}\sum _{x\in \{0,1\}^{n}}\left(\left({\frac {1}{2^{n/2}}}\sum _{y\in \{0,1\}^{n}}(-1)^{x\cdot y}\left|y\right\rangle \right)\otimes \left|f(x)\right\rangle \right)={\frac {1}{2^{n}}}\sum _{x\in \{0,1\}^{n}}\left(\sum _{y\in \{0,1\}^{n}}\left((-1)^{x\cdot y}\left|y\right\rangle \otimes \left|f(x)\right\rangle \right)\right)\end{aligned}}}

where ${\displaystyle (-1)^{x\cdot y}}$ can either be ${\displaystyle -1}$ or ${\displaystyle 1}$, depending on ${\displaystyle x\cdot y=x_{1}y_{1}+\dots +x_{n}y_{n}}$, where ${\displaystyle x_{i},y_{i}\in \{0,1\}}$, for ${\displaystyle i=1,\dots ,n}$. So, for example, if ${\displaystyle x=101}$ and ${\displaystyle y=111}$, then ${\displaystyle x\cdot y=1*1+0*1+1*1=2}$, which is an even number. Thus, in this case, ${\displaystyle (-1)^{x\cdot y}=(-1)^{1*1+0*1+1*1}=(-1)^{2}=1}$. Note that ${\displaystyle {x\cdot y}}$ is always a non-negative number.

Let's now rewrite

${\displaystyle |\Psi \rangle ''={\frac {1}{2^{n}}}\sum _{x\in \{0,1\}^{n}}\left(\sum _{y\in \{0,1\}^{n}}\left((-1)^{x\cdot y}\left|y\right\rangle \otimes \left|f(x)\right\rangle \right)\right)}$

as follows

${\displaystyle |\Psi \rangle ''=\sum _{y\in \{0,1\}^{n}}\left(\left|y\right\rangle \otimes \left({\frac {1}{2^{n}}}\sum _{x\in \{0,1\}^{n}}\left((-1)^{x\cdot y}\left|f(x)\right\rangle \right)\right)\right)}$

This manipulation will be convenient to understand the explanations in the next sections. Note that we have switched the order of the summations.

Measurement

After having performed all previously described operations, at the end of the circuit, a measurement is performed.

There are now two possible cases we need to consider separately

• ${\displaystyle x\oplus y=0^{n}}$ or
• ${\displaystyle x\oplus y=s}$, where ${\displaystyle s\neq 0^{n}}$.

First case

Let's first analyze the (special) case ${\displaystyle x\oplus y=0^{n}}$, which means that ${\displaystyle f}$ is (by requirement) a one-to-one function (as explained above in the "problem description").

Let's keep in mind that the quantum state before the measurement is

${\displaystyle \sum _{y\in \{0,1\}^{n}}\left|y\right\rangle \otimes \left({\frac {1}{2^{n}}}\sum _{x\in \{0,1\}^{n}}\left((-1)^{x\cdot y}\left|f(x)\right\rangle \right)\right)}$

Now, the probability that the measurement results in each string ${\displaystyle y\in \{0,1\}^{n}}$ is

${\displaystyle p_{y}={{\Bigg \|}{\frac {1}{2^{n}}}\sum _{x\in \{0,1\}^{n}}\left((-1)^{x\cdot y}\left|f(x)\right\rangle \right){\Bigg \|}}^{2}={\frac {1}{2^{n}}}}$

One way to see that the previous equation is true is to note that

${\displaystyle {{\Bigg \|}{\frac {1}{2^{n}}}\sum _{x\in \{0,1\}^{n}}\left((-1)^{x\cdot y}\left|f(x)\right\rangle \right){\Bigg \|}}^{2}={{\Bigg \|}{\frac {1}{2^{n}}}\sum _{x\in \{0,1\}^{n}}\left((-1)^{x\cdot y}\left|x\right\rangle \right){\Bigg \|}}^{2}}$

because the two vectors only differ in the ordering of their entries, given that ${\displaystyle f}$ is one-to-one.

The value of the right-hand side, that is

${\displaystyle {{\Bigg \|}{\frac {1}{2^{n}}}\sum _{x\in \{0,1\}^{n}}\left((-1)^{x\cdot y}\left|x\right\rangle \right){\Bigg \|}}^{2}}$

is more easily seen to be ${\displaystyle {\frac {1}{2^{n}}}}$.

Thus, when ${\displaystyle x\oplus y=0^{n}}$, the outcome is simply a uniformly distributed ${\displaystyle n}$-bit string.

Second case

Let's now analyze the case ${\displaystyle x\oplus y=s}$, where ${\displaystyle s\neq 0^{n}}$. Note that, in this case, ${\displaystyle f}$ is a two-to-one function, that is, there are two inputs that map to the same output of ${\displaystyle f}$.

The analysis performed in the first case is still valid for this second case, that is, the probability to measure any given string ${\displaystyle y\in \{0,1\}^{n}}$ can still be represented as

${\displaystyle p_{y}={{\Bigg \|}{\frac {1}{2^{n}}}\sum _{x\in \{0,1\}^{n}}\left((-1)^{x\cdot y}\left|f(x)\right\rangle \right){\Bigg \|}}^{2}}$

However, in this second case, we still need to figure out what this value of ${\displaystyle p_{y}}$ is. Let's see why in the following explanations.

Let ${\displaystyle A=range(f)}$. Let ${\displaystyle z\in A}$ (i.e. ${\displaystyle z}$ is some output of the function ${\displaystyle f}$), then note that, for every ${\displaystyle x_{1}\in \{0,1\}^{n}}$, there is one (and only one) ${\displaystyle x_{2}\in \{0,1\}^{n}}$, such that ${\displaystyle f(x_{1})=f(x_{2})=z}$; moreover, we also have ${\displaystyle x_{1}\oplus x_{2}=s}$, which is equivalent to ${\displaystyle x_{2}=s\oplus x_{1}}$ (see "the problem description" section above for a review of this concept).

Hence, we have

${\displaystyle p_{y}={{\Bigg \|}{\frac {1}{2^{n}}}\sum _{x\in \{0,1\}^{n}}\left((-1)^{x\cdot y}\left|f(x)\right\rangle \right){\Bigg \|}}^{2}={{\Bigg \|}{\frac {1}{2^{n}}}\sum _{z\in A}\left(((-1)^{x_{1}\cdot y}+(-1)^{x_{2}\cdot y})\left|z\right\rangle \right){\Bigg \|}}^{2}}$

Given that ${\displaystyle x_{2}=s\oplus x_{1}}$, then we can rewrite the coefficient ${\displaystyle (-1)^{x_{1}\cdot y}+(-1)^{x_{2}\cdot y}}$ as follows

${\displaystyle (-1)^{x_{1}\cdot y}+(-1)^{x_{2}\cdot y}=(-1)^{x_{1}\cdot y}+(-1)^{(x_{1}\oplus s)\cdot y}}$

Given that ${\displaystyle (x_{1}\oplus s)\cdot y=(x_{1}\cdot y)\oplus (s\cdot y)}$, then we can further write the expression above as

${\displaystyle (-1)^{x_{1}\cdot y}(1+(-1)^{y\cdot s})}$

So, ${\displaystyle p_{y}}$ can further be written as

${\displaystyle p_{y}={{\Bigg \|}{\frac {1}{2^{n}}}\sum _{z\in A}\left((-1)^{x_{1}\cdot y}(1+(-1)^{y\cdot s})\left|z\right\rangle \right){\Bigg \|}}^{2}}$
Odd number

Now, if ${\displaystyle y\cdot s=y_{1}s_{1}+\dots +y_{n}s_{n}}$ is an odd number, then ${\displaystyle (-1)^{y\cdot s}=-1}$. In that case,

${\displaystyle (-1)^{x_{1}\cdot y}(1+(-1)^{y\cdot s})=(-1)^{x_{1}\cdot y}(1-1)=0}$

Consequently, we have

${\displaystyle p_{y}={{\Bigg \|}{\frac {1}{2^{n}}}\sum _{z\in A}\left((-1)^{x_{1}\cdot y}(1+(-1)^{y\cdot s})\left|z\right\rangle \right){\Bigg \|}}^{2}=0}$

Given that ${\displaystyle p_{y}=0}$, then we never have this case, that is, no string ${\displaystyle y\in \{0,1\}^{n}}$ is seen (after the measurement) in this case.

(This is the case where we have destructive interference.)

Even number

If, instead, ${\displaystyle y\cdot s}$ is an even number (e.g. zero), then ${\displaystyle (-1)^{y\cdot s}=1}$. In that case,

${\displaystyle (-1)^{x_{1}\cdot y}(1+(-1)^{y\cdot s})=(-1)^{x_{1}\cdot y}2}$

So, we have

${\displaystyle p_{y}={{\Bigg \|}{\frac {1}{2^{n}}}\sum _{z\in A}\left((-1)^{x_{1}\cdot y}(2)\left|z\right\rangle \right){\Bigg \|}}^{2}={{\Bigg \|}{\frac {2}{2^{n}}}\sum _{z\in A}\left((-1)^{x_{1}\cdot y}\left|z\right\rangle \right){\Bigg \|}}^{2}={{\Bigg \|}{\frac {1}{2^{n-1}}}\sum _{z\in A}\left((-1)^{x_{1}\cdot y}\left|z\right\rangle \right){\Bigg \|}}^{2}}$

Note that ${\displaystyle {\frac {2}{2^{n}}}=2*2^{-n}=2^{1}*2^{-n}=2^{-n+1}=2^{-(n-1)}={\frac {1}{2^{n-1}}}}$.

(This is the case where we have constructive interference.)

So, in summary, for this second case, we have the following probabilities

${\displaystyle p_{y}={{\Bigg \|}{\frac {1}{2^{n}}}\sum _{x\in \{0,1\}^{n}}\left((-1)^{x\cdot y}\left|f(x)\right\rangle \right){\Bigg \|}}^{2}={\begin{cases}{\frac {1}{2^{n-1}}}&\quad {\text{if }}y\cdot s{\text{ is even}}\\0&\quad {\text{if }}y\cdot s{\text{ is odd}}\\\end{cases}}}$

Classical post-processing

When we run the circuit (operations) above, there are two cases:

• in the (special) case where ${\displaystyle x\oplus y=0^{n}}$, the measurement results in each string ${\displaystyle y\in \{0,1\}^{n}}$ with probability ${\displaystyle p_{y}={\frac {1}{2^{n}}}}$
• in the case ${\displaystyle x\oplus y=s}$ (where ${\displaystyle s\neq 0^{n}}$), the probability to obtain each string ${\displaystyle y\in \{0,1\}^{n}}$ is given by
${\displaystyle p_{y}={\begin{cases}{\frac {1}{2^{n-1}}}&\quad {\text{if }}y\cdot s{\text{ is even}}\\0&\quad {\text{if }}y\cdot s{\text{ is odd}}\\\end{cases}}}$

Thus, in both cases, the measurement results in some string ${\displaystyle y\in \{0,1\}^{n}}$ that satisfies ${\displaystyle s\cdot y=0}$, and the distribution is uniform over all of the strings that satisfy this constraint.

Is this enough information to determine ${\displaystyle s}$? The answer is "yes", provided that the process (above) is repeated several times (and a small probability of failure is accepted). Specifically, if the above process is run ${\displaystyle n-1}$ times, we get ${\displaystyle n-1}$ strings ${\displaystyle y_{1},y_{2},\dots ,y_{n-1}\in \{0,1\}^{n}}$, such that

${\displaystyle {\begin{cases}y_{1}\cdot s&=0\\y_{2}\cdot s&=0\\&\vdots \\y_{n-1}\cdot s&=0\end{cases}}}$

This is a system if ${\displaystyle n-1}$ linear equations in ${\displaystyle n}$ unknowns (i.e. the bits of ${\displaystyle s}$), and the goal is to solve it to obtain ${\displaystyle s}$. Note that each of the ${\displaystyle y_{1},y_{2},\dots ,y_{n-1}\in \{0,1\}^{n}}$ that we obtain after each measurement (for each "round" of the process) is, of course, the result of a measurement, so it is known (at the end of each "round").

We only get a unique non-zero solution ${\displaystyle s}$ if we are "lucky" and ${\displaystyle y_{1},y_{2},\dots ,y_{n-1}\in \{0,1\}^{n}}$ are linearly independent. The probability that ${\displaystyle y_{1},y_{2},\dots ,y_{n-1}}$ are linearly independent is at least

${\displaystyle \prod _{k=1}^{\infty }\left(1-{\frac {1}{2^{k}}}\right)=0.288788\dots >{\frac {1}{4}}}$

If we have linear independence, we can solve the system to get a candidate solution ${\displaystyle s'\neq 0^{n}}$ and test that ${\displaystyle f(0^{n})=f(s')}$. If ${\displaystyle f(0^{n})=f(s')}$, we know that ${\displaystyle s=s'}$, and the problem has been solved. If ${\displaystyle f(0^{n})\neq f(s')}$, it must be that ${\displaystyle s=0^{n}}$ (because, if this were not so, the unique non-zero solution to the linear equations would have been ${\displaystyle s}$). Either way, once we have linear independence, we can solve the problem.

Complexity

Simon's algorithm requires ${\displaystyle O(n)}$ queries to the black box, whereas a classical algorithm would need at least ${\displaystyle \Omega (2^{n/2})}$ queries. It is also known that Simon's algorithm is optimal in the sense that any quantum algorithm to solve this problem requires ${\displaystyle \Omega (n)}$ queries.[3][4]