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.

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.

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.

On SlideShare- Cove: A Practical Quantum Computer Programming Framework

Here's the slide share presentation of the final draft of my dissertation on Cove.

Cove: A Practical Quantum Computer Programming Framework

View more documents from mpurkeypile.

Ramping up work on Cove again

I really have not spent too much time working on Cove (my quantum computing framework) for a few months while I wrapped up my dissertation and took some time off. I'll be starting to ramp up work on Cove again in the coming weeks. My initial target will be reducing the memory requirements of the simulation so that I can carry out larger ones. (Efficient simulation has never been a goal.) After that I plan to continue the factoring example, followed by work on some papers.

Limit on rate of quantum computing

Levitin and Toffoli recently published a paper in Physics Review Letters titled "The fundamental limit on the rate of quantum dynamics: the unified bound is tight" [1]. The title is a pretty academic sounding, but the final sentence of the abstract sums it up perfectly: "These results establish the fundamental quantum limit on the rate of operation of any information-processing system." Hitting this limit will take decades if Moore's law keeps up however. There is a great summary on the paper here and you can find the entire paper on arXiv here [1].

It is impressive that this limit has been established, but there is still a lot of work ahead to reach this limit. Nonetheless we should be able to do impressive things regardless of this limit. Turing started establishing what we could compute in the 1930's [2], but that hasn't had a noticeable impact to the average person on what computing technology can accomplish. Think of all the possible improvements in algorithms as well. While there may be a limit on the speed of computation, algorithms may lend short cuts that render the limit a mute point. In quantum algorithms especially, we have quite a ways to go with only a handful of practical ones at present. Furthermore, these existing quantum algorithms have shown that previously hard problems can be made practical via quantum computation.

The name Toffoli will ring a bell to those familiar with quantum computing. The Toffoli gate, or controlled controlled not, is one of the fundamental gates. Furthermore the reversible equivalent of any classical computation can be constructed using Toffoli gates [3].

References
[1] L. B. Levitin and T. Toffoli, "The fundamental limit on the rate of quantum dynamics: the unified bound is tight," Physics Review Letters, vol. 103, 13Oct2009 2009.

[2] A. Turing, "On Computable Numbers, with an Application to Entscheid-ungsproblem," Proc. London Math Society, vol. 42, pp. 230-265, 1936.

[3] M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information, 1 ed. Cambridge, UK: Cambridge University Press, 2000.