The Quipper System

Algorithms.TF.Alternatives

Description

This module contains various supplementary functions related to the Triangle Finding algorithm: alternatives to and/or generalizations of the various routines in Oracle and QWTFP.

Synopsis

# Arithmetic functions

Increment a QIntTF (i.e., little-endian, mod 2l – 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 2l ; 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 2l (in which case the other arithmetic routines are unsound, since they may break the precondition).

Decrement a QIntTF in place.

An alternative to o5_MOD3 for reducing mod-3, conceptually simpler and not size-limited: uses the fact that 2-bit QIntTFs 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. indexed_fetch i m q performs the operation q ⊕= m[i].

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

Efficient qRAM "store" operation. indexed_store i m q performs the operation m[i] ⊕= q.

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

Efficient qRAM "swap" operation. indexed_swap i m q swaps q and m[i].

Our efficient qRAM implementation wrapped in a Qram object.