The Simon algorithm
Quantum Computing, Quantum Field Theory
- I. Introduction
- II. Elements of quantum mechanics
- III. The electromagnetic field
- IV. The qubit
- V. Quantum gates
- VI. States and operators
- VII. Shor’s algorithm
- VIII. Quantum teleportation
- IX. The Deutsch algorithm
- X. The no-cloning theorem
- XI. About anyons
- XII. About SU(2)
- XIII. Teleportation topology
- XIV. The Simon algorithm
- XV. Superdense coding
- XVI. Chern-Simons theory
- XVII. The toric code
- REF. Some pointers
The Deutsch algorithm helped discovering the total value of a binary function. The Josza extension helped discover whether a function is constant or balanced. The Simon algorithm deals with discovering periodic patterns in a function.
Specifically, given a function
\(f:\{0,1\}^n\mapsto\{0,1\}^n\)
satisfying
\(f(x)=f(y) \Leftrightarrow x = y \oplus c\)
with \(c = c_0\dots c_{n-1}\) a constant, can we determine c?
First, let’s note that applying the Hadamard transform on an arbitrary n-qubit
\(\displaystyle H\,|k_{n-1}\dots k_0\rangle = \frac{1}{2^{n/2}}\big((|0\rangle + (-)^{k_{n-1}}|1\rangle)\ldots (|0\rangle + (-)^{k_0}|1\rangle) \big) \\\;=\displaystyle \frac{1}{2^{n/2}}\sum_u (-)^{k.u}\,|u\rangle = H^{(n)}\,|k\rangle\)
which defines the n-Hadamard transform \(H^{(n)}\).
Put \(N=2^n\) and start with a ground state of twice n-qubits \(\psi_0 = |0\ldots 0\rangle|0\ldots 0\rangle\) and apply \(H^{(n)}\) on the first n-qubits:
\(\displaystyle\psi_1 = H^n\,|0\rangle|0\rangle = \frac{1}{\sqrt{N}}\sum_{k=0}^{N-1}|k\rangle|0\rangle\)
then apply the black-box function holding the result in the second register
\(\displaystyle\psi_2 = U_f\,|\psi_1\rangle = \frac{1}{\sqrt{N}}\sum_{k=0}^{N-1}|k\rangle|f(k)\rangle\)
applying the Hadamard treansform again
\(\displaystyle\psi_3 = U_f\,|\psi_1\rangle = \frac{1}{\sqrt{N}}\sum_{k=0}^{N-1}\big(\frac{1}{\sqrt{N}}\sum_{m=0}^{N-1}(-)^{m.k}|m\rangle\big)|f(k)\rangle\).
Now, the period \(c\) divides the N kets into cosets containing each two elements (because of the \(\mathbb{Z}_2\) addition \(\oplus\)). The value on these cosets is constant and if we take in each coset a representative value \(z\) we can reduce the sum over k by summing only over these representatives. Hence
\(\displaystyle\psi_3 = \frac{1}{N}\sum_{u=0}^{N-1}|u\rangle\,\sum_m|f(m)\rangle(-)^{m.u}\big(1+(-)^{c.u}\big)\).
If \(u\) is not orthogonal to \(c\) the term drops out, so measuring things will always reveal states which are orthogonal to \(c\). In fact, if you compute the probability of getting one of these states, call it \(v\), you get
\(\displaystyle\frac{1}{N^2}\sum_m\,\langle f(m)|\, f(m)\rangle\,|1+(-)^{c.v}|^2 = \frac{1}{2^{n-1}}\).
If you repeatedly measure the first register you end up with a collection of vectors spanning a space orthogonal to the period \(c\) which hence delivers the period. Note that the measurement collapses the state in each case and the procedure is destructive. So, this algorithm is not as magical as the Deutsch-Josza algorithm but still requires exponentially less power than any classical version.