Thursday, December 24, 2009

Logically manipulating qubits in Cove

In Cove a collection of qubits is represented by an instance of IQuantumRegister. The logical manipulation of qubits in a register is largely inspired by Python's list manipulating, or slicing as it is called. There are a variety of ways these qubits can be logically manipulated, the following illustration demonstrates a few:


In the above the numbers represent the index is represented by numbers, just like you would with an array. The letters A - D represent specific qubits. So you can see the SliceTo(2) operation obtains indexes 0 to 2, resulting in qubits A, B, C. The SliceSubset() operation slices the current indexes to an arbitrary set. In this case the qubit at index 2 (C) will become the first one and the qubit at index 1 (A) will become the second qubit in the new slice.

It is important to point out that each of the slicing operation returns a new instance of IQuantumRegister. This means that the slices can be independently manipulated. That being said, they all share the same qubits: so the manipulation of one slice may impact another. As an example if we perform a Not operation on qubit A, it will be Not'ed in every slice.

This allows for easy applications of operations. Take a CNot (controlled not) operation for example, this is an operation on two qubits. So if we take the original register of 4 qubits and want to perform the operation on qubits A and D we can just do something like this:

MyRegister.SliceSubset(new int[] {0, 3}).OperationCNot();

The OperationCNot() will also return the slice after the operation is performed. So this example shows how operations can be chained together to manipulate the register, then discarded if needed- leaving MyRegister as the original 4 qubits after the above line of code is executed.

Friday, December 18, 2009

D-Wave and Google

Google teaming up with D-Wave has been making a lot of noise lately. I wasn't originally going to write anything about it, until I came across a recent post by Scott Aaronson titled "Hopefully my last D-Wave post ever". I thought the way he wrote it was humorous- I liked the fictional interchange. I recommend reading both the post and comments.

I don't really have too much more to add other than to quote Carl Sagan: "extraordinary claims require extraordinary evidence" [1]. We're still waiting for the extraordinary evidence from D-Wave.

References

[1] C. Sagan, Billions & Billions: Thoughts on Life and Death at the Brink of the Millennium, 1 ed. New York, NY: Ballantine Books, 1997.

Tuesday, December 8, 2009

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.

Thursday, December 3, 2009

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.

Wednesday, December 2, 2009

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.

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.

Saturday, October 31, 2009

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.

Wednesday, October 21, 2009

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.

A quantum crypto network in China

This sounds impressive: Field experiment on a robust hierarchical metropolitan quantum cryptography network. Like a lot of things in quantum information, the leap between the lab and practical real world use is a big one. What I found most interesting about this is the use of quantum routers.

As the article states, routers are needed because of the no-cloning theorem. The no-cloning theorem states that you cannot copy the state of an arbitrary quantum system. In other words you cannot do a copy and paste. You can transfer it, essentially a cut and paste, via teleportation. You cannot do the copy and paste because to copy the system you basically end up doing a measurement, which alters the state of the system.

Thursday, October 15, 2009

Another step forward: Quantum algorithm for solving linear systems of equations

