Grover's Algorithm for Idiots (and Computer Scientists)

Physicists need to figure out how to make the concepts of quantum computing easier to understand for computer scientists. Gate & qubit based QC simulation consists exclusively of the matrix algebra of multiplying state vectors by unitary matrix operators. All of this bra-ket notation is unfamiliar and needlessly complex! (OK, at least for the "obvious basis functions" of gate-based QC).

So download QCF and fire up Octave and we'll get going with a real example of Grover's Algorithm, except you may actually be able to understand what I doing this time!

First, add the QCF path:

octave-3.4.0:1> addpath("/pathtoqcf/qcf")

Now we'll set up a 2-qubit state vector, which of course will have 2^2=4 states. The state vector will be initiated to 100% probability of being in state #0, which represents binary string "00":

octave-3.4.0:2> psi=bin2vec("00")

psi =

1

0

0

0

To be clear, the column vector psi (what physicists would call a "ket", or |psi>) is a representation of the possible quantum states of the qubits. Here in a 2-qubit system, the first entry refers to the state of 2 qubits being "00". The second entry refers to the state of the 2 qubits being "01", the 3rd "10", and the 4rth "11". You take the absolute square of the states to determine what their probability is. In this case, the probability of the 2 qubits being "00" is 1*1=1, or 100%, and the probability of the 2 qubits being any of the other states is 0*0=0, or 0%. So we can say these qubits have a 100% chance of being "00" when measured.

Now here is the 2-qubit (i.e. 4 state) Walsh Hadamard operator:

octave-3.4.0:3> H=hadamard(2)

H =

0.50000 0.50000 0.50000 0.50000

0.50000 -0.50000 0.50000 -0.50000

0.50000 0.50000 -0.50000 -0.50000

0.50000 -0.50000 -0.50000 0.50000

Which we will apply (using multiplication as always) to our state vector to make it an even superposition possibility of all possible states:

octave-3.4.0:4> psi=H*psi

psi =

0.50000

0.50000

0.50000

0.50000

Now the probability of the 2 qubits being in any of the possible states ("00","01","10","11") is 0.5*0.5=0.25, or 25%. If you were to measure them now, all states are equally possible.

OK, now we are initialized and ready to go. We are going to repeat the algorithm loop about (pi/4)*sqrt(number of states). In our case, that is 1.57 times. So we only need to iterate once, thus making the example pretty simple.

We first will apply the "oracle" operator, which inverts the element of the state vector that we are searching for. Just how we really make the oracle operator using quantum computing I hope to show in a later blog post (really!)

QCF has a way to make you an oracle operator based on an algorithmic function. Here is my oracle algorithmic function, which returns a "1" for state #2 (meaning qubit state "10", and I am counting the states up from zero), and "0" for everything else, which I will save as "oracle.m":

function b = oracle(i)

%true for x='10' i.e. state #2

if i==2

b=1;

else

b=0;

end

We feed that into QCF's "vf" function, which bakes you up an oracle unitary matrix operator based on my algorithmic function oracle over 2 qubits (i.e. 4 states):

octave-3.4.0:5> V_oracle=vf('oracle',2)

V_oracle =

1 0 0 0

0 1 0 0

0 0 -1 0

0 0 0 1

And you can see where state #2 is going to be inverted. So let's apply the oracle operator:

octave-3.4.0:6> psi=V_oracle*psi

psi =

0.50000

0.50000

-0.50000

0.50000

Now here comes the Grover's diffusion operator. Some people will tell you the diffusion operator is:

Well, in case you can't parse that crazy bra-ket physics-talk, the diffusion operator actually is defined as a unitary matrix like this:

A[i,j]=2/N for i<>j, A[i,i] = -1 + 2/N

A little easier to understand, huh? Best of all, you don't need to write a function to build this matrix, QCF will bake up your diffusion operator as well, here is the q-qubit (4 state) version:

octave-3.4.0:7> D=ia(2)

D =

-0.50000 0.50000 0.50000 0.50000

0.50000 -0.50000 0.50000 0.50000

0.50000 0.50000 -0.50000 0.50000

0.50000 0.50000 0.50000 -0.50000

Now apply the diffusion operator to the state vector:

octave-3.4.0:8> psi=D*psi

psi =

0.00000

0.00000

1.00000

0.00000

In this trivial example after one iteration, the desired state (#2 counting up from 0 again, corresponding to the qubits being "10") already has a 100% probability of being measured. In case you don't believe me, go ahead and measure the qubits:

octave-3.4.0:9> measure(psi)

ans =

0

0

1

0

Or in terms of qubit binary values themselves:

octave-3.4.0:10> pretty(measure(psi))

ans = 1|10>

where 1|10> means a 100% chance of being in state "10". Wasn't that easy????