This module provides functions for defining general-purpose transformations on low-level circuits. The uses of this include:

• gate transformations, where a whole circuit is transformed by replacing each kind of gate with another gate or circuit;
• error correcting codes, where a whole circuit is transformed replacing each qubit by some fixed number of qubits, and each gate by a circuit; and
• simulations, where a whole circuit is mapped to a semantic function by specifying a semantic function for each gate.

The interface is designed to allow the programmer to specify new transformers easily. To define a specific transformation, the programmer has to specify only four pieces of information:

• A type a=⟦Qubit⟧, to serve as a semantic domain for qubits.
• A type b=⟦Bit⟧, to serve as a semantic domain for bits.
• A monad m. This is to allow translations to have side effects if desired; one can use the identity monad otherwise.
• For every gate G, a corresponding semantic function ⟦G⟧. The type of this function depends on what kind of gate G is. For example:

If G :: Qubit -> Circ Qubit, then ⟦G⟧ :: a -> m a. 
If G :: (Qubit, Bit) -> Circ (Bit, Bit), then ⟦G⟧ :: (a, b) -> m (b, b).

The programmer provides this information by defining a function of type Transformer m a b. See #Transformers below. Once a particular transformer has been defined, it can then be applied to entire circuits. For example, for a circuit with 1 inputs and 2 outputs:

If C :: Qubit -> (Bit, Qubit), then ⟦C⟧ :: a -> m (b, a).

The following is a short but complete example of how to write and use a simple transformer. As usual, we start by importing Quipper:

import Quipper

We will write a transformer called sample_transformer, which maps every swap gate to a sequence of three controlled-not gates, and leaves all other gates unchanged. For convenience, Quipper pre-defines an identity_transformer, which can be used as a catch-all clause to take care of all the gates that don't need to be rewritten.

mytransformer :: Transformer Circ Qubit Bit
mytransformer (T_QGate "swap" 2 0 _ ncf f) = f $
  \[q0, q1] [] ctrls -> do
    without_controls_if ncf $ do
      with_controls ctrls $ do
        qnot_at q0 `controlled` q1
        qnot_at q1 `controlled` q0
        qnot_at q0 `controlled` q1
        return ([q0, q1], [], ctrls)
mytransformer g = identity_transformer g

Note how Quipper syntax has been used to define the replacement circuit, consisting of three controlled-not gates. Also, since the original swap gate may have been controlled, we have added the additional controls with a with_controls operator.

To try this out, we define some random circuit using swap gates:

mycirc a b c d = do
  swap_at a b
  hadamard_at b
  swap_at b c `controlled` [a, d]
  hadamard_at c
  swap_at c d

To apply the transformer to this circuit, we use the generic operator transform_generic:

mycirc2 = transform_generic mytransformer mycirc

Finally, we use a main function to display the original circuit and then the transformed one:

main = do
  print_simple Preview mycirc
  print_simple Preview mycirc2

We introduce the notion of a binding as a low-level way to describe functions of varying arities. A binding assigns a value to a wire in a circuit (much like a "valuation" in logic or semantics assigns values to variables).

To iterate through a circuit, one will typically specify initial bindings for the input wires. This encodes the input of the function ⟦C⟧ mentioned in the introduction. The bindings are updated as one passes through each gate. When the iteration is finished, the final bindings assign a value to each output wire of the circuit. This encodes the output of the function ⟦C⟧. Therefore, the interpretation of a circuit is representable as a function from bindings (of input wires) to bindings (of output wires), i.e., it has the type ⟦C⟧ :: Bindings a b -> Bindings a b.

The types T_Gate and Transformer are at the heart of the circuit transformer functionality. Their purpose is to give a concise syntax in which to express semantic functions for gates. As mentioned in the introduction, the programmer needs to specify two type a and b, a monad m, and a semantic function for each gate. With the T_Gate' and Transformer types, the definition takes the following form:

my_transformer :: Transformer m a b
my_transformer (T_Gate1 <parameters> f) = f $ <semantic function for gate 1>
my_transformer (T_Gate2 <parameters> f) = f $ <semantic function for gate 2>
my_transformer (T_Gate3 <parameters> f) = f $ <semantic function for gate 3>
...

The type T_Gate is very higher-order, involving a function f that consumes the semantic function for each gate. The reason for this higher-orderness is that the semantic functions for different gates may have different types.

This higher-orderness makes the T_Gate mechanism hard to read, but easy to use. Effectively we only have to write lengthy and messy code once and for all, rather than once for each transformer. In particular, all the required low-level bindings and unbindings can be handled by general-purpose code, and do not need to clutter each transformer.