Abstract: We propose a novel quantum programming paradigm - superposition-of-programs, motivated by the design idea of a popular class of quantum algorithms, namely quantum walk-based algorithms.

A new quantum programming language QGCL is defined to support the paradigm of superposition-of-programs. This language can be seen as a quantum extension of Dijkstra’s GCL (Guarded Command Language). Surprisingly, alternation in GCL splits into two different notions in the quantum setting: (1) classical alternation (of quantum programs) based on measurements, and (2) quantum alternation defined by external quantum "coins", with the latter being introduced in QGCL for the first time. Quantum alternation is the key program construct for realizing the paradigm of superposition-of-programs. Another very useful program construct in realizing the paradigm of superposition-of-programs, called quantum choice, can be easily defined in terms of quantum alternation. Furthermore, a kind of truly quantum recursion is introduced.

The denotational semantics of QGCL are defined by introducing a new mathematical tool called the guarded composition of operator-valued functions. In particular, the semantics of quantum recursion can be properly defined by employing mathematical tools from second quantization, including Fock space and creation and annihilation operators. 
 
We believe that quantum programming techniques in the superposition-of-programs paradigm will play an important role in further exploiting the unique power of quantum computing.
 ❘