Random thoughts, daily life, being a student, quantum computing.

2008-10-01

Grover's search algorithm, Part 1

So, as I've alluded to over the past while, I have written a quantum compiler and associated emulator. First, what's the difference between a simulator and an emulator. Well, to my mind, a simulator typically "roll's the dice" as it proceeds. Quantum algorithms tend to end with probabalistic results. For example, Grover's search with 3 qubits gives the correct result with a probability of .945. A simulator will use a random number generator to show the correct result 94.5% of the time, and the wrong result 5.5% of the time. Naturally, you have to run it a few times to be sure you have the correct result. (OK - not too many :).



With an emulator, you see all the potential results and their probabilities.


In the above diagram, you can see the desired result is 6 (110) and the probability of getting any other result is .007813 . (A green dot is a probabilistic integer, the blue dot is a leaf - think of it as an entry in the "matrix" describing the quantum state).

So - how do we do this... Well, with QPL, we write this code:


#Import gtrans.qpl
#Import qubitListToInt.qpl
#Import intToZeroQubitList.qpl

main ::()=
{
dataqbs = intToZeroQubitList(15|);
hadList dataqbs;
doNGrovers(4) dataqbs;
i = qubitListToInt(dataqbs);
}



The #Import constructs work similarly to Haskell's import, brining in the code at the named file.

The main function consists of 4 statements. The first creates what can be called a quantum integer, consisting of a list of qubits. The 15 is a classical value and represents the largest integer we would like to store (as an unsigned value). The next statement calls a function that will apply the Hadamard transform to each of the qubits. We then apply Grover's transform to the list (see the next posting), convert back to a probabilistic integer by measuring each of the qubits and voila - the answer appears.

Next posting - more details about the doNGrovers function.

No comments: