The Quipper System

Algorithms.TF.Definitions

Description

This module provides global definitions for the Triangle Finding Algorithm.

Synopsis

# Qram abstraction

data Qram Source #

A data structure to hold a Qram implementation. This provides operations for fetching and storing quantum data from a quantum array, addressed by a quantum integer. One implementation is given by algorithms a8_FetchT, a9_StoreT and a10_FetchStoreT.

Constructors

 Qram Fieldsqram_fetch :: forall qa. QData qa => QDInt -> IntMap qa -> qa -> Circ (QDInt, IntMap qa, qa) qram_store :: forall qa. QData qa => QDInt -> IntMap qa -> qa -> Circ (QDInt, IntMap qa, qa) qram_swap :: forall qa. QData qa => QDInt -> IntMap qa -> qa -> Circ (QDInt, IntMap qa, qa)

# Types for the Triangle Finding Algorithm

type CNode = [Bit] Source #

A node of the graph (classical circuit type).

type QNode = [Qubit] Source #

A node of the graph (quantum circuit type).

type QWTFP_spec = (Int, Int, QNode -> QNode -> Qubit -> Circ Qubit, Qram) Source #

The type of problem specifications for the Triangle Finding Problem. A problem specification consists of:

• an integer n which determines the number N=2n of nodes of the graph,
• an integer r which determines the size R=2r of tuples in the Hamming graph,
• a function edge_oracle which inputs two graph nodes and a qubit and flips the qubit if the nodes are connected by an edge and
• additional options, for selecting, e.g., which qRAM implementation should be used.

# TF integers

## Types

We define a QData family of integer datatypes (QIntTF, CIntTF, IntTF). These are similar to (QDInt, CInt, IntM), except that the integers are considered to be mod 2m-1 instead of 2m.

In general, functions on these types should be able to handle both 00…00 and 11…11, and should treat them equally, essentially regarding IntTF, CIntTF, and the computational basis of QIntTF as formal quotients. Some operations are not perfect. One should keep in mind, for example, that specifying a control on a QIntTF of the form q .==. 0 will compare the bitwise representation to 0, and not the logical quotient.

data XIntTF x Source #

All three types QIntTF, CIntTF, and IntTF are special cases of a more general type XIntTF x, parameterized by a type x of bits. It is an abstract type, and details of its implementation is not exposed to user-level code.

Constructors

 XIntTF (XInt x)

Instances

 # Methods(==) :: IntTF -> IntTF -> Bool #(/=) :: IntTF -> IntTF -> Bool # # MethodsshowsPrec :: Int -> IntTF -> ShowS #show :: IntTF -> String #showList :: [IntTF] -> ShowS # Show x => Show (XIntTF x) # MethodsshowsPrec :: Int -> XIntTF x -> ShowS #show :: XIntTF x -> String #showList :: [XIntTF x] -> ShowS # QCLeaf x => QCData (XIntTF x) # Methodsqcdata_mapM :: Monad m => XIntTF x -> (q -> m q') -> (c -> m c') -> QCType q c (XIntTF x) -> m (QCType q' c' (XIntTF x)) Source #qcdata_zip :: XIntTF x -> q -> c -> q' -> c' -> QCType q c (XIntTF x) -> QCType q' c' (XIntTF x) -> ErrMsg -> QCType (q, q') (c, c') (XIntTF x) Source #qcdata_promote :: BType (XIntTF x) -> XIntTF x -> ErrMsg -> BType (XIntTF x) Source # QCLeaf x => Labelable (XIntTF x) String # Methodslabel_rec :: XIntTF x -> String -> LabelMonad () Source # type QTypeB IntTF # type QTypeB IntTF = QIntTF type QCType x y (XIntTF z) # type QCType x y (XIntTF z) = XIntTF (QCType x y z)

The type of fixed-length m-qubit quantum integers, regarded modulo 2m-1.

The type of fixed-length m-bit classical integers, regarded modulo 2m-1.

The type of fixed-length m-bit integer parameters, regarded modulo 2m-1. A value of type IntTF may have indeterminate length, similarly to IntM.

## Operations for IntTF

Convert an IntTF of length m to an Integer in the range {0, …, 2m-2}. If the IntTF has indeterminate length, return the original Integer.

Convert an Integer to an IntTF of indeterminate length.

Convert an Integer to an IntTF of length m.

Return the length of an IntTF, or Nothing if indeterminate.

