Simon’s Algorithm
This algorithm was one of the stepping stone to quantum computing. Previously many have predicted quantum computer to be superior to classic computers but none could actually gave proper applications for quantum. This was the first algorithm to show the computer power of quantum.
Problem Statement
Given a function f:x->y such that there exists a one to one and two to one mapping such that: given x1,x2: f(x1)=f(x2),it is guaranteed :x1⊕x2=b
So here the task was to predict b such that the above condition holds true.
Classical Solution
Classically, if we want to know what bb is with 100% certainty for a given f, we have to check up to 2²^(n−1)+1+1 inputs, where n is the number of bits in the input. This means checking just over half of all the possible inputs until we find two cases of the same output. Much like the Deutsch-Jozsa problem, if we get lucky, we could solve the problem with our first two tries. But if we happen to get an f that is one-to-one, or get really unlucky with an f that’s two-to-one, then we’re stuck with the full 2^(n−1)+1.
In order to solve this in linear time, a quantum solution was proposed:
Quantum Solution
Where the query function, Qf acts on two quantum registers as:
|x⟩|a⟩→|x⟩|a⊕f(x)⟩|x⟩|a⟩→|x⟩|a⊕f(x)⟩
In the specific case that the second register is in the state |0⟩=|00…0⟩|0⟩=|00…0⟩ we have:
|x⟩|0⟩→|x⟩|f(x)⟩|x⟩|0⟩→|x⟩|f(x)⟩
The algorithm involves the following steps.
- Two n-qubit input registers are initialized to the zero state:
|ψ1⟩=|0⟩⊗n|0⟩⊗n
2. Apply a Hadamard transform to the first register:
3.Apply the query function Qf:
4.Measure the second register. A certain value of f(x) will be observed. Because of the setting of the problem, the observed value f(x) could correspond to two possible inputs: xx and y=x⊕by=x⊕b.
Therefore the first register becomes:
|ψ4⟩=1√2(|x⟩+|y⟩)
where we omitted the second register since it has been measured.
5.Apply Hadamard on the first register:
6. Measuring the first register will give an output only if:
which means:
A string z will be measured, whose inner product with b=0. Thus, repeating the algorithm ≈n times, we will be able to obtain n different values of z and the following system of equation can be written:
From which bb can be determined, for example by Gaussian elimination.
So, in this particular problem the quantum algorithm performs exponentially fewer steps than the classical one.
