Simon’s Algorithm

Overview

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.

grove.simon.simon

Module for Simon’s Algorithm. For more information, see [Simon1995], [Loceff2015], [Watrous2006]

[Simon1995]Simon, D.R. (1995), “On the power of quantum computation”, 35th Annual Symposium on Foundations of Computer Science, Proceedings, p. 116-123.
[Loceff2015]Loceff, M. (2015), “A Course in Quantum Computing for the Community College”, Volume 1, Chapter 18, p 484-541.
[Watrous2006]Watrous, J. (2006), “Simon’s Algorithm”, University of Calgary CPSC 519/619: Quantum Computation, Lecture 6.
class grove.simon.simon.Simon

Bases: object

This class contains an implementation of Simon’s algorithm using pyQuil. For more references see the documentation

find_mask(cxn, bitstring_map)

Runs Simon’s mask_array algorithm to find the mask.

Parameters:
  • cxn (QVMConnection) – the connection to the Rigetti cloud to run pyQuil programs
  • String] bitstring_map (Dict[String,) – a truth table describing the boolean function, whose period is to be found.
Returns:

Returns the mask of the bitstring map or raises an Exception if the mask cannot be found.

Return type:

String

grove.simon.simon.create_1to1_bitmap(mask)

A helper to create a bit map function (as a dictionary) for a given mask. E.g. for a mask \(m = 10\) the return is a dictionary:

>>> create_1to1_bitmap('10')
... {
...     '00': '10',
...     '01': '11',
...     '10': '00',
...     '11': '01'
... }
Parameters:mask (String) – binary mask as a string of 0’s and 1’s
Returns:dictionary containing a mapping of all possible bit strings of the same length as the mask’s string and their mapped bit-string value
Return type:Dict[String, String]
grove.simon.simon.create_valid_2to1_bitmap(mask, random_seed=None)

A helper to create a 2-to-1 binary function that is invariant with respect to the application of a specified XOR bitmask. This property must be satisfied if a 2-to-1 function is to be used in Simon’s algorithm

More explicitly, such a 2-to-1 function \(f\) must satisfy \(f(x) = f(x \oplus m)\) where \(m\) is a bit mask and \(\oplus\) denotes the bit wise XOR operation. An example of such a function is the truth-table

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

Note that, e.g. both 000 and 110 map to the same value 101 and \(000 \oplus 110 = 110\). The same holds true for other pairs.

Parameters:
  • mask (String) – mask input that defines the periodicity of f
  • random_seed (Integer) – (optional) integer to set numpy.random.seed parameter.
Returns:

dictionary containing the truth table of a valid 2-to-1 boolean function

Return type:

Dict[String, String]

References

[1]http://pages.cs.wisc.edu/~dieter/Courses/2010f-CS880/Scribes/05/lecture05.pdf
[2](1, 2) http://lapastillaroja.net/wp-content/uploads/2016/09/Intro_to_QC_Vol_1_Loceff.pdf