Towards a Quantum Programming Language

Paper information (2004, Mathematical Structures in Computer Science) — Peter Selinger. DOI; author page

Work

The paper proposes QPL (Quantum Programming Language), moving quantum programs above the circuit or quantum-Turing-machine level to a language with structured data, loops, and recursive procedures. It separates quantum data from classical control and uses typing rules to constrain program construction. Its denotational semantics interprets commands as superoperators on density operators, connecting program composition with quantum transformations.

Contributions

• A language design with quantum data types, classical control, loops, recursive procedures, and structured data.
• A static typing discipline aimed at making well-formed programs free of run-time type errors.
• A denotational account based on superoperators, including a treatment of recursion and partial computation.

Limits

QPL is a language and semantics result, rather than a compiler or complete toolchain for a particular hardware target. Its model is primarily idealized and finite-dimensional; noise, gate sets, device connectivity, compilation cost, and runtime engineering require additional models. Type safety alone does not prove an algorithm's postcondition, numerical accuracy, or hardware behavior.

Connections

The paper develops the program-description and semantics questions raised by Conventions for Quantum Pseudocode and Quantum Programming into a language design. van Tonder's quantum lambda calculus offers a functional and linear-calculus route, while Abramsky and Coecke's categorical semantics describes protocols through more abstract compositional structure. QPL emphasizes writable language constructs and superoperator semantics.

Original paper

Peter Selinger, Towards a Quantum Programming Language, Mathematical Structures in Computer Science 14(4), 527–586 (2004), DOI: 10.1017/S0960129504004256. Author page