How should qubits be represented in a quantum programming language?

In the quantum circuit model, a quantum computation is represented as a sequence of operations, sometimes known as gates, applied to a set of qubits. This leads to pictures such as:

In this picture, each horizontal line is a qubit, each box is an operation, and time flows from left to right.

When we want to design a programming language to express a quantum computation, the question naturally arises of whether qubits should be represented in the language, and if so, how. In the most naïve model of such a picture, there would be a software entity that represented each horizontal line, with little or no accessible state other than perhaps a label, but there are other possibilities.

Quantum States as Linear Types

Quipper uses linear types to model quantum states, although it refers to the data type as Qubit. The intuition is that the no-cloning theorem prevents you from making a copy of the quantum state of a qubit, so it makes sense to use the type system to prevent you from making a copy of the software representation of quantum state. Linear types have proven useful in other contexts where copying the software representation of an entity would be bad, for instance in functional concurrent programming, so why not for quantum computing?

The argument for linear types is, as mentioned, that they reflect the no-cloning theorem in the language. The implication is that a software qubit represents a qubit state, rather than an actual object. The problem with this view is that, once entangled, it no longer makes sense to talk about the state of an individual qubit; that’s more or less exactly what being entangled means. To model this in software, an entangling gate such as a CNOT should take two single-qubit states as inputs and return a software entity that represents two-qubit state as output — as long as you never want to perform a CNOT on two qubits that are each entangled with other qubits.

The software entity as quantum state abstraction breaks down for two reasons:

• because quantum computing works by applying operations to physical entities, not to quantum states, so the abstraction doesn’t correspond to operational reality; and
• because in general there is no actual physical quantum state smaller than the state of the entire quantum computer, so the abstraction doesn’t correspond to physical reality.

Qubits as Opaque References

An alternate approach is to use an opaque data type that represents a reference to a specific two-state quantum system, whether physical or logical (error-corrected), on which operations such as H or X may be performed. This is an operational view of qubits: qubits are defined by what you can do to them. Both OpenQASM and Q# follow this model.

Quantum Computing is Computing by Side Effect

The representation used in Q# has the interesting implication that all of the actual quantum computing is done by side effect. There is no way to directly interact with the quantum state of the computer; it has no software representation at all. Instead, one performs operations on qubit entities that have the side effect of modifying the quantum state. Effectively, the quantum state of the computer is an opaque global variable that is inaccessible except through a small set of accessor primitives (measurements) — and even these accessors have side effects on the quantum state, and so are really “mutators with results” rather than true accessors.

In general programming, the use of side effects and global state is generally discouraged. For quantum computing, on the other hand, they seem to match the actual physical reality pretty well. For this reason, we decided that this abstraction was the right one to use in Q#.

This post is the first one in the Q# Advent Calendar 2018. Follow the calendar for other great posts!