Sunday, November 15, 2009

NIST Creates a 2 Qubit Programmable Quantum Computer

At the National Institute of Standards and Technology (NIST) they've done it again: they've created a 2 qubit programmable quantum computer. The key word here is programmable, it can carry out an arbitrary sequence of operations. We still need to scale things up, but this is another important milestone.


(NIST Post doc David Hanneke doing a demo of the quantum computer. Image from NIST.)

Reducing Memory Requirements in Cove

With Cove, I've never spent much time on making the simulation efficient. Instead I've been focusing my efforts on creating a usable framework. Furthermore, once we have quantum computers any work spent on efficient simulations is largely a mute point.

Not taking into account tricks for efficient simulation, any simulation of a quantum computer requires exponential memory. This is best illustrated by expressing a quantum register (a collection of qubits) as a matrix. Each cell in the matrix is the probability amplitude of the register collapsing to that state. (These are also complex numbers.) As an example, we can consider a two qubit register:

So that's why we need an exponential number of cells: 1 qubit is expressed by 2 complex numbers, 2 qubits by 4 complex numbers, 3 by 8 complex numbers, and so on.

Operations are expressed by a 2^n x 2^n matrix, when they operate on n qubits. So a controlled not operation is a 4 x 4 matrix. Simple linear algebra shows how the operation is applied, here is an example of performing a not operation:

The math dictates that the operation is that 2^n x 2^n matrix. So what happens when the not operation is applied to a 4 qubit register? In Cove I used explicit matrix expansion [1]. That means that the matrix of the operation is expanded, in this case it would be a 16 x 16 matrix. Obviously this eats up a bunch of memory and this was pretty obvious early on. So to apply an operation on a n qubit register I needed 2n + (2^n)^2 complex numbers: the 2n for the state of the register before and after, and the (2^n)^2 for expanded operation. With this I hit memory limitations with no more than a few handfuls of qubits.

This past week I reduced the memory requirements quite a bit in change set [925]. This is something I've been meaning to do since this past spring. Basically what I did was expand the operation matrix one row at a time instead of all at once. This essentially cut the memory requirements down to 3n for a n qubit matrix. So I should be able to simulate much larger systems now.

References

[1] L. Spector, Automatic Quantum Computer Programming: A Genetic Programming Approach, 1 ed. New York, NY: Springer Science and Business Media, LLC, 2004.

Thursday, November 12, 2009

Cove Dissertation Published on arXiv Today

My dissertation on Cove, my framework for quantum computing, was published on arXiv today. Here's the link: http://arxiv.org/abs/0911.2423. I've already posted several other locations it can be obtained from, but arXiv is a pretty well known site for others in the field.

Friday, November 6, 2009

Overcoming Decoherence

Here's a good article in this month's Scientific American: How Noise Can Help Quantum Entanglement.

Decoherence is the largest obstacle in the physical implementation of quantum computers, so steps towards overcoming the current problems with it are important.