Set the length of an IntTF to m ≥ 0. This operation is only legal if the input (a) has indeterminate length or (b) has determinate length already equal to m. In particular, it cannot be used to change the length from anything other than from indeterminate to determinate.

If both arguments already have determinate lengths, and they do not coincide, throw an error. The String argument is used as an error message in that case.

Try to set the length of an IntTF to that of another XIntTF value (which could be a QIntTF, a CIntTF, or another IntTF). This will fail with an error if both numbers already have determinate lengths that don't coincide. In this case, the string argument is used as an error message. The promotion is done modulo 2m-1.

Convert an IntTF to human readable form. We show the bit value, i.e., 0 and 2m-1 are shown as different values.

## Operations for QIntTF

Convert a QIntTF to a list of qubits. The conversion is little-headian, i.e., the head of the list holds the least significant digit.

Convert a list of qubits to a QIntTF. The conversion is little-headian, i.e., the head of the list holds the least significant digit.

Return a piece of shape data to represent an m-qubit QIntTF. Please note that the data can only be used as shape; it will be undefined at the leaves.

## Auxiliary functions

The low-level isomorphism from XInt x to XIntTF x. Note that "isomorphism" is between the underlying raw types, and does not respect the arithmetic operations.

The low-level isomorphism from XIntTF x to XInt x. Note that "isomorphism" is between the underlying raw types, and does not respect the arithmetic operations.

Like xint_of_xinttf, but first try to promote the length of the IntTF to that of the given XIntTF.

# Miscellaneous circuit-building functions

phaseFlipIf :: ControlSource ctrl => ctrl -> Circ () Source #

Controlled phase flip of -1.

phaseFlipUnless :: ControlSource ctrl => ctrl -> Circ () Source #

Variant of phaseFlip that performs a phase flip unless all controls are in the given state.

qor :: Qubit -> [(Qubit, Bool)] -> Circ Qubit Source #

qor q c: Applies "not" to q, if any of the control qubits in c is in specified state.

# Arithmetic functions

Increment a standard QDInt (i.e. big-endian, mod 2).

Decrement a standard QDInt (i.e. big-endian, mod 2).

increment_big :: [Qubit] -> Circ [Qubit] Source #

Increment a bit-string, considered as a big-endian integer mod 2.

decrement_big :: [Qubit] -> Circ [Qubit] Source #

Decrement a bit-string, considered as a big-endian integer mod 2.

increment_little :: [Qubit] -> Circ [Qubit] Source #

Increment a bit-string, considered as a little-endian integer mod 2.

decrement_little :: [Qubit] -> Circ [Qubit] Source #

Decrement a bit-string, considered as a little-endian integer mod 2.

choose :: Integral a => a -> a -> a Source #

The standard “combinations” function “n choose k”.

# IntMaps as QData

addKeys :: IntMap a -> IntMap (Key, a) Source #

Replace an IntMap f with the IntMap mapping each key k to (k,f(k)). An auxiliary function for defining mapWithKeyM, etc.

mapWithKeyM :: Monad m => (Key -> a -> m b) -> IntMap a -> m (IntMap b) Source #

Analogous to mapM, but allows the function to use the key. Particularly useful for mapping in parallel over two (or more) IntMaps assumed to have the same domain.

mapWithKeyM_ :: Monad m => (Key -> a -> m b) -> IntMap a -> m () Source #

Analogous to mapM_, but allows the function to use the key.

intMap_replicate :: Int -> a -> IntMap a Source #

Analogous to replicate on lists.

(!) :: IntMap a -> Key -> a infixl 9 Source #

Convenient syntax for accessing elements of an IntMap. Left associative, and binds very strongly, like '(!!)'.

# Orphan instances

 QCData a => QCData (IntMap a) # Methodsqcdata_mapM :: Monad m => IntMap a -> (q -> m q') -> (c -> m c') -> QCType q c (IntMap a) -> m (QCType q' c' (IntMap a)) Source #qcdata_zip :: IntMap a -> q -> c -> q' -> c' -> QCType q c (IntMap a) -> QCType q' c' (IntMap a) -> ErrMsg -> QCType (q, q') (c, c') (IntMap a) Source #qcdata_promote :: BType (IntMap a) -> IntMap a -> ErrMsg -> BType (IntMap a) Source # # Methodslabel_rec :: IntMap a -> String -> LabelMonad () Source # Labelable a s => Labelable (IntMap a) (IntMap s) # Methodslabel_rec :: IntMap a -> IntMap s -> LabelMonad () Source #