Skip to content
Branch: master
Find file Copy path
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
79 lines (59 sloc) 3.86 KB

Simon's Algorithm


This module emulates Simon's Algorithm.

Simon's problem is summarized as follows. A function \(f :\{0,1\}^n\rightarrow\{0,1\}^n\) is promised to be either one-to-one, or two-to-one with some nonzero \(n\)-bit mask \(s\). The latter condition means that for any two different \(n\)-bit numbers \(x\) and \(y\), \(f(x)=f(y)\) if and only if \(x\oplus y = s\). The problem then is to determine whether \(f\) is one-to-one or two-to-one, and, if the latter, what the mask \(s\) is, in as few queries to \(f\) as possible.

The problem statement and algorithm can be explored further, at a high level, in reference [1]. The implementation of the algorithm in this module, however, follows [2].

Algorithm and Details

This algorithm involves a quantum component and a classical component. The quantum part follows similarly to other blackbox oracle algorithms. First, assume a blackbox oracle \(U_f\) is available with the property $$U_f\vert x\rangle\vert y\rangle = \vert x\rangle\vert y\oplus f(x)\rangle$$

where the top \(n\) qubits \(\vert x \rangle\) are the input, and the bottom \(n\) qubits \(\vert y \rangle\) are called ancilla qubits.

The input qubits are prepared with the ancilla qubits into the state $$(H^{\otimes n} \otimes I^{\otimes n})\vert 0\rangle^{\otimes n}\vert 0\rangle^{\otimes n} = \vert +\rangle^{\otimes n}\vert 0\rangle^{\otimes n}$$ and sent through a blackbox gate \(U_f\). Then, the Hadamard-Walsh transform \(H^{\otimes n}\) is applied to the \(n\) input qubits, resulting in the state given by $$(H^{\otimes n} \otimes I^{\otimes n})U_f\vert +\rangle^{\otimes n}\vert 0\rangle^{\otimes n}$$

It turns out the resulting \(n\) input qubits are in a uniform random state over the space killed by (modulo \(2\), bitwise) dot product with \(s\). This covers the one-to-one case as well, if one considers it to be the degenerate \(s=0\) case.

Suppose we then measured the \(n\) input qubits, calling the bitstring output \(y\). The above property then requires \(s\cdot y = 0\). The space of \(y\) that satisfies this is \(n-1\) dimensional. By running this quantum subroutine several times, \(n-1\) nonzero linearly independent bitstrings \(y_i\), \(i = 0, \ldots, n-2\), can be found, each orthogonal to \(s\).

This gives a system of \(n-1\) equations, with \(n\) unknowns for finding \(s\). One final nonzero bitstring \(y^{\prime}\) can be classically found that is linearly independent to the other \(y_i\), but with the property that \(s\cdot y^{\prime} = 1\). The combination of \(y^{\prime}\) and the \(y_i\) give a system of \(n\) independent equations that can then be solved for \(s\).

By using a clever implementation of Gaussian Elimination and Back Substitution for mod-2 equations, as outlined in Reference [2], \(s\) can be found relatively quickly. By then sending separate input states \(\vert 0\rangle\) and \(\vert s\rangle\) through the blackbox \(U_f\), we can find whether or not \(f(0) = f(s)\) (in fact, any pair \(\vert x\rangle\) and \(\vert x\oplus s\rangle\) will do as well). If so, we conclude \(f\) is two-to-one with mask \(s\); otherwise, \(f\) is one-to-one.

Overall, this algorithm can be solved in \(O(n^3)\), i.e., polynomial, time, whereas the best classical algorithm requires exponential time.

Source Code Docs

Here you can find documentation for the different submodules in simon.


.. automodule:: grove.simon.simon


[2](1, 2)
You can’t perform that action at this time.