λ-Q#: Understanding and Evolving the Q# Programming Language
Three months after I started my PhD focusing on programming languages (PL) for quantum computing, Microsoft announced the Q# programming language; precisely 5 years ago, as of the day I write this. I did not know much about the landscape of quantum programming languages at the time, but I was in awe after playing with the language for a bit. Some of it was the adoption of proven features from classical languages, such as immutability-by-default (reminiscent to me of Rust), and some was the functional nature of the language (which the PL community admires). When I learned about the Q# paper later in March, I was eager enough to read it the same day. I enthusiastically wrote to my advisor, noting the beauty of this quantum language designed in the industry.
Fast-forwarding by two or so years, I was interning at Microsoft Quantum on an unrelated project. Q# was still at the back of my mind, so while there, I tried to understand the history and pain points of the language by talking with the designers. This led me to propose a longer-term project for defining formal semantics for Q# and solving some of the problems I learned about. This project is far from complete, but I wanted to share some progress with you.
Formally Specifying Programming Languages
What does it mean to formally define a language, and why do we want to do it? While many programming languages come with informal specifications, they are written in natural languages (like English), often leaving subtle technical concepts for interpretation (leading to the infamous undefined behavior). A formal specification uses mathematical notation to avoid ambiguity in the meaning of the language and hence aids in understanding and allows precise implementation. This makes it easier to evaluate how new features may interact with existing ones, helping with the evolution of the language.
At a high level, a formal specification consists of the following:
- A surface (concrete) syntax and its grammar.
- An abstract syntax for types and program terms.
- Static semantics that describes the type system, which rules out meaningless programs and catches bugs in programs before they get executed.
- Dynamic semantics that describes the behavior of programs at a high abstraction level.
Designing a new language with a formal specification is much easier than endowing an existing language with one. The design decisions aimed at user convenience can typically be at odds with the needs of a researcher studying the language. Since Q# already exists, we borrowed the methodology pioneered in the specification of the Standard ML programming language:
- Define a well-behaved core language that describes the essence of Q# — λQ#.
- Elaborate from the surface Q# language to the core.
- Specify the static and dynamic semantics using this core.
- Optionally, study the consequences of extensions or variations of the language.
λQ#: An idealized core language for Q#
λQ# is a simply typed λ-calculus extended with commands encapsulating actions on the quantum state. In λQ#, we may encode any Q# program as a pure functional term, analogous to how a language like Haskell treats side effects (we also borrow the do notation from Haskell). The Algol programming language pioneered the idea of safely combining pure functional programming with side-effectful imperative programming.
Quantum teleportation in λQ# syntax
The syntax, the type system, and the safety properties of λQ# (enforcing the no-cloning theorem and safe qubit memory management; that the Q# compiler currently does not enforce) have been discussed in various presentations. I take this opportunity to instead emphasize how the dynamic semantics of the language is defined in an accessible manner using a small set of program equations.
In the following equations, the terms on the left of the turnstile (⊢) show the types of variables used in the equations. qref⟨q⟩ represents the type of qubit; × represents the product type; ≡ is the symbol for equivalence; ⟨⟩ represents unit; and D(U, V) = U ⊕ V represents a block diagonal matrix corresponding to controlled unitaries.
Equation (A) says that applying the quantum X gate to a qubit and then measuring it is the same as negating the measurement result. Equation (B) explains the action of a block diagonal matrix D(U, V) as quantum control: Applying the diagonal matrix and then measuring the control qubit is equivalent to measuring the control qubit and branching on the result to decide whether to apply U or V.
Equation (D) states that measuring a new qubit always results in 0 (false in our language). Equation (E) says that using a new qubit as control is the same as controlling by 0.
These four are the most interesting equations; I omit the other seven administrative equations. This presentation of semantics is known as algebraic or equational semantics. The key idea is to capture the entire behavior of a language using a complete set of equations. For quantum computation, this fully complete set (that we adapt for λQ#) was first introduced by Sam Staton in a 2015 paper. The beauty of this presentation style is two-fold: it is both broadly accessible as almost everyone is familiar with equations from school-level mathematics, and it is concise while still being formal.
I hope this post helps you understand our approach to formally specifying Q# using program equations. For full details, see our paper Q# as a Quantum Algorithmic Language (arXiv:2206.03532) presented at the Quantum Physics and Logic conference earlier this year. In the paper, my coauthors (Kesha Hietala, Sarah Marshall, Robert Rand) and I argue that λQ# represents the core of Q# as an Algol-like quantum language. It safely combines pure (classical) and effectful (quantum) computation while obeying a strict stack discipline for (qubit) memory management. We also provide translation rules from Q# to λQ#.
λQ# is an idealized version of Q# aimed at providing it a formal language definition, placing the language on a solid mathematical foundation, and enabling further evolution of its design and type system. I am currently working on preventing aliasing in Q# arrays and coverage of remaining features in λQ#; look out for my upcoming dissertation!
- Available as part of the Q# Language Spec. ↩︎
- Documented well in §6–7 of The History of Standard ML (2020). ↩︎
- Our paper’s title pays homage to Algol; λQ# could be called QAlgol. ↩︎
- See slides and video of my talk at QPL ’22 and a longer invited talk. ↩︎