Harrow, Hassidim, and Lloyd have recently published a paper titled "Quantum algorithm for solving linear systems of equations" [1]. You can find the paper here on ArXiv and there is a pretty good summary article here from MIT news. (Lloyd is pretty big in the pop sci world of quantum computing too, he's written Programming the Universe and a recent Scientific American article for instance.)

As the title says, they outline a quantum algorithm for solving linear systems of equations. In other words given:
The algorithm solves for the vector x, when matrix A and b are known. So why is this useful? Linear systems of equations show up all the time. Some diverse examples include: oil exploration, electrical networks, and flight crew scheduling [2] just to name a few. Of course, as they point out even in the abstract, they aren't actually solving for x, but "...an
approximation of the expectation value of some operator associated with x..." [1]. Another highlight is that this algorithm is an exponential speed up over the best known classical value! I recommend the MIT article from above if you want a general overview, or the entire paper (obviously) for all the details.

This is another important step forward we've had recently in addition to the steps forward in physical implementations I've written about here and here. Up until now there are really only two practical quantum algorithms, and they get cited quite a bit: Shor's algorithm for factoring [3] and Grover's fast database search [4]. Both of these where developed in the mid 1990s. Furthermore both of these algorithms have pretty narrow applications, while linear systems of equations are everywhere. We'll see how things pan out, but it could arguably be considered the most important development to date in the currently sparse universe of quantum algorithms.

References

[1] A. W. Harrow, A. Hassidim, and S. Lloyd, "Quantum algorithm for solving linear systems of equations," Phys. Rev. Lett, vol. 15, p. 15, 07Oct2009 2009.

[2] D. C. Lay, Linear Algebra and Its Applications, 1 ed. Reading, MA: Addison-Wesley, 1997.

[3] 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.

[4] L. K. Grover, "A fast quantum mechanical algorithm for database search," Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, pp. 212-219, 1996.

Tuesday, October 6, 2009

Why I Chose to Study Quantum Computing

One of the biggest questions facing doctoral students is: what area will you do your research in? Your choices may vary depending on the school and program. At the very least your research area will play a large role on who serves on your committee. I went to Colorado Tech University's Institute for Advance Studies (CTU IAS) where we were given quite a bit of leeway in the area selected. This post is based on my Doctorate experience at Colorado Tech.

Switching topics can lengthen the time to finish your dissertation, so it is best if you can choose one and stick with it. Obviously this cannot always be the case, but this needs to be kept in mind. Another thing that may lengthen the doctoral process is picking a project that is too ambitious or too much work for a dissertation. If you think about it the end result you need to finish is a dissertation that you've successfully defended and had your committee sign off on. There aren't any more points for doing three times as much work. So with that in mind scope should be limited for your dissertation. Your dissertation can be just the first step and the subsequent steps can be areas for future work.

As is probably obvious from this blog, I selected quantum computing programming as my research area. My focus wasn't so narrow at first, I had originally selected the more general topic of quantum computing. As I read more and more I always kept an eye on the software side of things. My physics background was limited, and I had none in quantum computing. So I had enough work cut out on the general quantum computing side of things. My day job was writing software, so I did feel that I had a perspective that others in the field might not have. Thus my choice evolved into quantum computer programming as I progressed through the literature.

As the tittle of this post says, why quantum computing? Here is a list of the motivating reasons behind the reason I selected quantum computer programming (in no particular order, and not formalized when I did the selection):
  1. Interesting subject. I wanted to pick something I was truly interested in. Without the passion for the subject I wouldn't have been able to sacrifice weekends, evenings, time with friends and family, etc. It was the true interest in the subject that allowed me to spend so much time on it.
  2. Bleeding edge. I wanted to pick something bleeding edge in computer science, as the body of work is much less- which means there are more places to select from for doctoral work. I figured since quantum computers were probably 15+ years out when I started (2006), this met the criteria. I suppose this could also be listed as selection of an "un-matured" area in Computer Science.
  3. Ground breaking area. Since quantum computers operate fundamentally different than classical (existing) computers this pretty much sealed the deal on this one. How much more ground breaking can you get then something that works differently than every other computer built?
  4. "Wow" factor. While it shouldn't really be listed as a criteria for selection of a research area if you want to be formal, it didn't hurt. As any doctoral student is at various points in the process, I became frustrated and stumped. I bring this point up because I was able to sit back and say to myself, "hey this is programming photons (or electrons, etc), this is cool stuff!" I don't think I would've been able to give myself that motivating kick quite as much if I had selected another subject area.
So those were my reasons for selecting quantum computing as a research area. However, the first two are good advice for any doctoral student: pick something you love and pick something years down the road.

Saturday, October 3, 2009

Purkeypile's Top Quantum Computing Papers

I've been meaning to write this ever since I wrote my top books on quantum computing. These following papers are the ones I've found to be the most important from a quantum software perspective as I developed Cove. The references should be enough for you to find a soft copy on the Net.

Founding Works

[1] D. Deutsch, "Quantum theory, the Church-Turing principle and the universal quantum computer," Proceedings of the Royal Society of London, vol. A, pp. 97-117, 1985.

For me, it goes without saying that this is the founding paper for quantum computing. Sure, others such as Feynman (R. P. Feynman, "Simulating Physics with Computers," International Journal of Theoretical Physics, vol. 21, 1982.) kicked around the idea of a quantum computer prior to Deutsch, but Deutsch was the first one to point out that you could utilize a quantum computer to perform something more efficiently than a classical computer via the Deutsch algorithm, which is outlined in the paper. (I don't really count Feynman's simulation of physics.)

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

What is important about this paper isn't really Knill's pseudocode, which I have really not come across much in the literature. What is important about this paper is his QRAM model of quantum computing, which I wrote about a month ago. The QRAM model basically states that a quantum computer is a device that is controlled and utilized by a classical computer. Pretty much every higher level quantum programming model makes use of this structure, although it may be implicit in some of the works.

[3] 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.

I shouldn't really have to write much about this paper. This is the introduction of the often cited factoring example of how quantum computers can usefully do something better than a classical computer.

[4] L. K. Grover, "A fast quantum mechanical algorithm for database search," Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, pp. 212-219, 1996.

Along with Shor's paper, Grover's is the other major practical quantum algorithm to date. Typically either Shor's or Grover's algorithm is used to demonstrate a quantum programming language.

Quantum Software

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

Omer's work is arguably one of the most complete quantum computer programming works, QCL. In fact Yanofsky and Mannucci dedicate a chapter to quantum computer programming in their book, and most of it covers Omer's work (N. S. Yanofsky and M. A. Mannucci, Quantum Computing for Computer Scientists, 1 ed. New York, NY: Cambridge University Press, 2008.). Additionally this is one of the closest works to Cove.

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

Along with Omer's work Bettelli's is the closest to Cove, and I drew a lot of inspiration from the two. Unlike Omer's work, which is a language, Bettelli's is essentially a framework for quantum computing in C++. This is significant because most other quantum programming proposals are languages. Not only have thousands of programming languages been developed (with a very few seeing much use), but designing a programming language requires the author(s) to tackle not only quantum computing, but classical computing too. It is hard enough to do quantum computing right, let alone provide a classical feature set to rival existing classical languages. At the beginning of Bettelli's paper he also outlines some traits quantum programming proposals should realize- I tried to take many of these to heart.

There are many other papers that are also important, but I consider these to be the top six from a software perspective. If you want to read more about the others I consider noteworthy, you can read section 2.2 in my dissertation on Cove.

Tuesday, September 29, 2009

Article on Implementing Quantum Computers

I came across this article: Quantum computers are coming- just don't ask when. I'm no expert on physical implementations of quantum computers, but I thought it gave a good overview of some of the current physical implementations and challenges. The optimistic view of overcoming the challenges for building and quantum computers is right on target in my opinion.

I also thought that the end of the article was particularly noteworthy: it mentions that the first quantum computers may be devices that are originally used as subsystems of classical computers. This is Knill's QRAM model as I've previously written about. It is good to see that the software and hardware worlds of quantum computing are thinking along the same lines for initial implementations. There is a lot of work still to be done, but we're making good progress.

Thursday, September 17, 2009

Cove Dissertation Finished


I've finished my doctoral dissertation at Colorado Technical University, titled "Cove: A Practical Quantum Computer Programming Framework". I'll be pushing it elsewhere onto the net later on, but for now you can down load it from my Cove site here.

Here's the abstract:
While not yet in commercial existence, quantum computers have the ability to solve certain classes of problems that are not efficiently solvable on existing Turing Machine based (classical) computers. For quantum computers to be of use, methods of programming them must exist. Proposals exist for programming quantum computers, but all of the existing ones suffer from flaws that make them impractical in commercial software development environments. Cove is a framework for programming quantum computers that extends existing classical languages to allow for quantum computation, thus providing a quantum computing toolkit for commercial software developers. Since the target users of Cove are commercial developers, it is an object oriented framework that can be used by multiple languages and also places emphasis on complete documentation. The focus of Cove is not so much on the software product, but on the fundamental concepts that make quantum computing practical for common developers.

While a little lengthy, it has a lot of good background information in chapter 2 for quantum computing novices. The circuit diagrams for building up Shor's algorithm in chapter 4 and the complete list of quantum operations should also be interest to some- not to mention the framework itself.

Thursday, September 10, 2009

Chip Scale Quantum Computer


I'd like to thank one of my dissertation readers, Dr. Thompson, for sending this my way: Quantum Chip Helps Crack Code. In a nutshell researchers at the University of Bristol did the part of factoring (finding the period) that needs a quantum computer on a chip sized device that is optical based.

They only did the period finding for factoring 15, which in itself doesn't sound too impressive- but this is on an actual quantum computer. Furthermore this is on a chip sized device, there isn't a need for a whole lab full of equipment to carry this out. Pretty impressive. I don't know if the approach is scalable, but perhaps it points towards our initial quantum computers being too large in size.

This together with NIST's work I wrote about recently has made this a pretty exciting past few months towards realizing commercial quantum computers.

Thursday, September 3, 2009

How will Quantum Computers Apply to Space Travel?


I've always been a big fan of space related things: I nearly wore out my VHS of Carl Sagan's Cosmos as kid and staying up to watch Voyager 2's flyby of Neptune was a highlight of the summer of 1989. (The image is a NASA image of Voyager.)

I've already brought up William Halal's work [1] in a few other posts. In it a Moon base is predicted around 2028 and Men on Mars shortly after, around 2030. Both of these estimates are with slightly more than 50% confidence. At first impression that sounds too soon to me, but then I think about how quickly we put men on the Moon- and with 1960's technology to boot. So after second thought it sounds reasonable. (I also recommend checking out Dr. Zubrin's Mars Society and work on Mars Direct, especially for those who don't think it is possible.)

So of course my mind started wondering, how will quantum computers play a role in space travel? The one area that jumps to the front of my mind is the simulation of quantum systems. A simulation could be used to investigate the potential of different propulsion schemes for example. Any simulation of a quantum system experiences an exponential slow down in the worse case on a classical (existing non-quantum) computer. So with a quantum computer you can do the sorts of simulations you wouldn't be able to do even if you had every classical computer in the world at your disposal. Who knows, maybe in Star Trek they're actually predicting problems with the warp core with a quantum computer? :)

