Quantum Programming Languages

From a pragmatical point of view QPLs are formal systems, which serve - in close analogy to classical programming languages - as a means to control the execution of programs on a quantum computer or on a classical computer simulating a quantum computer. A possible model describing this scenario is Knill's QRAM model, which is based on the idea that the program proper runs on a classical computer which controls the quantum computer, i.e. which controls a device driving a quantum experiment. From a theoretical perspective there are many additional problems which have been addressed so far. These include studies on quantum lambda calculi, on semantics of QPLs, on protocol analysis and on applications to information security. There are also ambitious attempts to set quantum theory on a new or at least an alternative formal footing using categorical concepts of computer science.

QPLs can also be classified into the traditional categories of functional and imperative/object-oriented programming languages. It has been argued that, in the context of QPLs, the functional programming paradigm appears to be advantageous for at least two reasons: first, compared to imperative languages, the type system of functional languages is more powerful so that programming errors can be detected at compile-time and second, in quantum theory, quantum operations are functions on suitable spaces: therefore, mapping these to the basic language constructs of a functional language seems to be the most natural choice.

Just as with classical programming languages there are many more aspects on QPLs which are a matter of debate. A QPL could be designed as a completely new language or as an extension of an existing classical language. The extension itself could either be embedded into the classical language or be realized in form of a library.

One of the problems which language designers face is the relatively small number of quantum algorithms which could help to demonstrate the expressiveness of their language. Another open problem is the construction of high level structures analogous to the structures, which are nowadays common in all modern programming languages such as modules, abstract data types, etc. Up to now, quantum sublanguages of QPLs are still close to assembly languages insofar as they operate directly on registers of qubits.

The following table (adopted from [4] and extended) summarizes some selected QPLs.

Language	Author(s)	imperative language	functional language	operational semantics	denotational semantics	Comments
QCL	Ömer
qGCL	Sanders/Zuliani					refinement calculus
Qlanguage	Bettelli/Calarco/Serafini					C++ and C++-based library
CHP	Aaronson/Gottesman					efficient simul. of stabilizer circuits
LanQ	Mlnarík					interprocess communication
NDQJava	Xu/Song/Qian/Dai/Zhang					Java-embedded QPL
	Sabry					Haskell as a QPL
QPL/QFC	Selinger					first order QPL
cQPL	Mauerer					extension of Selinger's QPL
QML	Altenkirch/Grattage					first order QPL, linear logic
	van Tonder					lambda calculus
	Selinger/Valiron					higher order QPL, lambda calculus
	Arrighi/Dowek					lambda calculus, linearity
QPAlg	Lalire/Jorrand					process calculus
CQP	Gay/Nagarajan					process calculus

Details, in particular references to the original articles, can be found in the survey articles [1,3-6,10,11] and in an online-bibliography on QPLs [2]. Most of the theory-oriented articles appeared in the proceedings of the International Workshops on Quantum Programming Languages QPL'04, QPL'05, and QPL'06 [7-9].

[1] S. Gay, Quantum Programming Languages. Survey and Bibliography, Math. Struct. in Comp. Science 16(4), 2006.

[2] S. Gay, Bibliography on Quantum Programming Languages

[3] R. Rüdiger, Quantenprogrammiersprachen Informatik-Spektrum 26(6),406-409(2003) also in [GI - Informatik-Lexikon] (in German)

[4] R. Rüdiger, Quantum Programming Languages: An Introductory Overview, The Computer Journal,50(2),134-150(2007), Advance Access publication on October 12, 2006

[6] P. Selinger, A brief survey of quantum programming languages., In Proceedings of Functional and Logic Programming, 7th International Symposium, FLOPS 2004, Nara, Japan, April 7-9, 2004. Vol. 2998 of LNCS, pp 1-6. Springer, 2004.

[7] P. Selinger (ed.), 2nd International Workshop on Quantum Programming Languages-QPL'04

[8] P. Selinger (ed.), 3rd International Workshop on Quantum Programming Languages-QPL'05

[9] P. Selinger (ed.), 4th International Workshop on Quantum Programming Languages-QPL'06

[10] D.A. Sofge, A Survey of Quantum Programming Languages: History, Methods, and Tools. In: Proceedings of the 2nd International Conference on Quantum, Nano, and Micro Technologies (ICQNM 2008), 66-71. IEEE Computer Society, 2008 Available at http://arxiv.org/abs/0804.1118

[11] D. Unruh, Quantum programming languages, Informatik Forsch. Entw. 21,55-63(2006)