Simon's problem

Simon's problem considers access to a function $f:\; \backslash \{0,1\backslash \}^n\; \backslash to\; \backslash \{0,1\backslash \}^m,\; \backslash ;\; m\; \backslash geq\; n$ as implemented by a black box or an oracle. This function is promised to be either a one-to-one function, or a two-to-one function; if $f$ is two-to-one, it is furthermore promised that two inputs $x$ and $x\text{'}$ evaluate to the same value if and only if $x$ and $x\text{'}$ differ in a fixed set of bits. I.e.,

:If $f$ is not one-to-one, it is promised that there exists a non-zero $s$ such that, for all $x\; \backslash neq\; x\text{'}$, $f(x)\; =\; f(x\text{'})$ if and only if $x\text{'}\; =\; x\; \backslash oplus\; s$

where $\backslash oplus$ denotes bitwise exclusive-or. Simon's problem asks, in its decision version, whether $f$ is one-to-one or two-to-one. In its non-decision version, Simon's problem asks whether $f$ is one-to-one or what is the value of $s$ (as defined above). The goal is to solve this task with the least number of queries (evaluations) of $f$.

Note that if $x\text{'}\; =\; x$, then $f(x\text{'})\; =\; f(x)$ and $x\text{'}\; =\; x\; \backslash oplus\; s$ with $s\; =\; 0$. On the other hand (because $a\; \backslash oplus\; b\; \backslash oplus\; b\; =\; a$ for all $a$ and $b$), $x\text{'}\; =\; x\; \backslash oplus\; s\; \backslash iff\; x\text{'}\; \backslash oplus\; x\; =\; s$. Thus, Simon's problem may be restated in the following form:

:Given black-box or oracle access to $f$, promised to satisfy, for some $s$ and all $x,x\text{'}$, $f(x)\; =\; f(x\text{'})$ if and only if $x\text{'}\; \backslash oplus\; x\; \backslash in\; \backslash \{0,\; s\backslash \}$, determine whether $s\; \backslash neq\; 0$ (decision version), or output $s$ (non-decision version).

Note also that the promise on $f$ implies that if $f$ is two-to-one then it is a periodic function:

$f(x)\; =\; f(y)\; =\; f(x\; \backslash oplus\; s).$

The following function is an example of a function that satisfies the required property for $n\; =\; 3$:

In this case, $s\; =\; 110$ (i.e. the solution). Every output of $f$ occurs twice, and the two input strings corresponding to any one given output have bitwise XOR equal to $s\; =\; 110$.

For example, the input strings $010$ and $100$ are both mapped (by $f$) to the same output string $000$. That is, $\{\backslash displaystyle\; f(010)=000\}$

and $$

{\displaystyle f(100)=000}. Applying XOR to 010 and 100 obtains 110, that is $\{\backslash displaystyle\; 010\backslash oplus\; 100=110=s\}.$

$s=110$ can also be verified using input strings 001 and 111 that are both mapped (by f) to the same output string 010. Applying XOR to 001 and 111 obtains 110, that is $001\backslash oplus111=110=s$. This gives the same solution $s=110$ as before.

In this example the function f is indeed a two-to-one function where $\{\backslash displaystyle\; s\backslash neq\; 0^\{n\}\}$.

Intuitively, this is a 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 $x$ and $y$ for which $f(x)=f(y)$. There is not necessarily any structure in the function $f$ that would help us to find two such inputs: more specifically, we can discover something about $f$ (or what it does) only when, for two different inputs, we obtain the same output. In any case, we would need to guess $\{\backslash displaystyle\; \backslash Omega\; (\{\backslash sqrt\; \{2^\{n\}\}\})\}$ different inputs before being likely to find a pair on which $f$ takes the same output, as per the birthday problem. Since, classically to find s with a 100% certainty it would require checking $\{\backslash displaystyle\; \backslash Theta\; (\{\backslash sqrt\; \{2^\{n\}\}\})\}$ inputs, Simon's problem seeks to find s using fewer queries than this classical method.

Image:Simons algorithm.svgThe algorithm as a whole uses a subroutine to execute the following two steps:

1. Run the quantum subroutine an expected $O(n)$ times to get a list of linearly independent bitstrings $y\_1,\; ...,\; y\_\{n\; -\; 1\}$.
2. Each $y\_k$ satisfies $y\_k\; \backslash cdot\; s\; =\; 0$, so we can solve the system of equations this produces to get $s$.

The quantum circuit (see the picture) is the implementation of the quantum part of Simon's algorithm. The quantum subroutine of the algorithm makes use of the Hadamard transform$$H^\{\backslash otimes\; n\}|k\backslash rangle\; =\; \backslash frac\{1\}\{\backslash sqrt\{2^n\}\}\; \backslash sum\_\{j\; =\; 0\}^\{2^n\; -\; 1\}\; (-1)^\{k\; \backslash cdot\; j\}\; |j\backslash rangle$$where $k\; \backslash cdot\; j\; =\; k\_1\; j\_1\; \backslash oplus\; \backslash ldots\; \backslash oplus\; k\_n\; j\_n$, where $\backslash oplus$ denotes XOR.

First, the algorithm starts with two registers, initialized to $|0\backslash rangle^\{\backslash otimes\; n\}|0\backslash rangle^\{\backslash otimes\; n\}$. Then, we apply the Hadamard transform to the first register, which gives the state

: $\backslash frac\{1\}\{\backslash sqrt\{2^n\}\}\; \backslash sum\_\{k\; =\; 0\}^\{2^n\; -\; 1\}\; |k\backslash rangle\; |0\backslash rangle^\{\backslash otimes\; n\}.$

Query the oracle $U\_f$ to get the state

: $\backslash frac\{1\}\{\backslash sqrt\{2^n\}\}\; \backslash sum\_\{k\; =\; 0\}^\{2^n\; -\; 1\}\; |k\backslash rangle\; |f(k)\backslash rangle$.

Apply another Hadamard transform to the first register. This will produce the state

: $\backslash frac\{1\}\{\backslash sqrt\{2^n\}\}\; \backslash sum\_\{k\; =\; 0\}^\{2^n\; -\; 1\}\; \backslash left[\backslash frac\{1\}\{\backslash sqrt\{2^n\}\}\; \backslash sum\_\{j\; =\; 0\}^\{2^n\; -\; 1\}\; (-1)^\{j\; \backslash cdot\; k\}\; |j\backslash rangle\; \backslash right]\; |f(k)\backslash rangle$

= \sum_{j = 0}^{2^n - 1} |j\rangle \left[\frac{1}{2^n} \sum_{k = 0}^{2^n - 1} (-1)^{j \cdot k} |f(k)\rangle \right].

Finally, we measure the first register (the algorithm also works if the second register is measured before the first, but this is unnecessary). The probability of measuring a state $|j\backslash rangle$ is$$\backslash left|\backslash left|\; \backslash frac\{1\}\{2^n\}\; \backslash sum\_\{k\; =\; 0\}^\{2^n\; -\; 1\}\; (-1)^\{j\; \backslash cdot\; k\}\; |f(k)\backslash rangle\; \backslash right|\backslash right|^2$$This is due to the fact that taking the magnitude of this vector and squaring it sums up all the probabilities of all the possible measurements of the second register that must have the first register as $|j\backslash rangle$. There are two cases for our measurement:

1. $s\; =\; 0^n$ and $f$ is one-to-one.
2. $s\; \backslash neq\; 0^n$ and $f$ is two-to-one.

For the first case, $$\backslash left|\backslash left|\; \backslash frac\{1\}\{2^n\}\; \backslash sum\_\{k\; =\; 0\}^\{2^n\; -\; 1\}\; (-1)^\{j\; \backslash cdot\; k\}\; |f(k)\backslash rangle\; \backslash right|\backslash right|^2\; =\; \backslash frac\{1\}\{2^n\}$$since in this case, $f$ is one-to-one, implying that the range of $f$ is $\backslash \{0,\; 1\backslash \}^n$, meaning that the summation is over every basis vector. For the second case, note that there exist two strings, $x\_1$ and $x\_2$, such that $f(x\_1)\; =\; f(x\_2)\; =\; z$, where $z\; \backslash in\; \backslash mathrm\{range\}(f)$. Thus, $$\backslash left|\backslash left|\; \backslash frac\{1\}\{2^n\}\; \backslash sum\_\{k\; =\; 0\}^\{2^n\; -\; 1\}\; (-1)^\{j\; \backslash cdot\; k\}\; |f(k)\backslash rangle\; \backslash right|\backslash right|^2$$

= \left|\left| \frac{1}{2^n} \sum_{z\, \in \,\mathrm{range}(f)} ((-1)^{j \cdot x_1} + (-1)^{j \cdot x_2}) |z\rangle \right|\right|^2Furthermore, since $x\_1\; \backslash oplus\; x\_2\; =\; s$, $x\_2\; =\; x\_1\; \backslash oplus\; s$, and so$$\backslash begin\{align\}$$

\left|\left| \frac{1}{2^n} \sum_{z\, \in \,\mathrm{range}(f)} ((-1)^{j \cdot x_1} + (-1)^{j \cdot x_2}) |z\rangle \right|\right|^2

&= \left|\left| \frac{1}{2^n} \sum_{z\, \in \,\mathrm{range}(f)} ((-1)^{j \cdot x_1} + (-1)^{j \cdot (x_1 \oplus s)}) |z\rangle \right|\right|^2 \\

&= \left|\left| \frac{1}{2^n} \sum_{z\, \in \,\mathrm{range}(f)} ((-1)^{j \cdot x_1} + (-1)^{j \cdot x_1 \oplus j \cdot s}) |z\rangle \right|\right|^2 \\

&= \left|\left| \frac{1}{2^n} \sum_{z\, \in \,\mathrm{range}(f)} (-1)^{j \cdot x_1}(1 + (-1)^{j \cdot s}) |z\rangle \right|\right|^2

\end{align}This expression is now easy to evaluate. Recall that we are measuring $j$. When $j\; \backslash cdot\; s\; =\; 1$, then this expression will evaluate to $0$, and when $j\; \backslash cdot\; s\; =\; 0$, then this expression will be $2^\{-n\; +\; 1\}$.

Thus, both when $s\; =\; 0^n$ and when $s\; \backslash neq\; 0^n$, our measured $j$ satisfies $j\; \backslash cdot\; s\; =\; 0$.

We run the quantum part of the algorithm until we have a linearly independent list of bitstrings $y\_1,\; \backslash ldots,\; y\_\{n\; -\; 1\}$, and each $y\_k$ satisfies $y\_k\; \backslash cdot\; s\; =\; 0$. Thus, we can efficiently solve this system of equations classically to find $s$.

The probability that $y\_1,\; y\_2,\; \backslash dots,\; y\_\{n-1\}$ are linearly independent is at least$$$$

\prod_{k=1}^\infty \left( 1 - \frac{1}{2^k} \right) = 0.288788\dots

Once we solve the system of equations, and produce a solution $s\text{'}$, we can test if $f(0^n)\; =\; f(s\text{'})$. If this is true, then we know $s\text{'}\; =\; s$, since $f(0^n)\; =\; f(0^n\; \backslash oplus\; s)\; =\; f(s)$. If it is the case that $f(0^n)\; \backslash neq\; f(s\text{'})$, then that means that $s\; =\; 0^n$, and $$

