Implementing Simon’s Algorithm in Qiskit

Simon’s Algorithm was the first demonstration of a quantum computer being able to solve a problem exponentially faster than a classical computer.

It aims to solve the following problem. Let’s say you have a black box function (an unknown function which you can’t “see” into) which looks like

This basically means that the function is either 1:1 — it maps one input to each output — or 2:1 — it maps two inputs to one each output. If the function is a 2:1 function the inputs that lead to the same output are related through the XOR operator on a bit string. We want to figure out if the function is 1:1 or 2:1, and if it is 2:1, what the bit string is.

Let’s say our function has n possible inputs. Classically, our best case scenario is 2 queries: if we try two different inputs and get the same output, then we know it’s 2:1. But, if we keep querying the function and we keep getting different answers, then we have to check just over half of the possible inputs to confirm that it is actually 1:1. This totals to 2^(n-1) + 1.

But, with a quantum computer, the most we would have to do is n queries.

For small values of n, this doesn’t seem like a huge difference, but as n grows, the difference does as well…exponentially. For instance, when n = 5, the worst case classical solution is 17 where as the worst case quantum solution is 5.

What is the algorithm?

The algorithm functions in six main steps.

1. Initialize 2 n qubit registers to |0>.
2. Apply a hadamard gate to the first register.
3. Apply the function
4. Measure the second register
5. Apply hadamard gates to each qubit in the first register
6. Measure the first register

At this point, we are interested in figuring out the probability that each string is measured. If b = 0^n, then we know that our function must be a 1:1 function. But, if b doesn’t equal zero, we can query a bunch of different inputs, get a bunch of different outputs and use gaussian elimination to deduce s.

Why does it work?

After the first step, our system looks like

Then, after we apply the Hadamard gate to the first register, our state is the tensor product of an equal superposition of all possible basis states and the second purely |0> states:

Then, after we implement the function — f(x) — we have

After we measure the second register, it will collapse and a certain value of f(x) will be observed. This could correlate to one of two possible inputs: x or x XOR b.

At this point, we can discard the second register and after applying our second set of Hadamards, we have

Then, we measure the first register which can only return a result when

This only happens when

And so we get a value of z whose inner product with b must be 0. If we repeat this process n times, we can get a series of equations which look something like

which can be solved.

How can we implement this in qiskit?

The specific implementation we are going to be doing here involves two qubits — so a total of 2² = 4 possible inputs. We are going to make our “black box function” a 2:1 function which operates according to the bit string “11”. This means that 00 and 11 will be mapped to the same output and 01 and 10 will be mapped to the the same output.

An oracle (i.e. the function) that does this is CX_(1a2a) CX_(1a2b) CX_(1b2a) CX_(1b2b). This basically looks like four CNOT gates between each possible combination of 1 qubit in the first register and 1 qubit in the second register.

First, we import everything.

Second, we code the circuit according to the above six steps. We call it “simon”.

It looks like

Then, we can take 1024 queries of our function

and get

This means that our bit string can either be 00 or 11. If 00 was the only solution, it would mean that our oracle was 1:1, however since it is not, it is a trivial solution. This means that our oracle must be 2:1 and the associated bit string is 11.

If we were to get more columns from this graph — i.e. more possible values for our bit string, we could use gaussian elimination to find the exact solution.