I'm not saying that we need quantum computers for space travel. I see quantum computers as a specialized resource, as I mentioned in my More Thoughts on Quantum Computers Becoming a Reality post a few weeks ago. What I am saying is that maybe they will help us tackle some of these hard problems to make longer distance space travel a reality more quickly and/or perhaps more safe.

For more on Mars Direct, also check out one of Dr. Zubrin's latest speeches:


References
[1] W. E. Halal, Technology's Promise: Expert Knowledge on the Transformation of Business and Society, 1 ed. New York, NY: Palgrave Macmillan, 2008.

Tuesday, August 25, 2009

Animoto Video of Cove

I was playing around with Animoto, which lets you put together a video to music from images and music. It is pretty simple to use and does a great job of blending the music and video.

I put together a quick little video (30 seconds) using some images from my dissertation on Cove:



Per Dr. Calongne's suggestion I used music from the Animoto site itself to avoid any digital rights problems.

Tuesday, August 18, 2009

More Thoughts on Quantum Computers Becoming a Reality

I wrote a few weeks ago in a previous post about William Halal [1] and when we'll have quantum computers. To summarize: the best guess he's gathered from consulting a bunch of experts is 2021 plus or minus 5 years- which seems reasonable to me.

Current computers where an expensive resource when we first had them. It took decades until they were cheap and practical enough where you could have one at home. I think the same will be true with quantum computers, they'll be very expensive at first. For this reason I see them being a shared resource at first. In other words it will be something that multiple classical computers share. That sharing could be at the institution level, such as a university having some available much like early computers. It also isn't unreasonable to think that processing time could be rented out on it, much like Amazon's EC2.

