Safe Haskell | None |
---|

This module provides global definitions for the Triangle Finding Algorithm.

- data Qram = Qram {}
- type CNode = [Bit]
- type QNode = [Qubit]
- type QWTFP_spec = (Int, Int, QNode -> QNode -> Qubit -> Circ Qubit, Qram)
- data XIntTF x = XIntTF (XInt x)
- type QIntTF = XIntTF Qubit
- type CIntTF = XIntTF Bit
- type IntTF = XIntTF Bool
- integer_of_inttf :: IntTF -> Integer
- inttf_of_integer :: Integer -> IntTF
- inttf :: Int -> Integer -> IntTF
- inttf_length :: IntTF -> Maybe Int
- inttf_set_length :: Int -> IntTF -> String -> IntTF
- inttf_promote :: IntTF -> XIntTF x -> String -> IntTF
- show_inttf :: IntTF -> String
- qulist_of_qinttf_lh :: QIntTF -> [Qubit]
- qinttf_of_qulist_lh :: [Qubit] -> QIntTF
- qinttf_shape :: Int -> QIntTF
- xinttf_of_xint :: XInt x -> XIntTF x
- xint_of_xinttf :: XIntTF x -> XInt x
- xint_with_promote :: XIntTF y -> IntTF -> IntM
- phaseFlipIf :: ControlSource ctrl => ctrl -> Circ ()
- phaseFlipUnless :: ControlSource ctrl => ctrl -> Circ ()
- qor :: Qubit -> [(Qubit, Bool)] -> Circ Qubit
- increment :: QDInt -> Circ QDInt
- decrement :: QDInt -> Circ QDInt
- increment_big :: [Qubit] -> Circ [Qubit]
- decrement_big :: [Qubit] -> Circ [Qubit]
- increment_little :: [Qubit] -> Circ [Qubit]
- decrement_little :: [Qubit] -> Circ [Qubit]
- choose :: Integral a => a -> a -> a
- addKeys :: IntMap a -> IntMap (Key, a)
- mapWithKeyM :: Monad m => (Key -> a -> m b) -> IntMap a -> m (IntMap b)
- mapWithKeyM_ :: Monad m => (Key -> a -> m b) -> IntMap a -> m ()
- intMap_replicate :: Int -> a -> IntMap a
- (!) :: IntMap a -> Key -> a

# Qram abstraction

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`

.

# Types for the Triangle Finding Algorithm

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=**2*^{n}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

will compare the bitwise representation
to 0, and not the logical quotient.*q* .==. 0

type QIntTF = XIntTF Qubit Source #

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

type CIntTF = XIntTF Bit Source #

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

## Operations for IntTF

integer_of_inttf :: IntTF -> Integer Source #

inttf_of_integer :: Integer -> IntTF Source #

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

show_inttf :: IntTF -> String Source #

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

xint_of_xinttf :: XIntTF x -> XInt x Source #

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_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^{ℓ}.

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

Analogous to `mapM_`

, but allows the function to use the key.

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

Convenient syntax for accessing elements of an `IntMap`

. Left associative, and binds very strongly, like '(!!)'.