Simon’s Algorithm

After the Deutsch-Jozsa Algorithm demonstrated the potential of quantum algorithms to give exponential speed-ups over their classical counterparts, Simon’s Algorithm was the first to demonstrate such a speed-up for a specific problem. Simon’s, inspired by Deutsch-Jozsa, in turn inspired the Quantum Fourier Transform and Shor’s Factoring Algorithm.

I took the Python Qiskit code from IBM Q Experience and translated it to OpenQASM (Quantum Assembly Language).

OPENQASM 2.0;
include "qelib1.inc";
qreg q[4];
creg c[4];
This initializes 4 quantum and 4 classical registers. The 4 quantum bits (qubits) all start at a ground state (lowest energy) of zero.

h q[0];
h q[1];
This puts the first 2 qubits into superposition states.

cx q[0], q[2];
cx q[0], q[3];
cx q[1], q[2];
cx q[1], q[3];
This creates a secret structure: s=11.

measure q[2] -> c[2];
measure q[3] -> c[3];
This measures the second 2 qubits.

h q[0];
h q[1];
measure q[0] -> c[0];
measure q[1] -> c[1];
This measures the first 2 qubits.

A secret structure, s, is applied to the inputs. In this case, s=11, there will be half as many unique outputs as unique inputs. If you have 8 unique inputs, you will have 8 total outputs, but only 4 unique outputs. Pairs of inputs will have the same outputs.

The application of the secret structure is in the second block from the left. For s=11, only XOR gates are used.

After executing the quantum computation, a classical algorithm is then used to determine that the secret structure, s, is 11. I skipped that part, but the IBM Q Experience link near the beginning of this article includes the Python Qiskit implementation of that. Therefore, Simon’s Algorithm is best executed in Qiskit. I used QASM simply because I enjoy it so much, plus using Qiskit would have required merely copying-and-pasting; there’s no fun in that.

Although s=11 seems to be the most common test of Simon’s Algorithm, I’ve also seen s=110 a couple of times. So, I decided to test that one, too.

OPENQASM 2.0;
include "qelib1.inc";
qreg q[6];
creg c[6];
This initializes 6 quantum registers and 6 classical registers.

h q[0];
h q[1];
h q[2];
The first 3 qubits are put into superposition states.

barrier q;
cx q[2], q[4];
x q[3];
cx q[2], q[3];
ccx q[0], q[1], q[3];
x q[0];
x q[1];
ccx q[0], q[1], q[3];
x q[0];
x q[1];
x q[3];
This applies the secret structure: s=110.

barrier q;
measure q[3] -> c[3];
measure q[4] -> c[4];
measure q[5] -> c[5];
This measures the second 3 qubits.

barrier q;
h q[0];
h q[1];
h q[2];
measure q[0] -> c[0];
measure q[1] -> c[1];
measure q[2] -> c[2];
This measures the first 3 qubits.

Applying a different secret structure results in almost identical code in the beginning and at the end. Only the second section, which actually applies the secret structure, substantially changes.

The second block from the left again applies the secret structure, however s=110 noticeably adds complexity compared to s=11. In addition to XOR (blue) gates, s=110 uses NOT (green) and AND (purple) gates.

The histogram for s=110 is relatively flat, similar to the histogram for s=11. Again, a classical algorithm is used to determine, from the outputs, the secret structure.

I tried explaining Simon’s Algorithm to a non-technical person and came up with a cooking analogy. For s=11, for simplicity, imagine two of your inputs are “wheat flour” and “raisins” and they both have “raisin cookies” as their outputs. Simon’s Algorithm identifies the recipe that makes that happen.