One obvious question is how the classical computers will interact with the quantum computer. Nearly all proposals for programming quantum computers explicitly or implicitly make use of Knill's QRAM model [2]. In Knill's QRAM model the classical computer is the master and the quantum computer is the slave:

Things get a little more complicated when you throw in multiple classical computers for a single quantum resource. Each of them cannot have full control of the quantum resource and have it function correctly. However, Knill's QRAM model can be expanded to include a "quantum controller" between the classical computer(s) and quantum resource:
This has the advantage that all the logic to deal with the clients can be built into the quantum controller. The controller could also talk to the clients through a standardized protocol, meaning that different physical implementations of quantum computers could still be utilized through the same interface. The controller could also do some other things:
  • Queue up requests for operations from a client and execute them at once.
  • On the fly optimization?
  • Deal with disconnected clients at any stage in the computation.
The list goes on. Obviously the implementation of this is hard. How exactly do the controller and classical computers communicate for instance? A lot of work would have to go into this, which is why I've listed it as an area for future research in my dissertation. Like programming quantum computers, I think we're best off tackling this issue before quantum computers become a reality outside the lab. Doing so will allow us to hit the ground running with quantum computers instead of stumbling along like we did in the early days of classical computing.

References
[1] W. E. Halal, Technology's Promise: Expert Knowledge on the Transformation of Business and Society, 1 ed. New York, NY: Palgrave Macmillan, 2008.
[2] E. Knill, "Conventions for Quantum Pseudocode," Los Alamos National Laboratory LAUR-96-2724, 1996.

