Interview with Peter Shor

Here's an interview from Dr. Dobb's with Jack Woehr interviewing Peter Shor- as in Shor's algorithm for factoring. Most discussions on quantum computing focus on the physical implementations, or perhaps algorithms. It was refreshing to see a mention of actually programming quantum computers too:

JW: I've seen quantum computer machine language simulators on the web. What would an implementation of Shor's Algorithm in a high-level quantum computing language look like?

PS: Good question. Certainly I can imagine a Fortran-style high-level language that would make Shor's Algorithm easier, but really, you'd want something more high-level than that.

That being said, I don't think the best approach will be a quantum computing language. Too much computation is classical, even when a quantum computer is used. As an example, a quantum computer is used just for a single step of Shor's algorithm- the rest is classical. Preferable to a quantum computing language I think would be a framework that extends classical languages to allow for quantum computation. There are many benefits, but I see the big two as being:

1. The framework designer can focus on tackling quantum computation. They don't have to try to include classical techniques that we've spent decades refining.
2. There is a large user base for the popular classical languages. By creating a framework there is less of a hurdle for those programmers to perform quantum computation. Furthermore it will integrate much better with existing code bases.

Of course, I developed Cove as a framework for quantum computation exactly because of the reasons above.

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.

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.