Simon's problem

Not to be confused with Simon problems in mathematical physics.

In computational complexity theory and quantum computing, Simon's problem is a computational problem that is proven to be solved exponentially faster on a quantum computer than on a classical (that is, traditional) computer. The quantum algorithm solving Simon's problem, usually called Simon's algorithm, served as the inspiration for Shor's algorithm. Both problems are special cases of the abelian hidden subgroup problem, which is now known to have efficient quantum algorithms.

The problem is set in the model of decision tree complexity or query complexity and was conceived by Daniel Simon in 1994. Simon exhibited a quantum algorithm that solves Simon's problem exponentially faster and with exponentially fewer queries than the best probabilistic (or deterministic) classical algorithm. In particular, Simon's algorithm uses a linear number of queries and any classical probabilistic algorithm must use an exponential number of queries.

This problem yields an oracle separation between the complexity classes BPP (bounded-error classical query complexity) and BQP (bounded-error quantum query complexity). This is the same separation that the Bernstein–Vazirani algorithm achieves, and different from the separation provided by the Deutsch–Jozsa algorithm, which separates P and EQP. Unlike the Bernstein–Vazirani algorithm, Simon's algorithm's separation is exponential.

Because this problem assumes the existence of a highly-structured "black box" oracle to achieve its speedup, this problem has little practical value. However, without such an oracle, exponential speedups cannot easily be proven, since this would prove that P is different from PSPACE.

Problem description

Given a function (implemented by a black box or oracle) $f:\{0,1\}^{n}\rightarrow \{0,1\}^{n}$ with the promise that, for some unknown $s\in \{0,1\}^{n}$, for all $x,y\in \{0,1\}^{n}$,

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

where $\oplus$ denotes bitwise XOR. The goal is to identify $s$ by making as few queries to $f(x)$ as possible. Note that

$a\oplus b=0^{n}$ if and only if $a=b$

Furthermore, for some $x$ and $s$ in $x\oplus y=s$, $y$ is unique (not equal to $x$) if and only if $s\neq 0^{n}$. This means that $f$ is two-to-one when $s\neq 0^{n}$, and one-to-one when $s=0^{n}$. It is also the case that $x\oplus y=s$ implies $y=s\oplus x$, meaning that

$$f(x)=f(y)=f(x\oplus {s})$$

which shows how $f$ is periodic.

The associated decision problem formulation of Simon's problem is to distinguish when $s=0^{n}$ ($f$ is one-to-one), and when $s\neq 0^{n}$ ($f$ is two-to-one).

Example

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

$x$	$f(x)$
000	101
001	010
010	000
011	110
100	000
101	110
110	101
111	010

In this case, $s=110$ (i.e. the solution). It can easily be verified that 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$. ${\displaystyle f(010)=000}$ and ${\displaystyle f(100)=000}$. If we apply XOR to 010 and 100 we obtain 110, that is ${\displaystyle 010\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. If we apply XOR to 001 and 111, we obtain 110, that is $001\oplus 111=110=s$. This gives the same solution $s=110$ we solved for before.

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

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 $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 ${\displaystyle \Omega ({\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 up to $2^{n-1}+1$ inputs, Simon's problem seeks to find s using fewer queries than this classical method.

Simon's algorithm

Quantum circuit representing/implementing Simon's algorithm

The algorithm as a whole uses this subroutine in 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}\cdot s=0$, so we can solve the system of equations this produces to get $s$.

Quantum subroutine

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^{\otimes n}|k\rangle ={\frac {1}{\sqrt {2^{n}}}}\sum _{j=0}^{2^{n}-1}(-1)^{k\cdot j}|j\rangle$$

where $k\cdot j=k_{1}j_{1}\oplus \ldots \oplus k_{n}j_{n}$, where $\oplus$ denotes XOR.

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

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

Query the oracle $U_{f}$ to get the state

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

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

${\frac {1}{\sqrt {2^{n}}}}\sum _{k=0}^{2^{n}-1}\left[{\frac {1}{\sqrt {2^{n}}}}\sum _{j=0}^{2^{n}-1}(-1)^{j\cdot k}|j\rangle \right]|f(k)\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\rangle$ is

$$\left|\left|{\frac {1}{2^{n}}}\sum _{k=0}^{2^{n}-1}(-1)^{j\cdot k}|f(k)\rangle \right|\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\rangle$. There are two cases for our measurement:

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

For the first case, since

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

since in this case, $f$ is one-to-one, implying that the range of $f$ is $\{0,1\}^{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\in \mathrm {range} (f)$. We can thus write

$$\left|\left|{\frac {1}{2^{n}}}\sum _{k=0}^{2^{n}-1}(-1)^{j\cdot k}|f(k)\rangle \right|\right|^{2}=\left|\left|{\frac {1}{2^{n}}}\sum _{z\,\in \,\mathrm {range} (f)}((-1)^{k\cdot x_{1}}+(-1)^{k\cdot x_{2}})|z\rangle \right|\right|^{2}$$

Furthermore, since we know that $x_{1}\oplus x_{2}=s$, we know that $x_{2}=x_{1}\oplus s$, and so

$${\begin{aligned}\left|\left|{\frac {1}{2^{n}}}\sum _{z\,\in \,\mathrm {range} (f)}((-1)^{k\cdot x_{1}}+(-1)^{k\cdot x_{2}})|z\rangle \right|\right|^{2}&=\left|\left|{\frac {1}{2^{n}}}\sum _{z\,\in \,\mathrm {range} (f)}((-1)^{k\cdot x_{1}}+(-1)^{k\cdot (x_{1}\oplus s)})|z\rangle \right|\right|^{2}\\&=\left|\left|{\frac {1}{2^{n}}}\sum _{z\,\in \,\mathrm {range} (f)}((-1)^{k\cdot x_{1}}+(-1)^{k\cdot x_{1}\oplus k\cdot s})|z\rangle \right|\right|^{2}\\&=\left|\left|{\frac {1}{2^{n}}}\sum _{z\,\in \,\mathrm {range} (f)}(-1)^{k\cdot x_{1}}(1+(-1)^{k\cdot s})|z\rangle \right|\right|^{2}\end{aligned}}$$

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

Thus, both when $s=0^{n}$ and when $s\neq 0^{n}$, our measured $k$ satisfies $k\cdot s=0$.

Classical post-processing

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

The probability that $y_{1},y_{2},\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'$, we can test if $f(0^{n})=f(s')$. If this is true, then we know $s'=s$, since $f(0^{n})=f(0^{n}\oplus s)=f(s)$. If it is the case that $f(0^{n})\neq f(s')$, 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 up the probabilities of success arbitrarily, while still having the same time complexity.

Complexity

Simon's algorithm requires $O(n)$ queries to the black box, whereas a classical algorithm would need at least $\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 $\Omega (n)$ queries.

See also

• Deutsch–Jozsa algorithm