f(0^n) \neq f(s')

since $f$ is one-to-one.

We can repeat Simon's algorithm a constant number of times to increase the probability of success arbitrarily, while still having the same time complexity.

Consider the simplest instance of the algorithm, with $n=1$. In this case evolving the input state through an Hadamard gate and the oracle results in the state (up to renormalization):

: $|0\backslash rangle\; |f(0)\backslash rangle\; +\; |1\backslash rangle|f(1)\backslash rangle.$

If $s=1$, that is, $f(0)=f(1)$, then measuring the second register always gives the outcome $|f(0)\backslash rangle$, and always results in the first register collapsing to the state (up to renormalization):

: $|0\backslash rangle+\; |1\backslash rangle.$

Thus applying an Hadamard and measuring the first register always gives the outcome $|0\backslash rangle$. On the other hand, if $f$ is one-to-one, that is, $s=0$, then measuring the first register after the second Hadamard can result in both $|0\backslash rangle$ and $|1\backslash rangle$, with equal probability.

We recover $s$ from the measurement outcomes by looking at whether we measured always $|0\backslash rangle$, in which case $s=1$, or we measured both $|0\backslash rangle$ and $|1\backslash rangle$ with equal probability, in which case we infer that $s=0$. This scheme will fail if $s=0$ but we nonetheless always found the outcome $|0\backslash rangle$, but the probability of this event is $2^\{-N\}$ with $N$ the number of performed measurements, and can thus be made exponentially small by increasing the statistics.

Consider now the case with $n=2$. The initial part of the algorithm results in the state (up to renormalization):$$|00\backslash rangle|f(00)\backslash rangle\; +$$

|01\rangle|f(01)\rangle +

|10\rangle|f(10)\rangle +

|11\rangle|f(11)\rangle.If $s=(00)$, meaning $f$ is injective, then finding $|f(x)\backslash rangle$ on the second register always collapses the first register to $|x\backslash rangle$, for all $x\backslash in\backslash \{0,1\backslash \}^2$. In other words, applying Hadamard gates and measuring the first register the four outcomes $00,01,10,11$ are thus found with equal probability.

Suppose on the other hand $s\backslash neq(00)$, for example, $s=(01)$. Then measuring $|f(00)\backslash rangle$ on the second register collapses the first register to the state $|00\backslash rangle+|10\backslash rangle$. And more generally, measuring $|f(xy)\backslash rangle$ gives $|x,y\backslash rangle+|x,y\backslash oplus1\backslash rangle=|x\backslash rangle(|0\backslash rangle+|1\backslash rangle)$ on the first register. Applying Hadamard gates and measuring on the first register can thus result in the outcomes $00$ and $10$ with equal probabilities.

Similar reasoning applies to the other cases: if $s=(10)$ then the possible outcomes are $00$ and $01$, while if $s=(11)$ the possible outcomes are $00$ and $11$, compatibly with the $j\backslash cdot\; s=0$ rule discussed in the general case.

To recover $s$ we thus only need to distinguish between these four cases, collecting enough statistics to ensure that the probability of mistaking one outcome probability distribution for another is sufficiently small.

Simon's algorithm requires $O(n)$ queries to the black box, whereas a classical algorithm would need at least $\backslash 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 $\backslash Omega(n)$ queries.{{Citation|title=The quantum query complexity of the Abelian hidden subgroup problem|url=http://perso.ens-lyon.fr/pascal.koiran/Publis/lip.05-17.ps|year=2007|last1=Koiran|last2=Nesme|last3=Portier|first1=P.|first2=V.|first3=N.|journal=Theoretical Computer Science|volume=380|issue=1-2|pages=115–126|doi=10.1016/j.tcs.2007.02.057|access-date=2011-06-06|doi-access=free}}{{Citation|title=A quantum lower bound for the query complexity of Simon's Problem|url=http://perso.ens-lyon.fr/pascal.koiran/Publis/icalp05.ps|year=2005|last1=Koiran|last2=Nesme|last3=Portier|first1=P.|first2=V.|first3=N.|journal=Proc. ICALP|volume=3580|pages=1287–1298|arxiv=quant-ph/0501060|access-date=2011-06-06|bibcode=2005quant.ph..1060K}}

The quantum circuit shown here is from [https://learning.quantum.ibm.com/course/fundamentals-of-quantum-algorithms/quantum-query-algorithms#simons-algorithm a simple example of how Simon's algorithm can be implemented in Python] using Qiskit, an open-source quantum computing software development framework by IBM.

File:Example Qiskit quantum circuit that implements Simon's algorithm.png

• Deutsch–Jozsa algorithm
• Shor's algorithm
• Bernstein–Vazirani algorithm

{{reflist}}

{{Quantum computing}}

Category:Quantum algorithms