## 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.

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.

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.

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):

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):

- 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.
- 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.
- 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?
- "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.

## 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.

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

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

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.

Subscribe to:
Posts (Atom)