quipper-core-0.8.0.1: An embedded, scalable functional programming language for quantum computing.

Quipper.QData

Description

This module provides type classes for dealing with various "shaped" quantum and classical data structures. Examples of data structures are tuples, lists, records, registers, arrays, indexed arrays, etc. Is it convenient to extend certain operations to arbitrary quantum data structures; for example, instead of measuring a single qubit and obtaining a bit, one may measure an n-tuple of qubits and obtain an n-tuple of bits. We call an operation "generic" if it can act on arbitrary data structures.

This module provides shaped types and low-level combinators, in terms of which higher-level generic quantum operations can be defined.

The low-level combinators provided by this module (with names qcdata_* and qdata_*) should never be used directly in user code (and for this reason, they are not re-exported by Quipper). Instead, they are intended as building blocks for user-level generic functions (in Quipper.Generic and related modules). The only exception is that the functions may be used in libraries or user-level code to define new quantum data constructors. Modules that contain such definitions should import Internal.

Synopsis

# Introduction

The data types we consider here come in two varieties: homogeneous and heterogeneous types.

A homogeneous data type describes a data structure that is built up from only one kind of basic data (for example, only qubits, only classical bits, or only boolean parameters). The following are typical examples of homogeneous types:

qa = (Qubit, Qubit, [Qubit])
ca = (Bit, Bit, [Bit])
ba = (Bool, Bool, [Bool]).

An important feature of homogeneous types is that they can be related to each other by shape. For example, ca above is the "classical version" of qa. We say that the above types qa, ca, and ba all share the same shape type. On the other hand, they differ in their leaf types, which are Qubit, Bit, and Bool, respectively.

When naming types, variables, and operations related to homogeneous data structures, we often use letters such as q, c, and b to denote, respectively, the quantum, classical, and boolean versions of some concept.

Homogeneous types are made available to Quipper programs via the QData and QShape type classes.

A heterogeneous data type describes a data structure that may contain both classical and quantum bits. A typical example of a heterogeneous type is:

qc = (Qubit, Bit, [Qubit]).

Heterogeneous types are often used to represent sets of endpoints of a circuit, or the inputs or outputs to some circuit building function. We often use the letters qc in connection with heterogeneous types.

Heterogeneous types are made available to Quipper programs via the QCData and QCDataPlus type classes.

# Primitive definitions

The type classes of this module are all derived from four primitive items, which must be defined by induction on types:

• A type class QCData qc, representing structured data types made up from classical and quantum leaves.
• A type family QCType x y qc, representing the type-level substitution operation [nobr qc [x / Qubit, y / Bit]].
• A type family QTypeB ba, representing the type-level substitution [nobr ba [Qubit / Bool]].
• A type class SimpleType qc, representing "simple" data 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.

An instance of QCData, QCType and QTypeB must be defined for each new kind of quantum data. If the quantum data is simple, an instance of SimpleType must also be defined.

All other notions in this module are defined in terms of the above four, and therefore need not be defined on a per-type basis.

## The QCType operation

type family QCType x y a Source #

