Simon's problem

Simon's algorithm

The algorithm as a whole uses a subroutine to execute the following two steps:

1. Run the quantum subroutine an expected ${\displaystyle O(n)}$ times to get a list of linearly independent bitstrings ${\displaystyle y_1,...,y_{n-1}}$.
2. Each ${\displaystyle y_k}$ satisfies ${\displaystyle y_k\cdot s=0}$, so we can solve the system of equations this produces to get ${\displaystyle 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$${\displaystyle H^{\otimes n}|k⟩=\frac{1}{\sqrt{2^n}}\sum _{j=0}^{2^n-1}(-1{)}^{k\cdot j}|j⟩}$$where ${\displaystyle k\cdot j=k_1{j}_1\oplus \dots \oplus k_n{j}_n}$, where ${\displaystyle \oplus }$ denotes XOR.

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

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

Query the oracle ${\displaystyle U_f}$ to get the state

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

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

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

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

For the first case, $${\displaystyle {\left|\left|\frac{1}{2^n}\sum _{k=0}^{2^n-1}(-1{)}^{j\cdot k}|f(k)⟩\right|\right|}^2=\frac{1}{2^n}}$$since in this case, ${\displaystyle f}$ is one-to-one, implying that the range of ${\displaystyle f}$ is ${\displaystyle \{0,1{\}}^n}$, meaning that the summation is over every basis vector. For the second case, note that there exist two strings, ${\displaystyle x_1}$ and ${\displaystyle x_2}$, such that ${\displaystyle f(x_1)=f(x_2)=z}$, where ${\displaystyle z\in \mathrm{r}\mathrm{a}\mathrm{n}\mathrm{g}\mathrm{e}(f)}$. Thus, $${\displaystyle {\left|\left|\frac{1}{2^n}\sum _{k=0}^{2^n-1}(-1{)}^{j\cdot k}|f(k)⟩\right|\right|}^2={\left|\left|\frac{1}{2^n}\sum _{z\in \mathrm{r}\mathrm{a}\mathrm{n}\mathrm{g}\mathrm{e}(f)}((-1{)}^{j\cdot x_1}+(-1{)}^{j\cdot x_2})|z⟩\right|\right|}^2}$$Furthermore, since ${\displaystyle x_1\oplus x_2=s}$, ${\displaystyle x_2=x_1\oplus s}$, and so$${\displaystyle \begin{array}{cc}{\left|\left|\frac{1}{2^n}\sum _{z\in \mathrm{r}\mathrm{a}\mathrm{n}\mathrm{g}\mathrm{e}(f)}((-1{)}^{j\cdot x_1}+(-1{)}^{j\cdot x_2})|z⟩\right|\right|}^2& ={\left|\left|\frac{1}{2^n}\sum _{z\in \mathrm{r}\mathrm{a}\mathrm{n}\mathrm{g}\mathrm{e}(f)}((-1{)}^{j\cdot x_1}+(-1{)}^{j\cdot (x_1\oplus s)})|z⟩\right|\right|}^2\\ & ={\left|\left|\frac{1}{2^n}\sum _{z\in \mathrm{r}\mathrm{a}\mathrm{n}\mathrm{g}\mathrm{e}(f)}((-1{)}^{j\cdot x_1}+(-1{)}^{j\cdot x_1\oplus j\cdot s})|z⟩\right|\right|}^2\\ & ={\left|\left|\frac{1}{2^n}\sum _{z\in \mathrm{r}\mathrm{a}\mathrm{n}\mathrm{g}\mathrm{e}(f)}(-1{)}^{j\cdot x_1}(1+(-1{)}^{j\cdot s})|z⟩\right|\right|}^2\end{array}}$$This expression is now easy to evaluate. Recall that we are measuring ${\displaystyle j}$. When ${\displaystyle j\cdot s=1}$, then this expression will evaluate to ${\displaystyle 0}$, and when ${\displaystyle j\cdot s=0}$, then this expression will be ${\displaystyle 2^{-n+1}}$.

Thus, both when ${\displaystyle s=0^n}$ and when ${\displaystyle s\ne 0^n}$, our measured ${\displaystyle j}$ satisfies ${\displaystyle j\cdot s=0}$.

Classical post-processing

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

The probability that ${\displaystyle y_1,y_2,\dots ,y_{n-1}}$ are linearly independent is at least$${\displaystyle \prod _{k=1}^{\mathrm{\infty }}\left(1-\frac{1}{2^k}\right)=0.288788\dots }$$Once we solve the system of equations, and produce a solution ${\displaystyle s^{\prime }}$, we can test if ${\displaystyle f(0^n)=f(s^{\prime })}$. If this is true, then we know ${\displaystyle s^{\prime }=s}$, since ${\displaystyle f(0^n)=f(0^n\oplus s)=f(s)}$. If it is the case that ${\displaystyle f(0^n)\ne f(s^{\prime })}$, then that means that ${\displaystyle s=0^n}$, and ${\displaystyle f(0^n)\ne f(s^{\prime })}$ since ${\displaystyle 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.

Explicit examples of Simon's algorithm for few qubits

One qubit

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

${\displaystyle |0⟩|f(0)⟩+|1⟩|f(1)⟩.}$

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

${\displaystyle |0⟩+|1⟩.}$

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

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

Two qubits

Consider now the case with ${\displaystyle n=2}$. The initial part of the algorithm results in the state (up to renormalization):$${\displaystyle |00⟩|f(00)⟩+|01⟩|f(01)⟩+|10⟩|f(10)⟩+|11⟩|f(11)⟩.}$$If ${\displaystyle s=(00)}$, meaning ${\displaystyle f}$ is injective, then finding ${\displaystyle |f(x)⟩}$ on the second register always collapses the first register to ${\displaystyle |x⟩}$, for all ${\displaystyle x\in \{0,1{\}}^2}$. In other words, applying Hadamard gates and measuring the first register the four outcomes ${\displaystyle 00,01,10,11}$ are thus found with equal probability.

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

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

To recover ${\displaystyle 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.

Complexity

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

Simon's algorithm Qiskit implementation

The quantum circuit shown here is from 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.