| Safe Haskell | None |
|---|---|
| Language | Haskell98 |
Quipper.Algorithms.TF.Oracle
Contents
Description
This module provides implementations of an oracle for the Triangle Finding Algorithm.
This oracle injects the graph G into the space {0, 1, . . . , 2l − 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.
Synopsis
- 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.