Safe Haskell | None |
---|

This module provides implementations of an oracle for the Triangle Finding Algorithm.

This oracle injects the graph *G* into the space
{0, 1, . . . , 2*l* − 1} of *l*-bit integers, and each oracle
call requires the extensive use of modular arithmetic.

The circuits produced by running this "orthodox" oracle are very big. We therefore also provide a "blackbox" oracle, which is simply a placeholder for an actual oracle call, to replace the orthodox oracle when running subroutines and for resource estimation. The oracle circuit is the same every time it is used, so for resource estimation purposes, it only needs to be generated once, rather than inlined at every use site.

- o1_ORACLE :: Int -> QNode -> QNode -> Qubit -> Circ (QNode, QNode, Qubit)
- o1_ORACLE_aux :: Int -> Int -> (QNode, QNode) -> Circ ((QNode, QNode), (QIntTF, QIntTF, QIntTF, QIntTF, QIntTF, QIntTF), (Qubit, Qubit, Qubit, Qubit, Qubit, Qubit, Qubit))
- o2_ConvertNode :: Int -> QNode -> Int -> Circ (QNode, QIntTF)
- o3_TestEqual :: QIntTF -> QIntTF -> Circ (QIntTF, QIntTF, Qubit)
- o4_POW17 :: QIntTF -> Circ (QIntTF, QIntTF)
- square :: QIntTF -> Circ (QIntTF, QIntTF)
- o5_MOD3 :: QIntTF -> Circ (QIntTF, QIntTF)
- o6_SUB :: QIntTF -> Int -> Circ (QIntTF, QIntTF)
- o7_ADD :: QIntTF -> QIntTF -> Circ (QIntTF, QIntTF, QIntTF)
- o7_ADD_controlled :: (ControlSource ctrl, Labelable ctrl String) => ctrl -> QIntTF -> QIntTF -> Circ (QIntTF, QIntTF, QIntTF)
- o8_MUL :: QIntTF -> QIntTF -> Circ (QIntTF, QIntTF, QIntTF)
- double_TF :: QIntTF -> Circ QIntTF
- placeholder_oracle :: QNode -> QNode -> Qubit -> Circ Qubit

# Orthodox oracle

o1_ORACLE :: Int -> QNode -> QNode -> Qubit -> Circ (QNode, QNode, Qubit) Source #

Algorithm O-1. The two `QNode`

inputs *u* and
*v* are assumed to be of equal length.

o1_ORACLE_aux :: Int -> Int -> (QNode, QNode) -> Circ ((QNode, QNode), (QIntTF, QIntTF, QIntTF, QIntTF, QIntTF, QIntTF), (Qubit, Qubit, Qubit, Qubit, Qubit, Qubit, Qubit)) Source #

Compute the various auxiliary data for `o1_ORACLE`

.

o3_TestEqual :: QIntTF -> QIntTF -> Circ (QIntTF, QIntTF, Qubit) Source #

Algorithm O-3. Compare if two QIntTF’s are equal; return the result in a fresh Qubit.

This function is in general iffy: 00…00 and 11…11 do *not* test as equal, as they should.
However, that case does not arise in the oracle: on the one hand, both 00…00 and 11…11
are literal fixed points of `o4_POW17`

, and on the other, `o5_MOD3`

never outputs 00.

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

Algorithm O-4. Compute 17th power of a 31-bit `QIntTF`

*x*, into a
freshly 31-bit *QIntTF*.

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

Map a QIntTF *x* to (*x*,*x*^2).

A subroutine factored out of

.`o4_POW17`

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

Algorithm O-5. Compute residue modulo 3 of the lower-order bits of a
`QIntTF`

, into a fresh 2-bit `QIntTF`

.

This algorithm is size-limited — works for up to 31-bit integers, but not beyond.

This also currently is mismatched with our specification of QIntTF, since it produces output in the range 1–3, rather than 0–2. However, output of this algorithm is only used via '03_TestEqual', so this is not a problem in practice.

o7_ADD_controlled :: (ControlSource ctrl, Labelable ctrl String) => ctrl -> QIntTF -> QIntTF -> Circ (QIntTF, QIntTF, QIntTF) Source #

Controlled version of `o7_ADD`

. Returns either a copy of the first
input (if controls are “off”) or the sum of the inputs
(if controls are “on”).

We make this version explicitly, rather than just using `controlled`

,
because the controls only need to be applied to a very few selected
gates in the routine.