This week I’m taking a break from my regular Haskell posts. A few weeks ago I posted about High Level Quantum Assembly using Haskell and that got me thinking about what a high level quantum computing language might look like. This week I’m going to attempt to perform a thought experiment and imagine what a hypothetical high-level quantum computing language might look like using some very basic category theory and type theory.

# Properties of quantum gates

I’m going to massively simplify quantum computing, because I don’t really understand the physics behind it. Basic low-level quantum computing involves two components, qubits and quantum gates which act on them.

There are plenty of interesting articles on quantum gates including Demystifying Quantum Gates — One Qubit At A Time by Jason Roell, Quantum Gates and Circuits: The Crash Course by Anita Ramanan, and this excellent introductory talk Quantum Computing for Computer Scientists by Andrew Helwer. I’m not going to discuss low-level quantum gates in detail; in fact that would be counter-productive because in order to create a high-level quantum computing language, we need to be able to forget about the details of how qubits work. What we want is to generalize the objects of quantum computing so that we don’t need to worry about these details any more.

Before we start generalizing, let’s examine the qualities of qubits and gates.

Qubits are represented by vectors with two components. The two components represent two orthogonal dimensions in some Hilbert space represented in Dirac notation as |0_{k}> and |1_{k}>, where k represents the index of the qubit in a system of multiple qubits. The multiple qubits’ vectors are stacked on one another to produce a **single vector** with 2k elements. In addition, when you have a system containing multiple entangled qubits, you are operating on the **tensor product** of all of the qubits in the system. The tensor product of k entangled qubits with one-another produces a **vector** which contains 2^{k} elements.

For example:

[a, b] ⊗ [c, d] = [a * c, a * d, b * c, b * d] [a, b] ⊗ [c, d] ⊗ [e, f] = [a * c, a * d, b * c, b * d] ⊗ [e, f] = [a * c * e, a * d * e, b * c * e, b * d * e, a * c * f, a * d * f, b * c * f, b * d * f]

Note that the state of any qubit system is ultimately represented as a **vector**.

When a qubit in a qubit set is measured, its superposition is “collapsed”, which forces it to assume a value of |0> or |1>. The likelihood of the qubit assuming a |0> or |1> value is based on the value of the qubit’s vector before the measurement. Again, I’m not sure exactly what this means physically, but I do understand that this operation is **non-reversible**, which distinguishes it from other operations on qubits.

Quantum gates act on qubits, performing operations which can change the phase of a single qubit or multiple qubits. I have no clue how this happens physically, but the effect of this operation on a qubit can be entirely captured by a unitary matrix. For example, the SWAP operation has the following matrix:

[1, 0, 0, 0 0, 0, 1, 0 0, 1, 0, 0 0, 0, 0, 1]

Since this is how quantum gates operate, we can model quantum systems as **matrix multiplications** applied to **vectors**. Specifically, “A gate which acts on k qubits is represented by a 2^{k} x 2^{k} unitary matrix.” [Wikipedia]

# A quantum category

Since quantum gates are equivalent to matrix multiplications on qubit state vectors, we can rely on the properties of matrix multiplication to create an abstraction.

Given two matrices, M and N, which are applied to a vector v in sequence, NMv, there exists a matrix NM which produces an identical result. The matrix NM is called the composition of M and N. Since the effect of quantum gates can be modeled by a unitary matrix, then equivalently, for every two quantum gates M and N, there exists a gate NM, which is the composition of M and N. In other words, quantum gates are **composable**.

Furthermore, since matrix multiplication is associative, quantum gate applications are **associative**. Therefore, for quantum gates M, N, and O and a qubit state vector v, O(NM)v == (ON)Mv. (Please let me know if this is not the case, I haven’t seen anything in my brief literature review which contradicts this statement).

In addition, for every vector v, there is an identity matrix I, such that Iv == v. Equivalently, there is a quantum **identity** gate; if you don’t apply a gate, you get the same qubit state vector you started with.

Since quantum gates are composable, associative, and have an identity, quantum gates form a category! Since we have a category, we can use category theory to describe a model for abstract quantum operations! Let’s specialize this category with types, to create a type theoretic model for quantum operations. We’ll start by creating a category called *Quantum* with two type constructors, *Measured Bool* and *Super Bool*, which represent the value of a qubit in its measured state and its superposition state.

data Quantum = Measured Bool | Super Bool

Now we can define operations on the value of a qubit which go from a measured qubit to a superposition qubit. For example, we could apply a Hadamard gate to *Measured Bool* to create a *Super Bool*:

We could also apply a Hadamard gate to a *Super Bool* to produce another *Super Bool*:

Here’s the type of the Hadamard function:

hadamard :: Quantum Bool -> Quantum Bool

In fact, we can apply all quantum gates to Measured Bool or Super Bool, with the requirement that the codomain of the gate functions must be the Super Bool type.

We can apply the constraint that all operations on the *Quantum* meta-type must be reversible, so that we preserve the quantum properties of the system. There is one exception to this constraint, the measure function:

This breaks our rule. How can we make everything consistent? The answer is that since *Measured Bool* is really just the classical type *Bool,* we can move it out of the *Quantum* metatype:

