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


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.


What to do, what to do ...

Every few months, I feel like I go through a "blogspurt", where I just want to get out and blog.

Then, it tapers off and nothing appears for the next 6 months. I've had thoughts of posting daily, and those just peter out over time.

So, what next?

I'm back taking a class at the U of C.

Oh yes - the other thing is that I have Grover's search algorithm working for at least up to 8 qubits. I actually use that as a benchmark as I make changes / updates in my quantum stack compiler and emulator.

So, I keep thinking about this and that's what I'm going to do. Start blogging about the quantum algorithms I've been programming.


Some of Washington's Wonders

So, while down visiting my sister here in the sunny state of Washington (No kidding - the weather is fantastic), I heard on the news that 16% of the drivers here are uninsured. I find that simply a manifestation of insanity. How can people tolerate this? What's more, how can they tolerate a government that does nothing about it? Apparently the fine for no insurance is a paltry $250. My god!

In Alberta, where I drive, you can't renew your license without proof that you are insured. In fact the penalty for even trying is a court appearance. I'm sure there are some drivers that let their insurance lapse, but in a recent thanksgiving blitz, only 13 drivers were found to be uninsured out of over 2000 infractions! We have some hefty fines if you fail to produce an insurance card and if you repeat offend, your license will be suspended.

But possibly what is more interesting is that our culture in Canada tends to make it unthinkable to even consider driving with no insurance. See for instance the PDF of uninsured drivers estimates at http://www.ircweb.org/News/20060628.pdf.

But enough shaking my head negatively in wonder, let's take a look at the Ferries! Fantastic items man. I'm currently sitting on the Kingston - Edmonds ferry (Near the start of the line - yay!) and what a cool thing. On top of that, I'm able to connect via their wireless network and post this little item - again - major coolness. BC Ferries just don't seem to compare.

Well - maybe not so cool. It is one of those pay for access plans. Guess I'll post later.

On a final note - what's with all the ColdFusion pages in government sites? Don't they know how to write JSP?


Blogging by email

As I've said on other posts, I don't know where people find the time to live as well as blog.

Perhaps email blogging is the key!

Here I am sitting on the bus typing away on a Blackberry, filling in what I want to blog. I spend approximately an hour a day on the bus.

Lately that time has been devoted to studying type theory, but why not use some of it for the blog?

(Addendum - Sadly the bb I have appends a ton of corporate stuff - not that suitable for this. Sigh)


64 Bits and lovin' it

So, I finally bought a recent computer and have a bit of memory now (8GB - Yay). Note that when you install a 32 bit OS, you just don't get to see those extra gigs (oops :).

A brief note about this thought, when you install some x86_64 apps outside of ubuntu's managed packages, you may need to install the package "ia32-libs". This happened to me when I finally gave up trying to get vmware 5.5 working and downloaded the 64bit version 6. It installed and ran, but when trying to start a machine it failed with the error "Failed to connect to process". Sheesh!

Luckily I found the fix eventually through google.

Now to see how the quantum orderfinding goes...