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.
No comments:
Post a Comment