Alexander S. Green
Benoît Valiron
ABSTRACT
The field of quantum algorithms is vibrant. Still, there is currently a lack of programming languages for describing quantum computation on a practical scale, i.e., not just at the level of toy problems. We address this issue by introducing Quipper, a scalable, expressive, functional, higher-order quantum programming language. Quipper has been used to program a diverse set of non-trivial quantum algorithms, and can generate quantum gate representations using trillions of gates. It is geared towards a model of computation that uses a classical computer to control a quantum device, but is not dependent on any particular model of quantum hardware. Quipper has proven effective and easy to use, and opens the door towards using formal methods to analyze quantum algorithms.
Supplemental Material
Available for Download
This README file contains information relating to the files in the auxilliary material file: The files in this archive are all the source files used by TeX when creating the paper from source. Including the original versions of any graphics.
- T. Altenkirch and A. S. Green. The Quantum IO Monad. In S. Gay and I. Mackie, editors, Semantic Techniques in Quantum Computation, pages 173--205. Cambridge University Press, 2009.Google Scholar
Cross Ref
- A. Ambainis, A. M. Childs, B. Reichardt, R.v Spalek, and S. Zhang. Any AND-OR formula of size n can be evaluated in time n 1/2+o(1) on a quantum computer. SIAM J. Comput., 39:2513--2530, 2010. Google ScholarDigital Library
- A. Childs and R. Kothari. Quantum query complexity of minor-closed graph properties. In Proceedings of the 28th Symposium on Theoretical Aspects of Computer Science, pages 661--672, 2011.Google Scholar
- A. M. Childs, R. Cleve, E. Deotto, E. Farhi, S. Gutmann, and D. A. Spielman. Exponential algorithmic speedup by a quantum walk. In Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing, pages 59--68, 2003. Google ScholarDigital Library
- K. Claessen. Embedded Languages for Describing and Verifying Hardware. PhD thesis, Chalmers University of Technology and Göteborg University, 2001.Google Scholar
- D. Deutsch. Quantum theory, the Church-Turing principle and the universal quantum computer. Proceedings of the Royal Society of London, Series A, 400(1818):97--117, 1985.Google ScholarCross Ref
- S. J. Gay. Quantum programming languages: Survey and bibliography. Mathematical Structures in Computer Science, 16(04):581--600, 2006. Google ScholarDigital Library
- S. Hallgren. Polynomial-time quantum algorithms for Pell's equation and the principal ideal problem. J. ACM, 54(1):4:1--4:19, Mar. 2007. Google ScholarDigital Library
- A. W. Harrow, A. Hassidim, and S. Lloyd. Quantum algorithm for linear systems of equations. Phys. Rev. Lett., 103(15):150502, 2009.Google ScholarCross Ref
- IARPA Quantum Computer Science Program. Broad Agency Announcement IARPA-BAA-10-02. Available from https://www.fbo.gov/notices/637e87ac1274d030ce2ab69339ccf93c, April 2010.Google Scholar
- S. Jordan. http://math.nist.gov/quantum/zoo/. Electronic resource.Google Scholar
- E. H. Knill. Conventions for quantum pseudocode. LANL report LAUR-96--2724, 1996.Google Scholar
- F. Magniez, M. Santha, and M. Szegedy. Quantum algorithms for the triangle problem. quant-ph/0310134, 2003. Google ScholarDigital Library
- F. Magniez, M. Santha, and M. Szegedy. Quantum algorithms for the triangle problem. In Proceedings of the 16th annual ACM-SIAM symposium on Discrete algorithms, pages 1109--1117, 2005. Google ScholarDigital Library
- M. A. Nielsen and I. L. Chuang. Quantum Computation and Quantum Information. Cambridge University Press, 2002. Google ScholarDigital Library
- B. Ömer. Quantum programming in QCL. Master's thesis, Institute of Information Systems, Technical University of Vienna, 2000.Google Scholar
- O. Regev. Quantum computation and lattice problems. SIAM J. Comput., 33(3):738--760, 2004. Google ScholarDigital Library
- P. Selinger and B. Valiron. A lambda calculus for quantum computation with classical control. Mathematical Structures in Computer Science, 16(3):527--552, 2006. Google ScholarDigital Library
- P. Selinger and B. Valiron. Quantum lambda calculus. In S. Gay and I. Mackie, editors, Semantic Techniques in Quantum Computation, pages 135--172. Cambridge University Press, 2009.Google ScholarCross Ref
- T. Sheard and S. Peyton Jones. Template metaprogramming for Haskell. In Proc. Haskell Workshop, 2002. Google ScholarDigital Library
- P. Shor. Algorithms for quantum computation: discrete logarithms and factoring. In Proceedings, 35th Annual Symposium on Foundations of Computer Science. CA: IEEE Press, 1994. Google ScholarDigital Library
- A. van Tonder. A lambda calculus for quantum computation. SIAM Journal of Computing, 33(5):1109--1135, 2004. Google ScholarDigital Library
- J. D. Whitfield, J. Biamonte, and A. Aspuru-Guzik. Simulation of electronic structure Hamiltonians using quantum computers. Molecular Physics, 109(5):735--750, 2011.Google ScholarCross Ref
Index Terms
- Quipper: a scalable quantum programming language
Recommendations
QWIRE: a core language for quantum circuits
POPL '17This paper introduces QWIRE (``choir''), a language for defining quantum circuits and an interface for manipulating them inside of an arbitrary classical host language. QWIRE is minimal---it contains only a few primitives---and sound with respect to ...
Quipper: a scalable quantum programming language
PLDI '13The field of quantum algorithms is vibrant. Still, there is currently a lack of programming languages for describing quantum computation on a practical scale, i.e., not just at the level of toy problems. We address this issue by introducing Quipper, a ...
An introduction to quantum programming in quipper
RC'13: Proceedings of the 5th international conference on Reversible ComputationQuipper is a recently developed programming language for expressing quantum computations. This paper gives a brief tutorial introduction to the language, through a demonstration of how to make use of some of its key features. We illustrate many of ...
Comments