Wire identifier. Wires are currently identified by an integer, but the users of this interface should be oblivious to this.

Wire type. A wire is either quantum or classical.

An arity, also known as a typing context, is a map from a finite set of wires to wire types.

A signed item of type a. Signed x True represents a positive item, and Signed x False represents a negative item.

When used with wires in a circuit, a positive sign is used to represent a positive control, i.e., a filled dot, and a negative sign is used to represent a negative control, i.e., an empty dot.

Extract the underlying item of a signed item.

Extract the sign of a signed item: True is positive, and False is negative.

A list of controlled wires, possibly empty.

A time step is a small floating point number used as a parameter to certain gates, such as rotation gates or the e^−iZt gate.

A flag that, if True, indicates that the gate is inverted.

A flag that, if True, indicates that the gate is controllable, but any further controls on the gate should be ignored. This is used, e.g., for circuits consisting of a basis change, some operation, and the inverse basis change. When controlling such a circuit, it is sufficient to control the middle operation, so the gates belonging to the basis change and its inverse will have the NoControlFlag set.

A flag, to specify if the corresponding subroutine can be controlled. Either no control allowed, or all controls, or only classical.

An identifier for a subroutine. A boxed subroutine is currently identified by a pair of: the user-defined name of the subroutine; and a value uniquely identifying the type and shape of the argument.

For now, we represent the shape as a string, because this gives an easy total Ord instance, needed for Data.Map. However, in principle, one could also use a pair of a type representation and a shape term. The implementation of this may change later.

A flag that indicates how many times a particular subroutine should be repeated. If non-zero, it implies some constraints on the type of the subroutine.

The low-level representation of gates.

Compute the incoming and outgoing wires of a given gate (excluding controls, comments, and anchors). This essentially encodes the type information of the basic gates. If a wire is used multiple times as an input or output, then gate_arity also returns it multiple times; this enables run-time type checking.

Note that gate_arity returns the logical wires, and therefore excludes things like labels, comments, and graphical anchors. This is in contrast to wires_of_gate, which returns the syntactic set of wires used by the gate.

Return the controls of a gate (or an empty list if the gate has no controls).

Return the NoControlFlag of a gate, or False if it doesn't have one.

Apply the given NoControlFlag to the given Gate. This means, if the first parameter is True, set the gate's NoControlFlag, otherwise do nothing. Throw an error if attempting to set the NoControlFlag on a gate that can't support this flag.

Reverse a gate. Throw an error if the gate is not reversible.

Return the set of wires used by a list of controls.

Return the set of wires used by a gate (including controls, labels, and anchors).

Unlike gate_arity, the function wires_of_gate is used for printing, and therefore returns all wires that are syntactically used by the gate, irrespective of whether they have a logical meaning.

Like wires_of_gate, except return a list of wires.

Recall that an Arity is a set of typed wires, and it determines the external interfaces at which circuits and gates can be connected. The type ExtArity stores the same information as the type Arity, but in a format that is more optimized for efficient updating. Additionally, it also stores the set of wires ever used.

Check whether the given gate is well-formed and can be legally applied in the context of the given arity. If successful, return the updated arity resulting from the gate application. If unsuccessful, raise an error. Properties checked are:

• that each gate has non-overlapping inputs, including controls;
• that each gate has non-overlapping outputs, including controls;
• that the inputs of the gate (including controls) are actually present in the current arity;
• that the types of the inputs (excluding controls) match those of the current arity;
• that the outputs of the gate (excluding controls) don't conflict with any wires already existing in the current arity.

Like arity_append, but without type checking. This is potentially faster, but should only used in applications that have already been thoroughly tested or type-checked.

For now, we disable run-time type checking, because we have not yet implemented run-time types properly. Therefore, we define arity_append to be a synonym for arity_append_unsafe.

Return an empty arity.

Return a wire unused in the current arity.

Return the next k wires unused in the current arity.

Add a new typed wire to the current arity. This returns a new wire and the updated arity.

Convert an extended arity to an ordinary arity.

Return the smallest wire id nowhere used in the circuit.

A completed circuit (a1,gs,a2,n) has an input arity a1, a list of gates gs, and an output arity a2. We also record n, the total number of wires used by the circuit. Because wires are allocated consecutively, this means that the wire id's used are [0..n-1].

