The type QCType x y a represents the substitution a [x / Qubit, y / Bit]. For example:

QCType x y (Qubit, Bit, [Qubit]) = (x, y, [x]).

An instance of this must be defined for each new kind of quantum data.

The type QTypeB ba represents the substitution ba [Qubit / Bool]. For example:

QTypeB (Bool, Bool, [Bool]) = (Qubit, Qubit, [Qubit]).

An instance of this must be defined for each new kind of quantum data.

The QCData type class contains heterogeneous data types built up from leaves of type Qubit and Bit. It is the basis for several generic operations that apply to classical and quantum data, such as copying, transformers, simulation, and heterogeneous versions of qterm and qdiscard.

QCData and QData are interrelated, in the sense that the following implications hold:

QData qa   implies   QCData qa
CData ca   implies   QCData ca

Implications in the converse direction also hold whenever qc is a fixed known type:

QCData qc   implies   QData (QType qc)
QCData qc   implies   CData (CType qc)
QCData qc   implies   BData (BType qc)

However, the type checker cannot prove the above implication in the case where qc is a type variable; for this, the more flexible (but more computationally expensive) QCDataPlus class can be used.

SimpleType is a subclass of QCData consisting of simple types. We say that a data type t is "simple" if any two elements of t have the same number of leaves. For example, tuples are simple, but lists are not.

The type operator QType converts a classical or heterogeneous type to a homogeneous quantum type. More precisely, the type QType a represents the substitution a [Qubit / Bit]. It can be applied to both homogeneous and heterogeneous types, and always yields a homogeneous type. For example:

QType (Bit, [Bit]) = (Qubit, [Qubit])
QType (Qubit, Bit) = (Qubit, Qubit)

The type operator CType converts a classical or heterogeneous type to a homogeneous quantum type. More precisely, the type CType a represents the substitution a [Bit / Qubit]. It can be applied to both homogeneous and heterogeneous types, and always yields a homogeneous type. For example:

CType (Qubit, [Qubit]) = (Bit, [Bit])
CType (Qubit, Bit) = (Bit, Bit)

The type operator BType converts a classical, quantum, or heterogeneous type to a homogeneous boolean type. More precisely, the type BType a represents the substitution a [Bool / Qubit, Bool / Bit]. It can be applied to both homogeneous and heterogeneous types, and always yields a homogeneous type. For example:

BType (Qubit, [Qubit]) = (Bool, [Bool])
BType (Qubit, Bit) = (Bool, Bool)

The type operator HType x converts a classical, quantum, or boolean type to a homogeneous type with leaves x. More precisely, the type HType x a represents the substitution a [x / Qubit, x / Bit]. For example:

HType x (Qubit, [Qubit]) = (x, [x])
HType x (Qubit, Bit) = (x, x)

There is a very subtle difference between HType x a and QCType x x a. Although these two types are equal for all x and a, the type checker cannot actually prove that QCType x x a is homogeneous from the assumption QCData a. It can, however, prove that HType x a is homogeneous. Therefore HType (or the slightly more efficient special cases QType, CType, BType) should always be used to create a homogeneous type from a heterogeneous one.

A dummy term of any type. This term is undefined and must never be evaluated. Its only purpose is to hold a type.

A dummy term of type Qubit. It can be used in shape parameters (e.g., qc_init), as well as shape type parameters (e.g., qcdata_mapM).

A dummy term of type Bit. It can be used in shape parameters (e.g., qc_init), as well as shape type parameters (e.g., qcdata_mapM).

A dummy term of type Bool.

Convert a piece of homogeneous quantum data to a shape type parameter. This is guaranteed to never evaluate x, and returns an undefined value.

Convert a piece of homogeneous classical data to a shape type parameter. This is guaranteed to never evaluate x, and returns an undefined value.

Convert a piece of homogeneous boolean data to a shape type parameter. This is guaranteed to never evaluate x, and returns an undefined value. Do not confuse this with the function qshape, which creates a shape value.

A dummy term of the same type as the given term. If x :: a, then dummy x :: a. This is guaranteed not to evaluate x, and returns an undefined value.

The QData type class contains homogeneous data types built up from leaves of type Qubit.

Map a function f over all the leaves of a data structure. The first argument is a dummy shape parameter: its value is ignored, but its type is used to determine the shape of the data to map over.

Example (ignoring the monad for the sake of simplicity):

qdata_mapM (leaf, [leaf]) f (x,[y,z,w]) = (f x, [f y, f z, f w]).

For data types that have a sense of direction, the mapping should preferably be performed from left to right, but this property is not guaranteed and may change without notice.

Zip two data structures with leaf types x and y together, to obtain a new data structure of the same shape with leaf type (x, y). The first three arguments are dummy shape type parameters, representing the shape type and the two leaf types, respectively.

The ErrMsg argument is a stub error message to be used in case of failure.

