Nottingham FP Lab Blog

(Typed) Quantum Circuits in Haskell

by Jon on October 21, 2005.
Tagged as: Lunches.

Before implementing quantum circuits it is instructive to first implement classical reversible circuits, so we can observe the differences. We look at circuits as black boxes that take in some number of wires, bit vectors, and output the same number of wires that has had the appropriate operation(s) applied. Circuits can be composed either sequentially or in parallel, and wires can be permuted. There is also a conditional operation, which takes two circuits as arguments and applies the second if the first wire is True and the first if the wire is False. Lastly, there is the one non-trivial operation on a single bit – negation.
This can all be represented in Haskell by the following data type:
>data RCirc = Wire [Int] > | Seq RCirc RCirc > | Par RCirc RCirc > | Cond RCirc RCirc > | Not
As an example, >Wire [1,0] would be a circuit that swaps the two bits/wires around, while

>Seq (Wire [1,0]) (Wire [1,0]) == Wire [0,1]

is the identity on two wires.

The only difference between classical circuits and quantum circuits are the wires. In classical circuits these can represent physical wires, but in quantum circuits the wires are a metaphore for quantum-bits (Qubits or qbits); so circuits operate on vectors of qubits in the quantum case. A qubit, like a cbit (classical bit), can be in either one of two computational basis states; usually written ${\mid}0\rangle$ and ${\mid}1\rangle$ . However, qubits can also exist in a superposition, written ${\alpha\mid}0{\rangle}+\beta{\mid}1\rangle$ , where $\alpha,\beta\in\mathbb{C}$ and $\mid\alpha\mid^2+\mid\beta\mid^2=1$ . Alpha and beta represent the complex amplitudes of the two basis states, which means a single qubit can encode an infinite amount of information. When measured (by observation), however, the superposition collapses and only either 0 or 1 is returned, with $P$({\mid}0\rangle)=\mid\alpha\mid^2$$ and $P$({\mid}1\rangle)=\mid\beta\mid^2$$ .
This one difference has only one associated effect on the data type of circuits: Not is not the only non-trivial one qubit operation. In fact there are infinitly many, as any unitary 2×2 matrix (a “rotation” of the basis) is a possible operation. So we can encode this using a new rotation circuit, which takes as an argument the rotation matrix, giving:

$%format comp = “\mathbb{C}” >data Circ = Wire [Int] > | Seq Circ Circ > | Par Circ Circ > | Cond Circ Circ > | Rot (comp,comp) (comp,comp)$

%format comp = “\mathbb{C}” >data Circ = Wire [Int] > | Seq Circ Circ > | Par Circ Circ > | Cond Circ Circ > | Rot (comp,comp) (comp,comp)

The Not operation can be recovered as:

>Rot (0,1) (1,0)

and the Hadamard operation, which is sometimes called the square-root-of-Not, can be encoded as:

$%format hh = “$1/\sqrt{2}$” >Rot (h,h) (h,-h) where h = hh$
These rotations translate into the following matricies:

> [0, 1 ; and [h, h ; > [1, 0 ] [h, -h ]

In order to define a typed circuit, the types must first be defined. These are defined as:

$%format `ten` = “\ensuremath{\otimes}” > data Ty = T1 | T2 | Ty `ten` Ty$

%format `ten` = “\ensuremath{\otimes}” > data Ty = T1 | T2 | Ty `ten` Ty

Where >T2 is the type of a single qubit, and $\otimes$ (tensor) allows groups of “wires” to be constructed (wires in parallel). >T1 is the unit of $\otimes$ . A context for a circuit is simply a Snoc list of types:

> data TCon = Snoc Ty .

The Haskell representation of typed circuits can now be written as:

> data TCirc = TCirc { inTy, outTy ::TCon, hpS, > gbS :: Int, > circ :: Circ}

inTy and outTy contain the useful input and output type contexts to the circuit. hpS contains the number of heap qubits required (heap size), and likewise gbS contains the number of measured (garbage) output qubits. This in fact gives us a typed object in the category FQC, for use with the QML compiler.