Now every function in *Quantum* can be reversible! We change our definition of *Quantum* like this:

data Quantum = Super Bool

There’s no real reason to restrict ourselves to the *Bool* type. It’s possible to represent other types such as *Bitset* and *Int* with classical types, so we can imagine representing a *Bitset* or an *Int* as a collection of qubits. A *Super Int* could simply be a superposition of all possible *Int* values. What would we need a *Super Int* for? I have no clue; but it’s technically possible to have one, so why not?

In fact we can represent all classical pure types using qubits, so let’s generalize the diagram above with the set of all pure types, *T*. Let’s rename the *Super* value constructor to *Quantum* too:

data Quantum a = Quantum a

We need to define a *measure* function for all types in *Quantum T*, but that detail is left as an exercise for the reader.

This simplifies our definition of *Quantum* functions; all functions in the *Quantum* category are now reversible.

For example, *hadamard* still has the same type:

hadamard :: Quantum Bool -> Quantum Bool

but now we only need one version of H, rather than two:

# A quantum Applicative Functor

There’s one problem with our *Quantum* category; we can no longer move any classical data into it! Let’s fix that by making an *Applicative Functor* for our category.

To start with, let’s make *Quantum* an instance of *Functor*:

instance Functor (Quantum a) where fmap f (Quantum a) = Quantum (f (measure a))

Now we can take any classical function, *f*, and apply it to any *Quantum* data *a*, by measuring it first. Note that by definition *fmap* **must involve a measurement** of the superposition, collapsing the superposition. For example, if we wanted to apply the classical *not* function to the result of calling *hadamard* on a *Quantum Bool*, we could do the following:

hadamardNot :: Quantum Bool -> Quantum Bool hadamardNot x = fmap not (hadamard x)

Suppose we have a list of *Quantum Bool*, and we want to *hadamardNot* each of the elements, we can now use regular Haskell to do this:

hadamardNotList :: [Quantum Bool] -> [Quantum Bool] hadamardNotList x = fmap hadamardNot x

Next, let’s make *Quantum* an instance of *Applicative*:

instance Applicative (Quantum a) where pure x = Quantum x (Quantum f) <*> (Quantum x) = Quantum (f (measure x))

Note that apply (<*>) by definition **must also involve a measurement** of the superposition, collapsing the superposition.

Now we can use *pure* to take classical data or functions from *T* into *Quantum T*:

For example, we could move a *Bool* into *Quantum*, call *hadamard* on it, and apply a classical *not* function to it like this:

let qnot = (Quantum not) in qnot <*> (hadamard (pure True))

This would have the effect of moving the *True* value into a quantum register, applying the H gate, measuring the result and taking the *not* of that result. A useless operation, but I’m sure more useful computations exist.

Note that it’s still possible to make functions which reside entirely in the Quantum category, so we could define a function *bell*:

bell :: (Quantum Bool, Quantum Bool) -> (Quantum Bool, Quantum Bool) bell (x, y) = cnot (hadamard x) y

Functions in *Quantum* which don’t involve *fmap*, *pure*, *<*>*, or *measure* are reversible.

At this point, it’s pretty easy to imagine compound quantum data types, for example a binary tree of qubits could be defined like this:

data QubitTree = Leaf | Node (Quantum Bool) QubitTree QubitTree

You could imagine other kinds of data structures, for example a graph G = (V, E), where V is a set of vertices, each of which contains a qubit, and E, the set of edges, represent entangled qubit pairs. Each qubit would be entangled with all of its neighbors on the graph.

Or you could move a compound data structure into the *Quantum Applicative Functor *like this:

makeQuantumList :: [a] -> Quantum [a] makeQuantumList x = pure x

# A quantum Monad

The next obvious step is to make *Quantum* an instance of *Monad*, which is quite simple:

instance Monad (Quantum a) where return x = Quantum x x >>= f = f (measure x)

So we can chain functions which generate a *Quantum* value from a classical value using bind. Again, by definition, a bind (>>=) **must also involve a measurement** of the superposition, collapsing the superposition. I don’t even have an example of a function which might take a classical value and evaluate to a superposition, so I’m just going to pretend that there are two of them called foo and bar:

foo :: String -> Quantum Int bar :: Int -> Quantum Float

We could chain these operations one after another using bind:

return "Quantum" >>= foo >>= bar

This is an extremely useless operation, but maybe someone will figure out how to make the *Quantum Monad* useful.

Again, it’s important to note that functions in *Quantum* which don’t involve *return* and *bind* are reversible.

There is a possible extension of the *Quantum* category where you can preserve the reversibility of operations even in the presence of *measure*, *fmap*, *apply*, *pure*, *bind* and *return*, by introducing another typeclass *Measured*. The *measure*, *fmap*, *apply*, *pure*, *bind* and *return* operations would take a *Quantum* value to a *Measured* value, but that complicates things significantly, so I don’t really want to go into detail about it.

# Strongly-typed quantum computing?

It looks like I just ended up adding quantum computations to Haskell without actually inventing a new language after all. This was an interesting thought experiment, but I’m still not sure if it’s useful. At least it’s a fun way to spend a weekend!

**P.S. Please cite this article if you build upon the ideas described here.**