Sometimes, it is possible to have a boolean parameter with some aspect of its shape indeterminate. The function qdata_promote takes such a boolean parameter, as well as a piece of quantum data, and sets the shape of the former to that of the latter.

Indeterminate shapes can be used with certain operations, such as controlling and terminating, where some aspect of the shape of the parameter can be determined from the context in which it is used. This is useful, e.g., for quantum integers, where one may want to specify a control condition by an integer literal such as 17, without having to specify the number of bits. Thus, we can write, e.g.,

gate `controlled` qi .==. 17

instead of the more cumbersome

gate `controlled` qi .==. (intm (qdint_length qi) 17).

Another useful application of this arises in the use of infinite lists of booleans (such as [False..]), to specify a control condition for a finite list of qubits.

Because this function is used as a building block, we also pass an error message to be used in case of failure. This will hopefully make it clearer to the user which operation caused the error.

The inverse of qdata_zip: Take a data structure with leaf type (x, y), and return two data structures of the same shape with leaf types x and y, respectively. The first three arguments are dummy shape type parameters, analogous to those of qdata_zip.

Map a function over every leaf in a data structure. Non-monadic version of qdata_mapM.

Visit every leaf in a data structure, updating an accumulator.

Map a function over every leaf in a data structure, while also updating an accumulator. This combines the functionality of qdata_fold and qdata_map.

Monadic version of qdata_fold: Visit every leaf in a data structure, updating an accumulator.

Monadic version of qdata_fold_map: Map a function over every leaf in a data structure, while also updating an accumulator. This combines the functionality of qdata_foldM and qdata_mapM.

Return a list of leaves of the given homogeneous data structure. The first argument is a dummy shape type parameter, and is only used for its type.

The leaves are ordered in some deterministic, but arbitrary way. It is guaranteed that when two data structures of the same shape type and shape (same length of lists etc) are sequentialized, the leaves will be ordered the same way. No other property of the order is guaranteed, In particular, it might change without notice.

Take a specimen homogeneous data structure to specify the "shape" desired (length of lists, etc); then reads the given list of leaves in as a piece of homogeneous data of the same shape. The ordering of the leaves is assumed to be the same as that which qdata_sequentialize produces for the given shape.

A "length mismatch" error occurs if the list does not have exactly the required length.

Please note that, by contrast with the function qdata_sequentialize, the first argument is a shape term parameter, not a shape type parameter. It is used to decide where the qubits should go in the data structure.

Combine a shape type argument q, a leaf type argument a, and a shape size argument x into a single shape argument qx. Note:

• q captures only the type, but not the size of the data. Only the type of q is used; its value can be undefined. This is sufficient to determine the depth of leaves in a data structure, but not their number.
• x captures only the size of the data, but not its type. In particular, x may have leaves of non-atomic types. x must consist of well-defined constructors up to the depth of leaves of q, but the values at the actual leaves of x may be undefined.
• The output qx combines the type of q with the size of x, and can therefore be used both as a shape type and a shape value. Note that the actual leaves of qx will be qubit and bit, which are synonyms for undefined.

Example:

q = undefined :: ([Qubit], [[Qubit]])
x = ([undefined, 0], [[undefined], [0, 1]])
qdata_makeshape qc a x = ([qubit, qubit], [[qubit], [qubit, qubit]])

where a :: Int.

Like qdata_mapM, except the leaves are visited in exactly the opposite order. This is used primarily for cosmetic reasons: For example, when initializing a bunch of ancillas, and then terminating them, the circuit will look more symmetric if they are terminated in the opposite order.

Like qdata_promote, except take a piece of classical data.

The CData type class contains homogeneous data types built up from leaves of type Bit.

The BData type class contains homogeneous data types built up from leaves of type Bool.

The QShape class allows the definition of generic functions that can operate on quantum data of any "shape", for example, nested tuples or lists of qubits.

In general, there are three kinds of data: quantum inputs (such as Qubit), classical inputs (such as Bit), and classical parameters (such as Bool). For example, a Qubit can be initialized from a Bool; a Qubit can be measured, resulting in a Bit, etc. For this reason, the type class QShape establishes a relation between three types:

qa

A data structure having Qubit at the leaves.

ca

A data structure of the same shape as qa, having Bit at the leaves.

ba

A data structure of the same shape as qa, having Bool at the leaves.

Some functions input a classical parameter for the sole purpose of establishing the "shape" of a piece of data. The shape refers to qualities of a data structure, such as the length of a list, which are not uniquely determined by the type. For example, two different lists of length 5 have the same shape. When performing a generic operation, such as reversing a circuit, it is often necessary to specify the shape of the inputs, but not the actual inputs.

In the common case where one only needs to declare one of the types qa, ca, or ba, one of the simpler type classes QData, CData, or BData can be used.

