Quipper.Algorithms.TF.Definitions

This module provides global definitions for the Triangle Finding Algorithm.

Qram abstraction

data Qram

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

Fields

• qram_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]

A node of the graph (classical circuit type).

type QNode = [Qubit]

A node of the graph (quantum circuit type).

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

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

• an integer n which determines the number N=2ⁿ of nodes of the graph,
• an integer r which determines the size R=2^r 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 2^m-1 instead of 2^m.

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

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

Eq IntTF

Defined in Quipper.Algorithms.TF.Definitions

Methods

(==) :: IntTF -> IntTF -> Bool

(/=) :: IntTF -> IntTF -> Bool

Show IntTF

Defined in Quipper.Algorithms.TF.Definitions

Methods

showsPrec :: Int -> IntTF -> ShowS

show :: IntTF -> String

showList :: [IntTF] -> ShowS

Show x => Show (XIntTF x)

Defined in Quipper.Algorithms.TF.Definitions

Methods

showsPrec :: Int -> XIntTF x -> ShowS

show :: XIntTF x -> String

showList :: [XIntTF x] -> ShowS

QCLeaf x => QCData (XIntTF x)

Defined in Quipper.Algorithms.TF.Definitions

Methods

qcdata_mapM :: Monad m => XIntTF x -> (q -> m q') -> (c -> m c') -> QCType q c (XIntTF x) -> m (QCType q' c' (XIntTF x))

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)

qcdata_promote :: BType (XIntTF x) -> XIntTF x -> ErrMsg -> BType (XIntTF x)

QCLeaf x => Labelable (XIntTF x) String

Defined in Quipper.Algorithms.TF.Definitions

Methods

label_rec :: XIntTF x -> String -> LabelMonad ()

type QTypeB IntTF

Defined in Quipper.Algorithms.TF.Definitions

type QTypeB IntTF = QIntTF

type QCType x y (XIntTF z)

Defined in Quipper.Algorithms.TF.Definitions

type QCType x y (XIntTF z) = XIntTF (QCType x y z)

type QIntTF = XIntTF Qubit

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

type CIntTF = XIntTF Bit

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

type IntTF = XIntTF Bool

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

Operations for IntTF

integer_of_inttf :: IntTF -> Integer

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

inttf_of_integer :: Integer -> IntTF

Convert an Integer to an IntTF of indeterminate length.

inttf :: Int -> Integer -> IntTF

Convert an Integer to an IntTF of length m.

inttf_length :: IntTF -> Maybe Int

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

inttf_set_length :: Int -> IntTF -> String -> IntTF

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.

inttf_promote :: IntTF -> XIntTF x -> String -> IntTF

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 2^m-1.

show_inttf :: IntTF -> String

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

Operations for QIntTF

qulist_of_qinttf_lh :: QIntTF -> [Qubit]

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.

qinttf_of_qulist_lh :: [Qubit] -> QIntTF

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.

qinttf_shape :: Int -> QIntTF

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

xinttf_of_xint :: XInt x -> XIntTF x

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.

xint_of_xinttf :: XIntTF x -> XInt x

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.

xint_with_promote :: XIntTF y -> IntTF -> IntM

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

Controlled phase flip of -1.

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

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

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

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

Arithmetic functions

increment :: QDInt -> Circ QDInt

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

decrement :: QDInt -> Circ QDInt

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

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

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

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

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

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

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

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

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

choose :: Integral a => a -> a -> a

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

IntMaps as QData

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

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)

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

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

intMap_replicate :: Int -> a -> IntMap a

Analogous to replicate on lists.

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

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

Orphan instances

QCData a => QCData (IntMap a)

Methods

qcdata_mapM :: Monad m => IntMap a -> (q -> m q') -> (c -> m c') -> QCType q c (IntMap a) -> m (QCType q' c' (IntMap a))

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)

qcdata_promote :: BType (IntMap a) -> IntMap a -> ErrMsg -> BType (IntMap a)

Labelable a String => Labelable (IntMap a) String

Methods

label_rec :: IntMap a -> String -> LabelMonad ()

Labelable a s => Labelable (IntMap a) (IntMap s)

Methods

label_rec :: IntMap a -> IntMap s -> LabelMonad ()