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:
As an example, would be a circuit that swaps the two bits/wires around, while
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 and . However, qubits can also exist in a superposition, written , where and . 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 and .
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:
The Not operation can be recovered as:
and the Hadamard operation, which is sometimes called the square-root-of-Not, can be encoded as:
These rotations translate into the following matricies:
In order to define a typed circuit, the types must first be defined. These are defined as:
Where is the type of a single qubit, and (tensor) allows groups of “wires” to be constructed (wires in parallel). is the unit of . A context for a circuit is simply a Snoc list of types:
The Haskell representation of typed circuits can now be written as:
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.