The inverse of qcdata_zip: Take a data structure whose leaves are pairs, and return two data structures of the same shape, collecting all the left components and all the right components, respectively. The first five arguments are shape type parameters, analogous to those of qcdata_zip.

Map two functions f and g over the leaves of a heterogeneous data structure. Apply f to all the leaves at Qubit positions, and g to all the leaves at Bit positions. Non-monadic version of qcdata_mapM.

Visit every leaf in a data structure, updating an accumulator. This function requires two accumulator functions f and g, to be used at Qubit positions and Bit positions, respectively.

Map a function over every leaf in a data structure, while also updating an accumulator. This combines the functionality of qcdata_fold and qcdata_map.

Monadic version of qcdata_fold: Visit every leaf in a data structure, updating an accumulator. This function requires two accumulator functions f and g, to be used at Qubit positions and Bit positions, respectively.

Monadic version of qcdata_fold_map: Map a function over every leaf in a data structure, while also updating an accumulator. This combines the functionality of qcdata_foldM and qcdata_mapM.

Return a list of leaves of the given heterogeneous data structure. The first argument is a dummy shape type parameter, and is only used for its type. Leaves in qubit positions and bit positions are returned, respectively, as the left or right components of a disjoint union.

The leaves are ordered in some deterministic, but arbitrary way. It is guaranteed that when two data structures of the same shape type and shape (same length of lists etc) are sequentialized, the leaves will be ordered the same way. No other property of the order is guaranteed, In particular, it might change without notice.

Take a specimen heterogeneous data structure to specify the "shape" desired (length of lists, etc); then reads the given list of leaves in as a piece of heterogeneous data of the same shape. The ordering of the leaves, and the division of the leaves into qubit and bit positions, is assumed to be the same as that which qcdata_sequentialize produces for the given shape.

A "length mismatch" error occurs if the list does not have exactly the required length. A "shape mismatch" error occurs if the list contains an Endpoint_Bit entry corresponding to a Qubit position in the shape, or an Endpoint_Qubit entry corresponding to a Bit position.

Please note that, by contrast with the function qcdata_sequentialize, the first argument is a shape term parameter, not a shape type parameter. It is used to decide where the qubits and bits should go in the data structure.

Combine a shape type argument q, two leaf type arguments a and b, and a shape size argument x into a single shape argument qx. Note:

• q captures only the type, but not the size of the data. Only the type of q is used; its value can be undefined. This is sufficient to determine the depth of leaves in a data structure, but not their number.
• x captures only the size of the data, but not its type. In particular, x may have leaves of non-atomic types. x must consist of well-defined constructors up to the depth of leaves of q, but the values at the actual leaves of x may be undefined.
• The output qx combines the type of q with the size of x, and can therefore be used both as a shape type and a shape value. Note that the actual leaves of qx will be qubit and bit, which are synonyms for undefined.

Example:

qc = undefined :: ([Qubit], [[Bit]])
x = ([undefined, (0,False)], [[undefined], [Just 2, Nothing]])
qcdata_makeshape qc a b x = ([qubit, qubit], [[bit], [bit, bit]])

where a :: (Int,Bool), b :: (Maybe Int).

Like qcdata_mapM, except the leaves are visited in exactly the opposite order. This is used primarily for cosmetic reasons: For example, when initializing a bunch of ancillas, and then terminating them, the circuit will look more symmetric if they are terminated in the opposite order.

The QCDataPlus type class is almost identical to QCData, except that it contains one additional piece of information that allows the type checker to prove the implications

QCDataPlus qc     implies   QShape (BType qc) (QType qc) (CType qc)
QCDataPlus qc     implies   QData (QType qc)
QCDataPlus qc     implies   CData (CType qc)
QCDataPlus qc     implies   BData (BType qc)

This is sometimes useful, for example, in the context of a function that inputs a QCData, measures all the qubits, and returns a CData. However, the additional information for the type checker comes at a price, which is drastically increased compilation time. Therefore QCDataPlus should only be used when QCData is insufficient.

QCDataPlus_Simple is a convenience type class that combines QCDataPlus and SimpleType.

QCDataPlus_Simple is a convenience type class that combines QCDataPlus and SimpleType.

The class QCLeaf consists of the two types Qubit and Bit. It is primarily used for convenience, in those cases (such as the arithmetic library) where some class instance should be defined for the cases Qubit and Bit, but not for general QCData. It is also used, e.g., in the definition of the 'Quipper.(./=.)' operator.

A type to represent a Qubit leaf, for the sole purpose that show will show it as "Q".

A type to represent a Bit leaf, for the sole purpose that show will show it as "C".

Turn any QCData into a string uniquely identifying its type and shape. The current implementation assumes that appropriately unique Show instances are defined for all QCData.

The type operator LType converts Qubit to Qubit_Leaf and Bit to Bit_Leaf.