The type QCType x y a represents the substitution [nobr 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.

Instances

 type QCType x y Char Source # type QCType x y Char = Char type QCType x y Float Source # type QCType x y Float = Float type QCType x y Double Source # type QCType x y Double = Double type QCType x y Int Source # type QCType x y Int = Int type QCType x y Integer Source # type QCType x y Integer = Integer type QCType x y () Source # type QCType x y () = () type QCType x y Bit Source # type QCType x y Bit = y type QCType x y Qubit Source # type QCType x y Qubit = x type QCType x y (Signed a) Source # type QCType x y (Signed a) = Signed (QCType x y a) type QCType x y [a] Source # type QCType x y [a] = [QCType x y a] type QCType x y (B_Endpoint a b) Source # type QCType x y (B_Endpoint a b) = B_Endpoint (QCType x y a) (QCType x y b) type QCType x y (a, b) Source # type QCType x y (a, b) = (QCType x y a, QCType x y b) type QCType x y (a, b, c) Source # type QCType x y (a, b, c) = (QCType x y a, QCType x y b, QCType x y c) type QCType x y (a, b, c, d) Source # type QCType x y (a, b, c, d) = (QCType x y a, QCType x y b, QCType x y c, QCType x y d) type QCType x y (a, b, c, d, e) Source # type QCType x y (a, b, c, d, e) = (QCType x y a, QCType x y b, QCType x y c, QCType x y d, QCType x y e) type QCType x y (a, b, c, d, e, f) Source # type QCType x y (a, b, c, d, e, f) = (QCType x y a, QCType x y b, QCType x y c, QCType x y d, QCType x y e, QCType x y f) type QCType x y (a, b, c, d, e, f, g) Source # type QCType x y (a, b, c, d, e, f, g) = (QCType x y a, QCType x y b, QCType x y c, QCType x y d, QCType x y e, QCType x y f, QCType x y g) type QCType x y (a, b, c, d, e, f, g, h) Source # type QCType x y (a, b, c, d, e, f, g, h) = (QCType x y a, QCType x y b, QCType x y c, QCType x y d, QCType x y e, QCType x y f, QCType x y g, QCType x y h) type QCType x y (a, b, c, d, e, f, g, h, i) Source # type QCType x y (a, b, c, d, e, f, g, h, i) = (QCType x y a, QCType x y b, QCType x y c, QCType x y d, QCType x y e, QCType x y f, QCType x y g, QCType x y h, QCType x y i) type QCType x y (a, b, c, d, e, f, g, h, i, j) Source # type QCType x y (a, b, c, d, e, f, g, h, i, j) = (QCType x y a, QCType x y b, QCType x y c, QCType x y d, QCType x y e, QCType x y f, QCType x y g, QCType x y h, QCType x y i, QCType x y j)

## The QTypeB operation

type family QTypeB a Source #

The type QTypeB ba represents the substitution [nobr 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.

Instances

 type QTypeB Bool Source # type QTypeB Bool = Qubit type QTypeB Char Source # type QTypeB Char = Char type QTypeB Double Source # type QTypeB Double = Double type QTypeB Float Source # type QTypeB Float = Float type QTypeB Int Source # type QTypeB Int = Int type QTypeB Integer Source # type QTypeB Integer = Integer type QTypeB () Source # type QTypeB () = () type QTypeB [a] Source # type QTypeB [a] = [QTypeB a] type QTypeB (Signed a) Source # type QTypeB (Signed a) = Signed (QTypeB a) type QTypeB (a, b) Source # type QTypeB (a, b) = (QTypeB a, QTypeB b) type QTypeB (B_Endpoint a b) Source # type QTypeB (B_Endpoint a b) = B_Endpoint (QTypeB a) (QTypeB b) type QTypeB (a, b, c) Source # type QTypeB (a, b, c) = (QTypeB a, QTypeB b, QTypeB c) type QTypeB (a, b, c, d) Source # type QTypeB (a, b, c, d) = (QTypeB a, QTypeB b, QTypeB c, QTypeB d) type QTypeB (a, b, c, d, e) Source # type QTypeB (a, b, c, d, e) = (QTypeB a, QTypeB b, QTypeB c, QTypeB d, QTypeB e) type QTypeB (a, b, c, d, e, f) Source # type QTypeB (a, b, c, d, e, f) = (QTypeB a, QTypeB b, QTypeB c, QTypeB d, QTypeB e, QTypeB f) type QTypeB (a, b, c, d, e, f, g) Source # type QTypeB (a, b, c, d, e, f, g) = (QTypeB a, QTypeB b, QTypeB c, QTypeB d, QTypeB e, QTypeB f, QTypeB g) type QTypeB (a, b, c, d, e, f, g, h) Source # type QTypeB (a, b, c, d, e, f, g, h) = (QTypeB a, QTypeB b, QTypeB c, QTypeB d, QTypeB e, QTypeB f, QTypeB g, QTypeB h) type QTypeB (a, b, c, d, e, f, g, h, i) Source # type QTypeB (a, b, c, d, e, f, g, h, i) = (QTypeB a, QTypeB b, QTypeB c, QTypeB d, QTypeB e, QTypeB f, QTypeB g, QTypeB h, QTypeB i) type QTypeB (a, b, c, d, e, f, g, h, i, j) Source # type QTypeB (a, b, c, d, e, f, g, h, i, j) = (QTypeB a, QTypeB b, QTypeB c, QTypeB d, QTypeB e, QTypeB f, QTypeB g, QTypeB h, QTypeB i, QTypeB j)

## The QCData class

The QCData class provides only three primitive combinators: qcdata_mapM, qcdata_zip, and qcdata_promote. These are sufficient to define all other shape-generic operations.

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

The functions qcdata_mapM and qcdata_zip require "shape type parameters". These are dummy arguments whose value is ignored, but whose type is used to determine the shape of the data to map over. The dummy terms qubit :: Qubit and bit :: Bit may be used to represent leaves in shape type arguments.

Note to programmers defining new QCData instances: Instances must ensure that the functions qcdata_mapM and qcdata_zip do not evaluate their dummy arguments. These arguments will often be undefined. In particular, if using a pattern match on this argument, only a variable or a lazy pattern can be used.

class (Labelable qc String, Typeable qc, Show qc, Show (LType qc), qc ~ QCType Qubit Bit qc, CType (QType qc) ~ CType qc, BType (CType qc) ~ BType qc, QCType Int Bool (CType qc) ~ BType qc) => QCData qc where Source #

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.

Minimal complete definition

Methods

qcdata_mapM :: Monad m => qc -> (q -> m q') -> (c -> m c') -> QCType q c qc -> m (QCType q' c' qc) Source #

Map two functions f and g over all 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. The first argument is a shape type parameter.

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

qcdata_mapM (qubit, bit, [qubit]) f g (x,y,[z,w]) = (f x, g 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.

qcdata_zip :: qc -> q -> c -> q' -> c' -> QCType q c qc -> QCType q' c' qc -> ErrMsg -> QCType (q, q') (c, c') qc Source #

Zip two heterogeneous data structures together, to obtain a new data structure of the same shape, whose elements are pairs of the corresponding elements of the input data structures. The zipping is strict, meaning that both input data structure must have exactly the same shape (same length of lists, etc). The first five arguments are shape type parameters, representing the shape of the data structure, the two leaf types of the first data structure, and the two leaf types of the second data structure, respectively.

Example:

qcdata_zip (bit, [qubit]) int bool char string (True, [2,3]) ("b", ['c', 'd']) = ((True, "b"), [(2,'c'), (3,'d')])
where the shape parameters are:
int = dummy :: Int
bool = dummy :: Bool
char = dummy :: Char
string = dummy :: String  

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

qcdata_promote :: BType qc -> qc -> ErrMsg -> BType qc Source #

It is sometimes convenient to have a boolean parameter with some aspect of its shape indeterminate. The function qcdata_promote takes such a boolean parameter, as well as a piece of QCData, and attempts to set the shape of the former to that of the latter.

The kinds of promotions that are allowed depend on the data type. For example, for simple types, qcdata_promote has no work to do and should just return the first argument. For types that are not simple, but where no promotion is desired (e.g. Qureg), qcdata_promote should check that the shapes of the first and second argument agree, and throw an error otherwise. For lists, we allow a longer list to be promoted to a shorter one, but not the other way around. For quantum integers, we allow an integer of indeterminate length to be promoted to a determinate length, but we do not allow a determinate length to be changed to another determinate length.

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

Instances

## The SimpleType class

class QCData qc => SimpleType qc where Source #

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.

Minimal complete definition

fs_shape

Methods

fs_shape :: qc Source #

Produce a term of the given shape. This term will contain well-defined data constructors, but may be undefined at the leaves.

Instances

 Source # Methodsfs_shape :: () Source # Source # Methods Source # Methods (SimpleType a, SimpleType b) => SimpleType (a, b) Source # Methodsfs_shape :: (a, b) Source # (SimpleType a, SimpleType b, SimpleType c) => SimpleType (a, b, c) Source # Methodsfs_shape :: (a, b, c) Source # (SimpleType a, SimpleType b, SimpleType c, SimpleType d) => SimpleType (a, b, c, d) Source # Methodsfs_shape :: (a, b, c, d) Source # (SimpleType a, SimpleType b, SimpleType c, SimpleType d, SimpleType e) => SimpleType (a, b, c, d, e) Source # Methodsfs_shape :: (a, b, c, d, e) Source # (SimpleType a, SimpleType b, SimpleType c, SimpleType d, SimpleType e, SimpleType f) => SimpleType (a, b, c, d, e, f) Source # Methodsfs_shape :: (a, b, c, d, e, f) Source # (SimpleType a, SimpleType b, SimpleType c, SimpleType d, SimpleType e, SimpleType f, SimpleType g) => SimpleType (a, b, c, d, e, f, g) Source # Methodsfs_shape :: (a, b, c, d, e, f, g) Source # (SimpleType a, SimpleType b, SimpleType c, SimpleType d, SimpleType e, SimpleType f, SimpleType g, SimpleType h) => SimpleType (a, b, c, d, e, f, g, h) Source # Methodsfs_shape :: (a, b, c, d, e, f, g, h) Source # (SimpleType a, SimpleType b, SimpleType c, SimpleType d, SimpleType e, SimpleType f, SimpleType g, SimpleType h, SimpleType i) => SimpleType (a, b, c, d, e, f, g, h, i) Source # Methodsfs_shape :: (a, b, c, d, e, f, g, h, i) Source # (SimpleType a, SimpleType b, SimpleType c, SimpleType d, SimpleType e, SimpleType f, SimpleType g, SimpleType h, SimpleType i, SimpleType j) => SimpleType (a, b, c, d, e, f, g, h, i, j) Source # Methodsfs_shape :: (a, b, c, d, e, f, g, h, i, j) Source #

# Type conversions

We define convenient abbreviations for conversions to, or between, homogeneous types.

type QType a = QCType Qubit Qubit a Source #

The type operator QType converts a classical or heterogeneous type to a homogeneous quantum type. More precisely, the type QType a represents the substitution [nobr 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)

type CType a = QCType Bit Bit a Source #

The type operator CType converts a classical or heterogeneous type to a homogeneous quantum type. More precisely, the type CType a represents the substitution [nobr 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)

type BType a = QCType Bool Bool a Source #

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 [nobr 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)

type HType leaf qa = QCType leaf leaf (QType qa) Source #

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 [nobr 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.

# Shape parameters

Several operations, such as qcdata_mapM and qcdata_zip, require a "shape type parameter". The purpose of such a parameter is only to fix a type; its value is completely unused.

Introduction to shape type parameters

The need for shape type parameters arises when dealing with a data structure whose leaves are of some arbitrary type, rather than Qubit, Bit, or Bool. For example, consider the data structure

[(1, 2), (3, 4)]

This could be parsed in several different ways:

• as a data structure [(leaf, leaf), (leaf, leaf)], where each leaf is an integer;
• as a data structure [leaf, leaf], where each leaf is a pair of integers;
• as a data structure leaf, where each leaf is a list of pairs of integers.

The purpose of a shape type is to disambiguate this situation. In shape types, the type Qubit (and sometimes Bit, in the case of heterogeneous types) takes the place of a leaf. In the three situations of the above example, the shape type would be [(Qubit, Qubit)] in the first case; [Qubit] in the second case, the Qubit in the third case.

Difference between shape type parameters and shape term parameters

A shape type parameter exists only to describe a type; its value is irrelevant and often undefined. A shape type parameter describes the location of leaves in a type. On the other hand, the purpose of a shape term parameter is used to fix the number and locations of leaves in a data structure (for example, to fix the length of a list). Shape term parameters are also often just called "shape parameters" in Quipper.

The distinction is perhaps best illustrated in an example. A typical shape type parameter is

undefined :: (Qubit, [Qubit], [[Bit]])

A typical shape term parameter is

(qubit, [qubit, qubit, qubit], [[bit, bit], []]) :: (Qubit, [Qubit], [[Bit]])

Both of them have the same type. The shape type parameter specifies that the data structure is a triple consisting of a qubit, a list of qubits, and a list of lists of bits. The shape term parameter moreover specifies that the first list consists of exactly three qubits, and the second lists consists of a list of two bits and a list of zero bits.

Note that the value of the shape type parameter is undefined (we often use the term dummy instead of undefined, to get more meaningful error messages). On the other hand, the value of the shape term parameter is partially defined; only the leaves are of undefined value.

Functions for specifying shape type parameters

Since it is not possible, in Haskell, to pass a type as an argument to a function, we provide some terms whose only purpose is to represent types. All of them have value undefined. Effectively, a shape type parameter is a type "written as a term".

The following terms can also be combined in data structures to represent composite types. For example:

(qubit, [bit]) :: (Qubit, [Bit])

dummy :: a Source #

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.

shapetype_q :: QData qa => QType qa -> qa Source #

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

shapetype_c :: QData qa => CType qa -> qa Source #

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

shapetype_b :: QData qa => BType qa -> qa Source #

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.

shape :: a -> a Source #

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.

# Homogeneous types

## The QData class

The QData type class contains homogeneous data types built up from leaves of type Qubit. It contains no methods; all of its functionality is derived from QCData. It does, however, contain a number of equations that help the type checker figure out how to convert heterogeneous type to homogeneous ones and vice versa.

class (qa ~ QType (CType qa), qa ~ QTypeB (BType qa), qa ~ QCType Qubit Bool qa, qa ~ QType qa, QCData qa, QCData (CType qa)) => QData qa Source #

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

Instances

 ((~) * qa (QType (CType qa)), (~) * qa (QTypeB (BType qa)), (~) * qa (QCType Qubit Bool qa), (~) * qa (QType qa), QCData qa, QCData (CType qa)) => QData qa Source #

## Derived combinators on QData

This section provides several convenient combinators for the QData class. All of them are definable from those of QCData.

qdata_mapM :: (QData qa, Monad m) => qa -> (x -> m y) -> HType x qa -> m (HType y qa) Source #

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.

qdata_zip :: QData qa => qa -> x -> y -> HType x qa -> HType y qa -> ErrMsg -> HType (x, y) qa Source #

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.

qdata_promote :: QData qa => BType qa -> qa -> ErrMsg -> BType qa Source #

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

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.

qdata_unzip :: QData s => s -> x -> y -> HType (x, y) s -> (HType x s, HType y s) Source #

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.

qdata_map :: QData s => s -> (x -> y) -> HType x s -> HType y s Source #

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

qdata_fold :: QData s => s -> (x -> w -> w) -> HType x s -> w -> w Source #

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

qdata_fold_map :: QData s => s -> (x -> w -> (y, w)) -> HType x s -> w -> (HType y s, w) Source #

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.

qdata_foldM :: (QData s, Monad m) => s -> (x -> w -> m w) -> HType x s -> w -> m w Source #

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

qdata_fold_mapM :: (QData s, Monad m) => s -> (x -> w -> m (y, w)) -> HType x s -> w -> m (HType y s, w) Source #

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.

qdata_sequentialize :: QData s => s -> HType x s -> [x] Source #

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.

qdata_unsequentialize :: QData s => s -> [x] -> HType x s Source #

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.

qdata_makeshape :: QData qa => qa -> a -> HType a qa -> qa Source #

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.

qdata_mapM_op :: (QData s, Monad m) => s -> (x -> m y) -> HType x s -> m (HType y s) Source #

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.

qdata_promote_c :: QData s => BType s -> CType s -> ErrMsg -> BType s Source #

Like qdata_promote, except take a piece of classical data.

## The CData and BData classes

class (QData (QType ca), CType (QType ca) ~ ca) => CData ca Source #

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

Instances

 (QData (QType ca), (~) * (CType (QType ca)) ca) => CData ca Source #

class (QData (QTypeB ba), BType (QTypeB ba) ~ ba) => BData ba Source #

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

Instances

 (QData (QTypeB ba), (~) * (BType (QTypeB ba)) ba) => BData ba Source #

## The QShape class

By definition, QShape ba qa ca means that ba, qa, and ca are, respectively, boolean, quantum, and classical homogeneous data types of the same common shape. The QShape class directly defined in terms of the QData class. In fact, the two classes are interchangeable in the following sense:

QShape ba qa ca   implies   QData qa,

and conversely,

QData qa        implies   QShape (BType qa) qa (CType qa).

Moreover, the functional dependencies ba -> qa, qa -> ca, ca -> ba ensure that each of the three types determines the other two. Therefore, in many ways, QShape is just a convenient notation for functionality already present in QData.

class (QData qa, CType qa ~ ca, BType qa ~ ba) => QShape ba qa ca | ba -> qa, qa -> ca, ca -> ba Source #

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.

Instances

 (QData qa, (~) * (BType qa) ba, (~) * (CType qa) ca) => QShape ba qa ca Source #

# Heterogeneous types

A heterogeneous type describes a data structure built up from leaves of type Qubit and Bit. Such types are used, for example, to represent sets of endpoints in circuits, parameters to subroutines and circuit building functions. A typical example is:

(Bit, Qubit, [Qubit]).

## Derived combinators on QCData

The QCData type class only contains the three primitive combinators qcdata_mapM, qcdata_zip, and qcdata_promote. Many other useful combinators are definable in terms of these, and we provide several of them here.

qcdata_unzip :: QCData qc => qc -> q -> c -> q' -> c' -> QCType (q, q') (c, c') qc -> (QCType q c qc, QCType q' c' qc) Source #

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.

qcdata_map :: QCData qc => qc -> (q -> q') -> (c -> c') -> QCType q c qc -> QCType q' c' qc Source #

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.

qcdata_fold :: QCData qc => qc -> (q -> w -> w) -> (c -> w -> w) -> QCType q c qc -> w -> w Source #

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.

qcdata_fold_map :: QCData qc => qc -> (q -> w -> (q', w)) -> (c -> w -> (c', w)) -> QCType q c qc -> w -> (QCType q' c' qc, w) Source #

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.

qcdata_foldM :: (QCData qc, Monad m) => qc -> (q -> w -> m w) -> (c -> w -> m w) -> QCType q c qc -> w -> m w Source #

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.

qcdata_fold_mapM :: (QCData qc, Monad m) => qc -> (q -> w -> m (q', w)) -> (c -> w -> m (c', w)) -> QCType q c qc -> w -> m (QCType q' c' qc, w) Source #

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.

qcdata_sequentialize :: QCData qc => qc -> QCType q c qc -> [B_Endpoint q c] Source #

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.

qcdata_unsequentialize :: QCData qc => qc -> [B_Endpoint q c] -> QCType q c qc Source #

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.

qcdata_makeshape :: QCData qc => qc -> a -> b -> QCType a b qc -> qc Source #

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).

qcdata_mapM_op :: (QCData qc, Monad m) => qc -> (q -> m q') -> (c -> m c') -> QCType q c qc -> m (QCType q' c' qc) Source #

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 class

class (QCData qc, QData (QType qc)) => QCDataPlus qc Source #

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.

Instances

 (QCData qc, QData (QType qc)) => QCDataPlus qc Source #

## Fixed size QCDataPlus

class (QCData qc, SimpleType qc) => QCData_Simple qc Source #

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

Instances

 (QCData qc, SimpleType qc) => QCData_Simple qc Source #

class (QCDataPlus qc, SimpleType qc) => QCDataPlus_Simple qc Source #

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

Instances

 (QCDataPlus qc, SimpleType qc) => QCDataPlus_Simple qc Source #

## The QCLeaf class

class (QCData q, SimpleType q, ControlSource q, ControlSource (Signed q), Labelable q String, QCType Qubit Bit q ~ q, QCType Bool Bool q ~ Bool) => QCLeaf q Source #

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 ./=. operator.

Instances

 Source # Source #

## Canonical string representation

For the purpose of storing boxed subroutines, it is useful to have a unique representation of QCData shapes as strings. The currently implementation relies on show to give unique representations. Therefore, when defining Show instances for QCData, one should make sure that the generated strings contain enough information to recover both the type and the shape uniquely.

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

Constructors

 Qubit_Leaf

Instances

 Source # MethodsshowList :: [Qubit_Leaf] -> ShowS #

data Bit_Leaf Source #

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

Constructors

 Bit_Leaf

Instances

 Source # MethodsshowList :: [Bit_Leaf] -> ShowS #

canonical_shape :: QCData qc => qc -> String Source #

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.

# Defining new QCData instances

To define a new kind of quantum data, the following must be defined:

• A class instance of QCData,
• a type instance of QCType, and
• a type instance of QTypeB.

If the new type is simple, an class instance of SimpleType should also be defined.

If the new type may be integrated with Template Haskell, a class instance of CircLiftingUnpack should also be defined.

To ensure that circuit labeling will work for the new type, a class instance of Labelable must also be defined for every member of QCData. See Quipper.Labels for detailed instructions on how to do so.

Modules that define new kinds of quantum data should import Quipper.Internal.