Thursday, August 13, 2009

Quantiki



Quantwiki (http://www.quantiki.org/) is essentially a free content quantum information science site, meaning anyone can create and add content. The content includes wiki articles, discussion forums, news, job postings, and more. The links to recent papers on various sites/journals is also useful. Since the site not only hosts forums, but has articles and other contents, makes it a good place for the community to carry out discussions and serve as a good repository of related information for the quantum information science community.

Tuesday, August 11, 2009

A Step Towards Practical Quantum Computers

This was passed on to me from the head of my Doctoral committee, Dr. Sanden: At NIST they've implemented successive quantum operations on qubits, in addition to multiple teleports. You can check out the article on Technology Review here.

While I'm not a physicist, and thus less involved in physical implementations of quantum computers, this is pretty exciting news. Decoherence is a big problem in physical implementations- essentially the state unintentionally collapsing through inadvertant measurement. When any measurement (perhaps partial) occurs the qubits collapse from possible superposition to a state that can be represented classically, that is by bits instead of qubits. So essentially one can think of decoherence as unintended measurements taking a system out of superposition.

(On a somewhat related note, this is why quantum operations must be reversible. Irreversible operations require energy to erase information, and input of energy acts as a measurement.)

Wednesday, August 5, 2009

Top Books on Quantum Computing

During the course of writing my dissertation I looked at every book on quantum computing that I could get my hands on, and ended up purchasing many of them. I thought it would be helpful to others, especially those new to the subject, to post what I consider the essential books on quantum computing. I've posted the reference for each, along with a few sentences about what I liked about the books. The reference should be enough for you to find it at your favorite bookstore. The books are not listed in any particular order.

A lot of material in the books overlaps each other, but I found that having several slightly different explanations helped to understand things better. Additionally, I came to find that some books had more complete coverage about certain topics. Keep in mind that my area is computer science- this means that I was more concerned with how quantum computers work mathematically as opposed to how to physically implement them.

Purkeypile's Essential Quantum Computing Texts



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

This is considered by many to be the essential text on quantum computing. Its coverage is pretty thorough, so you can usually find what you're looking for. However, the explanations can be a little brief, so I think the other texts are better for beginners. This was typically one that I used as a reference to find some details that might not be in the others.


[2] P. Kaye, R. Laflamme, and M. Mosca, An Introduction to Quantum Computing. New York City, New York: Oxford University Press, 2007.

I found this one did a great job on explaining the mathematics of quantum computing in the early chapters. If I had to pick one book to explain the basics of quantum computing, this would be it.


[3] M. Nakahara and T. Ohmi, Quantum Computing: From Linear Algebra to Physical Realizations, 1 ed. Boca Raton, FL: CRC Press, 2008.

I include this book not just because of the great and easy to read coverage of the entire subject, but also because of the complete example on factoring. Many papers and texts just treat part of factoring as a sort of a black box. If you want to know how to implement factoring from elementary operations, this is the book you have to have. This has been my most referenced book while trying to carry out more complex simulations.


[4] N. S. Yanofsky and M. A. Mannucci, Quantum Computing for Computer Scientists, 1 ed. New York, NY: Cambridge University Press, 2008.

This is another great book that covers all the necessary introduction topics. I include this book in the list partially because it is the only text I've come across that dedicates an entire chapter to quantum programming.


Worth Looking At

[5] M. Hirvensalo, Quantum Computing, 2 ed. Berlin: Springer, 2004.

This one has a good introduction to quantum information. I also found myself consulting this one if I wanted an alternate explanation of something I read in the Kaye text.

[6] N. D. Mermin, Quantum Computer Science: An Introduction, 1 ed. Cambridge, UK: Cambridge University Press, 2007.

This is one of the few books geared towards computer scientists. As such it had a refreshing view and made note of things that are of importance to a computer scientist, but not necessarily a physicist.

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

I include this one because it covers some aspects on simulation (albeit somewhat indirectly) that I didn't find covered in other texts. In particular, the algorithm for expanding a gate matrix was useful. It is also an interesting read.

[8] S. Loepp and W. K. Wootters, Protecting Information: From Classical Error Correction to Quantum Cryptography, 1 ed. New York, NY: Cambridge University Press, 2006.

This one is worth mentioning because of the coverage of quantum cryptography and good overall look at information in general.
--------

Perhaps in the future I'll also post some of the papers I consider essential, or some of the more popular science type books on quantum computing.

Tuesday, August 4, 2009

Structured Design Process and Drug Development


Alexander Christakis writes a lot about using the structured design process (SDP) in his book "How People Harness their Collective Wison and Power to Construct the Future in Co-Laboratories of Democracy" [1]. (You can get it here on Amazon in hardcover.) In particular in chapter 14 he writes about how using SDP can short end the front end work necessary for drug development. As an example he suggests workshops that can cut time for some processes down from weeks or months to just a few days. I think the key point is really that we can dramatically decrease the time our processes take just by changing the process itself.

Drug development is one area I think quantum computing holds the potential to really make an impact in. Often when one hears about quantum computing Shor's algorithm (factoring) and Grover's algorithm (unsorted search) are the two examples that are frequently cited. Simulating quantum systems is often missing from this list. Just think of what all we'd be able to do if we could efficiently simulate a quantum system (via a quantum computer)... I think this extends beyond drugs into physics and probably a bunch of other areas we cannot even think of at this point.

References
[1] A. N. Christakis and K. C. Bausch, How People Harness their Collective Wisdom and Power to Construct the Future in Co-Laboratories of Democracy, 1 ed. Greenwich, Connecticut: Information Age Publishing, 2006.

Tuesday, July 28, 2009

William Halal on Quantum Computing

William Halal published a book titled "Technology's Promise: Expert Knowledge on the Transformation of Business and Society" in 2008 [1]. (You can find it here on Amazon.) I had read an early draft of the book in the summer of 2007 prior to a presentation he did at Colorado Technical University's Institute for Advanced Studies.

Quantum computers currently don't exist outside the lab. What we do have in the lab doesn't consist of more than a few handfuls of qubits. This is because physically implementing quantum computers is a very hard task do to decoherence. In other words the system must be isolated from the outside environment. If the qubits interact with the outside environment then it is an observation and the system will "collapse" out of superposition and yield a classical result.

Given the difficulty in implementing quantum computers, there are a wide variety of guesses on when and if they'll become available. I've heard everything from we have them now (D-Wave systems) to we'll never have them.

What William Halal has done is utilize the work of the TechCast project to gather the opinions of 100 experts to come up with best guesses. (These experts are gathered from around the world.) According to this, he lists that "...quantum computers are likely to become available about 2021 +/- 5 years" in "Technology's Promise".

I think the prediction of 2021 is a reasonable one. This still gives us 12 years to overcome the challenges of creating them, which is quite a long time in technology. I wouldn't be too surprised if some hurdles pushed us out a few years, but I also wouldn't be surprised if we made some leaps that also rained the date in a few years. In any case, I expect to see some big advances toward making quantum computing a reality in the next decade or two.

References
[1] W. E. Halal, Technology's Promise: Expert Knowledge on the Transformation of Business and Society, 1 ed. New York, NY: Palgrave Macmillan, 2008.

Wednesday, July 22, 2009

Splice for Web Service Mashups

This post plays off the previous on cloud computing. Full disclosure: I work for Xignite and helped to write Splice.



Splice is a web service mashup platform that allows you mix and mash web services. (One can think of this as combining the results from multiple web services and altering the output as desired: renaming, dropping, and restructuring the output.) The development environment is graphical meaning that you can do all this without any programming. It also has the added benefit of making web service calls in parallel where possible. Often in programming parallezing parts of a program can be difficult, so this is an important benefit. Thus one can think of Splice facilitating the customized exchange of data between systems via web services.

So how does this fit in with quantum computing? One could use it to tie together various simulation pieces to facilitate simulations across various systems.

Tuesday, July 21, 2009

Cloud Computing


The Horizon Report (2009) lists cloud computing as a technology taking hold in one year or less [1]. I would argue that it has taken hold already, as the article lists several examples.


How does cloud computing play into quantum computer programming? I see it as having the potential for carrying out large simulations of quantum computers. With Cove [2] I ran into memory and computation constraints pretty early on when simulating just a few handfuls of qubits. Taking advantage of multiple cores is an obvious first step, but utilizing the cloud would allow for even larger simulations. Of course the problem has to be decomposed to take advantage of the cloud, but simulations essentially boil down to multiplication between large matrices.

Of course an obvious advantage of using the cloud is the pay as you go model. Instead of building up a lab to run my simulation, I can just take advantage of the cloud and avoid the expense and overhead of setting up this lab.

References
[1] NMC. (2009). Cloud Computing - The Horizon Project, New Media Consortium, 2009. Retrieved July 21, 2009, from http://horizon.nmc.org/wiki/Cloud-Computing
[2] https://cove.purkeypile.com/

Cove Presentation Posted

I did a presentation on Cove (the quantum computer programming framework I've developed) last week at Colorado Technical University. It is the slides that are in the last post, along with my presentation of them and some question and answers.

Friday, July 17, 2009

Cove: A Practical Quantum Computer Programming Framework

My doctoral research at Colorado Technical University has been in quantum computer programming. As part of that I developed a framework for programming quantum computers, called Cove. You can find presentations, source code, etc on the site for Cove.

The slides from my dissertation defense give a pretty good introduction to quantum computers, and how Cove fits in. You can find the slides on the Cove website or on slideshare.net:

Tuesday, July 7, 2009

David Detsch on TED Talks

David Deutsch is considered by many people, myself included, to be one of the founders of quantum computing. This is something he introduced in the mid 1980's by showing something that could be done with a quantum computer that couldn't be done with a classical (modern) computer [1]. This is known as Deutsch algorithm, although it wasn't very useful. Consequently quantum computing was something of an oddity until Peter Shor introduced his factoring algorithm in the mid 1990's [2].



While this TED Talk is several years old, I still find it an interesting talk from one of the father's of quantum computing: http://blog.ted.com/2006/09/david_deutsch_o.php. In this talk he brings up two points that I find pretty interesting and worthy of some more discussion:
  1. What can be done is really only limited by the laws of physics. If the laws of physics don't prevent it then it is really only our lack of knowledge on how to do it.
  2. He advocates that we need to be able to fix problems, not just prevent them. He applies this to the medical field: if you get punched in the nose you want your nose fixed, not how not to get punched in the nose. He also applies this to global warming, which I thought was pretty insightful.
While a great scientist, Deutsch's views on other things are insightful and thought provoking. If you have the 19 minutes to spare, I recommend you check out is talk in the link above. If you have even more time I recommend you check out his book, The Fabric of Reality [3].

References
[1] D. Deutsch, "Quantum theory, the Church-Turing principle and the universal quantum computer," Proceedings of the Royal Society of London, vol. A, pp. 97-117, 1985.
[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] D. Deutsch, The Fabric of Reality, 1 ed. London: Penguin Books, 1997.