Return the set of all the wires in a circuit.

Reverse a gate list.

Reverse a circuit. Throw an error if the circuit is not reversible.

Set the NoControlFlag on all gates of a circuit.

An ordered circuit is a Circuit together with an ordering on (usually all, but potentially a subset of) the input and output endpoints.

This extra information is required when a circuit is used within a larger circuit (e.g. via a Subroutine gate), to identify which wires of the sub-circuit should be bound to which wires of the surrounding circuit.

Reverse an OCircuit. Throw an error if the circuit is not reversible.

One often wants to consider the inputs and outputs of a circuit as more structuredtyped than just lists of bitsqubits; for instance, a list of six qubits could be structured as a pair of triples, or a triple of pairs, or a six-bit QDInt.

While for the most part this typing information is not included in low-level circuits, we need to consider it in hierarchical circuits, so that the information stored in a subroutine is sufficient to call the subroutine in a typed context.

Specifically, the extra information needed consists of functions to destructure the input/output data as a list of typed wires, and restructure such a list of wires into a piece of data of the appropriate type.

The trivial CircuitTypeStructure on ([Wire],Arity).

Use a CircuitTypeStructure to destructure a piece of (suitably typed) data into a list of typed wires.

Use a CircuitTypeStructure to structure a list of typed wires (of the appropriate length/arity) into a piece of structured data.

A typed subroutine consists of:

• a low-level circuit, ordered to allow binding of incoming and outgoing wires;
• functions for structuring/destructuring the inputs and outputs to and from lists of wires (these functions being dynamically typed, since the input/output type may vary between subroutines);
• a ControllableFlag, recording whether the circuit is controllable.

Extract just the Circuit from a TypedSubroutine.

A name space is a map from names to subroutine bindings. These subroutines can reference each other; it is the programmer’s responsibility to ensure there is no circular dependency, and no clash of names.

The empty namespace.

A function to display the names of all the subroutines in a Namespace.

A boxed circuit is a distinguished simple circuit (analogous to a “main” function) together with a namespace.

An ordered boxed circuit is a BCircuit together with an ordering on the input and output endpoints, or equivalently, an OCircuit together with a namespace.

Construct an OBCircuit from a BCircuit and an ordering on the input and output endpoints.

Reverse a simple boxed circuit, or throw an error if not reversible.

The ReadWrite monad describes a standard read-write computation, here specialized to the case where writes are Gates, prompts are Bits, and reads are Bools. Thus, a read-write computation can do three things:

• terminate with a result. This is the case RW_Return.
• write a single Gate and continue. This is the case RW_Write.
• issue a prompt, which is a Wire, then read a Bool, then continue. This is the case RW_Read.

Transforms a read-write computation into one that behaves identically, but also returns the list of gates generated.

This is used as a building block, for example to allow a read-write computation to be run in a simulator while simultaneously using a static backend to print the list of generated gates.

Extract the contents of a static ReadWrite computation. A ReadWrite computation is said to be static if it contains no RW_Read instructions, or in other words, no dynamic lifting. If an RW_Read instruction is encountered, issue an error message using the given stub.

Turn a static read-write computation into a list of gates, while also updating a namespace. "Static" means that the computation may not contain any RW_Read operations. If it does, the message "dynamic lifting" is passed to the given error handler.

Important usage note: This function returns a triple (gates, ns, x). The list of gates is generated lazily, and can be consumed one gate at a time. However, the values ns and x are only computed at the end of the computation. Any function using them should not apply a strict pattern match to ns or x, or else the whole list of gates will be generated in memory. For example, the following will blow up the memory:

(gates, ns, (a, n, x)) = gatelist_of_readwrite errmsg comp

whereas the following will work as intended:

(gates, ns, ~(a, n, x)) = gatelist_of_readwrite errmsg comp

The type of dynamic boxed circuits. The type DBCircuit a is the appropriate generalization of (BCircuit, a), in a setting that is dynamic rather than static (i.e., with dynamic lifting or "interactive measurement").

Convert a dynamic boxed circuit to a static boxed circuit. The dynamic boxed circuit may not contain any dynamic liftings, since these cannot be performed in a static setting. In case any output liftings are encountered, try to issue a meaningful error via the given stub error message.

Convert a boxed circuit to a dynamic boxed circuit. The latter, of course, contains no RW_Read instructions.