Safe Haskell | None |
---|

- increment_TF :: QIntTF -> Circ QIntTF
- decrement_TF :: QIntTF -> Circ QIntTF
- o5_MOD3_alt :: QIntTF -> Circ (QIntTF, QIntTF)
- indexed_fetch :: QData qa => QDInt -> IntMap qa -> qa -> Circ (QDInt, IntMap qa, qa)
- indexed_store :: QData qa => QDInt -> IntMap qa -> qa -> Circ (QDInt, IntMap qa, qa)
- indexed_swap :: QData qa => QDInt -> IntMap qa -> qa -> Circ (QDInt, IntMap qa, qa)
- alt_qram :: Qram

# Arithmetic functions

increment_TF :: QIntTF -> Circ QIntTF Source #

Increment a `QIntTF`

(i.e., little-endian, mod 2^{l} – 1)
in place.

This and `decrement_TF`

assume as precondition that the input is never
11…11, and preserve this condition, by fixing 11…11. This means these
are *not* correct if `IntTF`

is treated as a formal quotient of
2^{l} ; with that approach, incrementing/decrementing in place
cannot be a quantum operation (since it must map 00…00 and 11…11 both
to 00…01, so would have nonzero kernel). These are however correct if
`IntTF`

is considered as a formal *subspace* of 2^{l} (in which
case the other arithmetic routines are unsound, since they may break
the precondition).

o5_MOD3_alt :: QIntTF -> Circ (QIntTF, QIntTF) Source #

An alternative to `o5_MOD3`

for reducing mod-3, conceptually
simpler and not size-limited: uses the fact that 2-bit `QIntTF`

s
give us true mod-3 arithmetic.

Has same complexity *O(l)* as `o5_MOD3`

, with (probably) a
slightly higher leading coefficient, due to difference in size
between `increment_TF`

and `increment_little`

.

# Efficient qRAM

We provide an efficient qRAM implementation in QuipperLib.Qram.
The following turns it into a `Qram`

object for the Triangle
Finding algorithm.

indexed_fetch :: QData qa => QDInt -> IntMap qa -> qa -> Circ (QDInt, IntMap qa, qa) Source #

Efficient qRAM "fetch" operation.

performs the operation `indexed_fetch`

*i* *m* *q**q* ⊕= *m*[*i*].

indexed_store :: QData qa => QDInt -> IntMap qa -> qa -> Circ (QDInt, IntMap qa, qa) Source #

Efficient qRAM "store" operation.

performs the operation `indexed_store`

*i* *m* *q**m*[*i*] ⊕= *q*.

indexed_swap :: QData qa => QDInt -> IntMap qa -> qa -> Circ (QDInt, IntMap qa, qa) Source #

Efficient qRAM "swap" operation.

swaps `indexed_swap`

*i* *m* *q**q* and *m*[*i*].