Q# Programming Language

This post summarizes the features of Microsoft’s Q# Language Specification. It is derived from §2.1 of my thesis proposal. I also created a PDF version of the Q# language specification.


Overview

Q# is a standalone domain-specific programming language from Microsoft for writing and running quantum programs. It lets one seamlessly combine classical and quantum computation while providing a separation between pure classical functions and effectful quantum operations, collectively known as callables. The programming model assumes a high level of abstraction with no notion of quantum circuits or quantum states.

Q# organizes programs using namespaces that contain open directives, declaration of callables, and type declarations for user-defined types. Namespaces are not hierarchical, however; i.e., there is no relation between two namespaces even if they have a common prefix.

User-defined types declared using newtype are essentially records. Callables, as mentioned earlier, include functions and operations. Operations may carry operation characteristics, Adj and Ctl, to declare support for functorsAdjoint and Controlled —to enable metaprogramming. They may also include additional specializations for their adjoint and controlled variants, but the reference implementation does not check these specializations for correctness. The default specification is the body of the operation.

Instead of providing a custom specialization, the user can also ask the compiler to auto-generate a specialization using directives such as self, invert, and distribute. Auto-generation is not possible in all cases, such as when mutable variables are involved. If the programmer provides no specialization or generation directive, the directive auto applies by default. For example, the following operations are equivalent:

operation Trivial() : Unit
    is Adj + Ctl { }

operation Trivial() : Unit {
    body (...) { } // dots indicate same arguments as declaration
    adjoint auto;
    controlled auto;
    controlled adjoint auto;
}

Q# supports single-line comments that start with double forward slash characters (//). There is also support for documentation comments that start with triple slashes (///), which may include headers such as Description, Input, Output, Type Parameters, Example, among others.

Statements

Statements familiar from classical programming include return, fail, let & mutable for variable declaration, set for rebinding mutable variables, an iterator-based for loop, a conditional while loop, and a branching if-elif-else conditional. Quantum-specific statements include use & borrow for qubit allocation, a repeat-until-fixup loop for expressing the repeat-until-success pattern, and a within-apply statement for expressing the (automatic) uncomputation pattern. Statements also include calls to any callable returning Unit.

Note that any classical statements may appear in operations but not vice versa for quantum-specific statements and functions—a consequence of this restriction is that functions can never call operations. Further, the while loop is currently not supported inside an operation.

The use statement provides access to freshly allocated qubits corresponding to state |0⟩, while the borrow statement allows access to previously allocated (and potentially entangled) qubits. Q# assumes that a program always starts with no qubits, operations allocate qubits as needed, and they get automatically deallocated at the end of lexical scope, i.e., the lifetime of a qubit variable is equal to its lexical scope.

Expressions

Q# expressions are values (literals) and identifiers. They can be combined using operators, modifiers, and combinators. Since all compound data types in Q# are immutable, it includes a notion of a copy-and-update operator (w/ <-) apart from several familiar operators such as a ternary conditional (? |), logical, comparison, bitwise, and arithmetic operators. There is also a concatenation operator (+) for Strings and arrays.

Modifiers include the Adjoint and Controlled functor applications and the unwrap modifier (!) that deconstructs a user-defined type (UDT). Combinators include call (()), named item access (::) for UDTs, and array item access ([]).

Literals include values for most data types: Unit (()), Int, BigInt, Double, Bool (true and false), String, Result (Zero and One), Pauli (PauliI, PauliX, PauliY, and PauliZ), Range, arrays, and tuples. Qubit type is opaque and has no literal.

For functions and operations, there is support for creating closures using lambda expressions (-> and =>, respectively) and partial applications.

Type System

Q# currently features a fairly simple type system. Apart from the primitive data types listed in the preceding section, there is support for compound data types such as arrays, tuples, user-defined types, and callables. Callables are first-class values, and hence, Q# supports higher-order programming. The type of an operation follows the schema <TIn> => <TOut> is <Char> where Char, the operation characteristics (Adj, Ctl, or both), may be omitted if unneeded. Similarly, the type schema of a function is <TIn> -> <TOut>. Further, callables allow type parameterization to support generic programming.

There is limited support for subtyping. Specifically, an operation that supports more functors (declared using the operation’s characteristics) than needed at the call site may be substituted. Callables require explicit type declarations, but most types in callable bodies are inferable by Q#’s Hindley-Milner-style type inference algorithm.

Remarks

In essence, a Q# program describes quantum computation at a high abstraction level without adherence to the circuit model. With choices such as immutability by default and a clean separation between operations that perform (quantum) side effects and functions that perform pure classical computation, Q# represents a safe synthesis of functional and imperative programming styles in the design space of programming languages for quantum computation. This synthesis is reminiscent of Algol-like languages in the classical PL literature. However, there are limitations. Q# allows uncontrolled aliasing of qubits that, like in classical programming languages, can lead to unsafe computation. Even though the quantum memory model in Q# is to allocate and deallocate qubits in a stack-like manner, the compiler does not enforce this stack discipline. See our paper Q# as a Quantum Algorithmic Language (QAlgol) for early solutions toward these problems.