Quantum data and control made easier. (English) Zbl 1279.68035

Selinger, Peter (ed.), Proceedings of the 4th international workshop on quantum programming languages (QPL 2006), Oxford, UK, 17–19 July 2006. Amsterdam: Elsevier. Electronic Notes in Theoretical Computer Science 210, 85-105 (2008).
Summary: We define nQML, a functional quantum programming language that follows the “quantum data and control” paradigm. In comparison to Altenkirch and Grattage’s QML, the control constructs of nQML are simpler and can implement quantum algorithms more directly and naturally. We avoid the unnecessary complexities of a linear type system by using types that carry the address of qubits in the quantum state. We provide a denotational semantics over density matrices and unitary transformations, inspired by Selinger’s semantics for QPL. Our semantics leads naturally to an interpreter for nQML, written in Haskell. We also explore the extension of nQML with polymorphic higher-order functions.
For the entire collection see [Zbl 1276.68031].


68N15 Theory of programming languages
68N18 Functional programming and lambda calculus
81P10 Logical foundations of quantum mechanics; quantum logic (quantum-theoretic aspects)
81P68 Quantum computation


QPL; Haskell; nQML; qGCL
Full Text: DOI


[1] Altenkirch, T. and J. Grattage, A functional quantum programming language, in: Proceedings of the 20th Annual IEEE Symposium on Logic in Computer Science, 2005, pp. 249-258
[2] Gay, S.J., Quantum programming languages: survey and bibliography, Mathematical structures in computer science, 16, 581-600, (2006) · Zbl 1122.68021
[3] Grattage, J. and T. Altenkirch, A compiler for a functional quantum programming language (2005), manuscript
[4] Grattage, J. and T. Altenkirch, QML: Quantum data and control (2005), manuscript
[5] Grover, L.K., A fast quantum mechanical algorithm for database search, in: Proceedings of the 28th Annual ACM Symposium on the Theory of Computing, Philadelphia, PA, 1996, pp. 212-219 · Zbl 0922.68044
[6] Knill, E., Conventions for quantum pseudocode, Technical Report LAUR-96-2724, Los Alamos National Laboratory (1996)
[7] Ömer, B., “Structured Quantum Programming,” Ph.D. thesis, Institute of Information Systems, Technical University of Vienna (2003)
[8] Sanders, J.W.; Zuliani, P., Quantum programming, (), 80-99 · Zbl 0963.68037
[9] Selinger, P., Towards a quantum programming language, Mathematical structures in computer science, 14, 527-586, (2004) · Zbl 1085.68014
[10] Selinger, P.; Valiron, B., A lambda calculus for quantum computation with classical control, Mathematical structures in computer science, 16, 527-552, (2006) · Zbl 1122.68033
[11] Shor, P.W., Polynomial time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM journal on computing, 26, 1484-1509, (1997) · Zbl 1005.11065
[12] van Tonder, A., A lambda calculus for quantum computation, SIAM journal on computing, 33, 1109-1135, (2004) · Zbl 1057.81016
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.