QC — Simon’s algorithm
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.
For example, for a = 011, f fulfills this requirement.
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.
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).
With our example f, the qubits are transformed to:
As shown, there are 4 possible outputs for the second register:
Let’s measure the second register. Say, our measurement is 110.
With this measure, the superposition of the first register becomes:
Time to apply 3 Hadamard gates again. The Hadamard operation is defined as:
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.
Below, we demonstrate how the first qubit is transformed under a Hadamard gate.
Notice that some of the sign of the amplitude has changed due to
For example,
We repeat the gates two more times and get
Before applying the Hadamard gates above, the superposition is
which can be rewritten as
After applying the Hadamard gates, we make a measurement. This measurement z will fulfill the relation below (with proof later).
where zᵢ is the corresponding qubit of z. As shown in our previous calculation, our measurements will produce one of the following values.
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.
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:
Let’s work out the Math a little bit more to show
After the Oracle function, the two registers becomes:
Next, we measure the second register and the first register becomes:
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:
Let’s apply it to the first register.
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.
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.
Even the coefficient above may have a different sign, they all have the same probability of measurement which equals
With enough measurements, we can find all n measurements needed to solve a.
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.
