QC — Simon’s algorithm

Image for post
Image for post
Photo by Joanjo Pavon

Simon’s algorithm is another algorithm mentioned frequently in quantum computing. We will take some time to study it because it demonstrates some techniques that are different from what we discussed so far.

Simon’s algorithm

Consider a function that fulfills the following condition.

Image for post
Image for post

For example, for a = 011, f fulfills this requirement.

Image for post
Image for post

Let’s solve the problem with a 6-qubit system. The first three qubits form a register to store x and the last three qubits from a second register to store f(x). First, we prepare the superposition of the first register below using the Hadamard gates.

Image for post
Image for post

We apply a controlled-not U gate with the first 3 qubits as controls and the last 3 qubits as targets. Therefore, the last 3 qubits become f(x).

Image for post
Image for post

With our example f, the qubits are transformed to:

Image for post
Image for post

As shown, there are 4 possible outputs for the second register:

Image for post
Image for post

Let’s measure the second register. Say, our measurement is 110.

Image for post
Image for post

With this measure, the superposition of the first register becomes:

Image for post
Image for post

Time to apply 3 Hadamard gates again. The Hadamard operation is defined as:

Image for post
Image for post

where ⟨x, z⟩ is the bitwise addition modulo 2 — we perform a bit-wise multiplication of x and z (xᵢ · zᵢ) and “exclusive or ⊕” all the results.

Image for post
Image for post

Below, we demonstrate how the first qubit is transformed under a Hadamard gate.

Image for post
Image for post

Notice that some of the sign of the amplitude has changed due to

Image for post
Image for post

For example,

Image for post

We repeat the gates two more times and get

Image for post
Image for post
Source

Before applying the Hadamard gates above, the superposition is

Image for post
Image for post

which can be rewritten as

Image for post
Image for post

After applying the Hadamard gates, we make a measurement. This measurement z will fulfill the relation below (with proof later).

Image for post
Image for post

where zᵢ is the corresponding qubit of z. As shown in our previous calculation, our measurements will produce one of the following values.

Image for post
Image for post

Next, we use these measurements z to solve a. The measurement |000⟩ gives us no useful information in solving the problem but the last three measurements produce three equations with three unknowns.

Image for post
Image for post

Therefore it can be solved and the solution for a is either 011 or 000. We know a=0 is not the solution we are looking for. Therefore a = 011.

Here is the quantum circuit we get:

Image for post
Image for post

Let’s work out the Math a little bit more to show

Image for post
Image for post

After the Oracle function, the two registers becomes:

Image for post
Image for post

Next, we measure the second register and the first register becomes:

Image for post
Image for post

Because the equations below come from another source, the equations below use a slightly different notation. In particular, y is actually the z before and z is actually x. Recall the result of the Hadamard gates as:

Image for post
Image for post

Let’s apply it to the first register.

Image for post
Image for post

Let’s consider the case where ⟨a, y = 1. It turns out it will produce a destructive interference that cancels each other out. i.e. there is no chance our measurement will have ⟨a, y = 1.

Image for post
Image for post

Since ⟨a, y⟩ is a modulo 2 operation, it has a value equals to 0 or 1. So let see what happen when ⟨a, y⟩ =0.

Image for post
Image for post

Even the coefficient above may have a different sign, they all have the same probability of measurement which equals

Image for post
Image for post

With enough measurements, we can find all n measurements needed to solve a.

Image for post
Image for post

Next

This is the final algorithm before we discuss one of the most famous quantum algorithm: Shor’s algorithm. The algorithm discussed so far is more like a toy experiment. Shor’s algorithm is the real deal in demonstrating quantum computing.

Written by

Deep Learning

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store