Why we should program quantum computers with frameworks

I knew when I started my doctoral research at Colorado Tech that I wanted to do it in quantum computing. I work on software for a living, so I was thinking it would be good if I could combine the two somehow. It didn't take me long in my literature review to come across and settle on quantum computer programming as a research area as a way to blend on these two areas.

One thing really stood out to me at first: most of the existing proposals for quantum computers were languages designed for quantum computing. However, I think there are very strong reasons for creating frameworks on top of existing classical languages instead of creating new languages:

1. Over 8500 programming languages have been created [1], but in reality only a few see any sort of wide spread use. In my opinion, it is highly unlikely that we'll adopt new languages solely for the purpose of quantum computing.
   
2. By creating a new language the designer(s) must tackle not only the quantum issues, which are hard enough, but all the classical ones as well. We've spent years on classical languages, the focus of quantum programming design efforts should be on quantum computation, not rehashing classical problems. Tackling the classical issues as well distracts from the goal at hand.
   
3. Quantum computing is only typically utilized for part of the computation. Take Shor's algorithm for factoring [2] as an example: a quantum computer is utilized only for part of the algorithm, the rest is classical. Put that in the bigger picture of whatever software is doing the factoring and it becomes clear that quantum computing really does fit into Knill's QRAM model [3] where the quantum computer is a resource of the classical computer.
4. Frameworks are meant to be extended, perhaps in ways the designer didn't envision. Frameworks are much easier to extend (through hot spots [4]) by their very nature than languages are. Extending the framework can lead to more elegant solutions and more readable code as opposed to trying the bend a language to accomplish something the designer didn't intend or want to allow.
   

These were some of the factors that really motivated me to create Cove as a framework instead of creating yet another language. (Cove is a quantum computing framework developed as part of my Doctoral research.) That isn't to say that there aren't a lot of good lessons to be learned from languages- I drew a lot from Omer's QCL [5] as an example. I also drew a lot from Bettelli [6, 7], who also made the point that we should program quantum computers by expanding classical languages.

(I've written about this previously in my dissertation on Cove to a certain degree, this just makes it more explicit in a more condensed blog format.)

References
[1] T. J. Bergin, "A History of the History of Programming Languages," Communications. ACM, vol. 50, p. 5, May 2007 2007.

[2] P. W. Shor, "Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer," SIAM Journal on Computing, vol. 26, p. 25, October 1997 1997.

[3] E. Knill, "Conventions for Quantum Pseudocode," Los Alamos National Laboratory LAUR-96-2724, 1996.

[4] H. C. Cunningham, L. Yi, and T. Pallavi, "Framework design using function generalization: a binary tree traversal case study," in Proceedings of the 44th annual Southeast regional conference Melbourne, Florida: ACM, 2006.

[5] B. Omer, "A Procedural Formalism for Quantum Computing," in Theoretical Physics. vol. Masters Vienna: Technical University of Viena, 1998, p. 93.

[6] S. Bettelli, "Towards an architecture for quantum programming," in Mathematics. vol. Ph.D. Trento, Italy: University of Trento, 2002, p. 115.

[7] S. Bettelli, T. Calarco, and L. Serafini, "Toward an architecture for quantum programming," The European Physical Journal D - Atomic, Molecular, Optical and Plasma Physics, vol. 25, p. 19, August 2003 2003.

GHz Manipulation of Quantum States of Electrons

At UC Santa Barbara they've moved forward in manipulating the state of electrons within diamonds at GHz rates. (UCSB Press release here. Page of UCSB's Center for Spintronics and Quantum Computation here.)

Lead author, Post-Doc Greg Fuchs of UCSB.

Paper: Evolution of Quantum Systems by Diagrams of States

I came across this paper on arXiv, titled "Evolution of Quantum Systems by Diagrams of States" by Felloni, Leporati, and Strini. You can get the paper from arXiv here.

I've only skimmed it so far, but it is good to see this sort of thing. I suppose by the nature of things, quantum computation is very math intensive and we lack good visual representations of things. The only real two exceptions to this are quantum circuit diagrams and the Bloch Sphere. The circuit diagrams represent the application of operations to quantum registers (collections of qubits). As an example, here is the circuit diagram to construct a Sum operation from elementary operations:

The other big graphical representation we have is the Bloch Sphere. Basically this is a way of viewing the state of a single qubit on a sphere. In this the poles (of the z axis) represent |0> and |1>, and a point on the surface represents the state of the qubit. This is great for visualizing a single qubit, but doesn't scale beyond that. I wouldn't cite in a paper, but this blog is a more informal forum, so here's the link to Bloch Sphere on Wikipedia. Here's what a Bloch Sphere looks like though:

As I said, it is good to see a paper like this. The abstract the authors put together for the paper sums it up better than I would, so here it is:

We explore the main processes involved in the evolution of general quantum systems by means of Diagrams of States, a novel method to graphically represent and analyze how quantum information is elaborated during computations performed by quantum circuits. We present quantum diagrams of states for representations of quantum states by density matrices, partial trace operations, density matrix purification and time-evolution by Kraus operators. Following these representations, we describe by diagrams of states themost general transformations related to single qubit decoherence and errors.

Diagrams of states prove to be a useful approach to analyze quantum computations, by offering an intuitive graphic representation of the processing of quantum information. They also help in conceiving novel quantum computations, from describing the desired information processing to deriving the final implementation by quantum gate arrays.

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.