The Quipper System

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

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

Algorithm O-2. Convert a QNode into a freshly assigned QIntTF,

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.

Algorithm O-4. Compute 17th power of a 31-bit QIntTF x, into a freshly 31-bit QIntTF.

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

A subroutine factored out of o4_POW17.

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.

Algorithm O-6. Subtract an integer parameter from a QIntTF. Return the result as a second, freshly assigned QIntTF.

Algorithm O-7. Add two QIntTFs. Return the result as a third, freshly assigned QIntTF.

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.

Algorithm O-8. Multiply two QIntTFs; return the result as a third, freshly assigned QIntTF.

Double a QIntTF in place.

A subroutine factored out of o8_MUL.

# Blackbox oracle

A black-box oracle for testing. Produces a labelled black-box gate in place of the actual oracle circuit.