The Quipper System

Safe HaskellNone

Algorithms.TF.Definitions

Contents

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 

Fields

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

Eq IntTF # 

Methods

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

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

Show IntTF # 

Methods

showsPrec :: Int -> IntTF -> ShowS #

show :: IntTF -> String #

showList :: [IntTF] -> ShowS #

Show x => Show (XIntTF x) # 

Methods

showsPrec :: Int -> XIntTF x -> ShowS #

show :: XIntTF x -> String #

showList :: [XIntTF x] -> ShowS #

QCLeaf x => QCData (XIntTF x) # 

Methods

qcdata_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 # 

Methods

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

type QTypeB IntTF # 
type QCType x y (XIntTF z) # 
type QCType x y (XIntTF z) = XIntTF (QCType x y z)

type QIntTF = XIntTF Qubit Source #

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

type CIntTF = XIntTF Bit Source #

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

type IntTF = XIntTF Bool Source #

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

integer_of_inttf :: IntTF -> Integer Source #

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.

inttf_of_integer :: Integer -> IntTF Source #

Convert an Integer to an IntTF of indeterminate length.

inttf :: Int -> Integer -> IntTF Source #

Convert an Integer to an IntTF of length m.

inttf_length :: IntTF -> Maybe Int Source #

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

inttf_set_length :: Int -> IntTF -> String -> IntTF Source #

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 Source #

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.

show_inttf :: IntTF -> String Source #

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

qulist_of_qinttf_lh :: QIntTF -> [Qubit] Source #

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 Source #

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 Source #

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 Source #

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 Source #

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 Source #

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 :: QDInt -> Circ QDInt Source #

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

decrement :: QDInt -> Circ QDInt Source #

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

Methods

qcdata_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 #

Labelable a String => Labelable (IntMap a) String # 

Methods

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

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

Methods

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