A thought experiment: Category Theory and Quantum Computing

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.