A data structure to hold an oracle. The binary welded tree algorithm is parametric on an oracle. An oracle encodes a graph, and provides the following information: the tree depth n (in the above example: 3), the label length m (in bits; 5 in the above example), the number of edge colors k, the entrance label ENTRANCE, and for each color 0 ≤ c < k, a reversible circuit ORACLEsub /c/. On basis vectors, this circuit encodes the edge information in the following sense:

ORACLEc(a, b, r) = (a, b ⊕ vc(a), r ⊕ fc(a)),

where fsub /c/ is 1 if the node a is connected to an edge of color c, and 0 otherwise; and vsub /c/ is the node label connected to node a along an edge of color c (if any), and arbitrary otherwise.

Not all available node labels need to be used (for example, 0 and 16 are unused in the graph in the above illustration).

The main loop of the binary welded tree algorithm.

qrwbwt oracle s dt: Do a quantum random walk on the binary welded tree given by the oracle oracle, for s times steps of length dt. Returns a bit list corresponding to the computed exit node label.

timestep (a, b, r, dt, m): Perform a single time step dt of the quantum walk. This is done by iterating through each of the available edge colors, and performing a diffusion step for each color. Here, a is an m-qubit registers holding (a superposition of) the current node label. b is an m-qubit ancilla register, and r is an ancilla qubit. Both b and r are expected to be initialized to |0〉 by the caller, and will be returned in state |0〉.

The top-level oracle circuit. The arguments are of the form (a, b, r, color, f, g, n), where a, b are quantum registers of length n+2, color is a boolean register of length 2, and f and g are boolean registers of length n.

Input a node label a of length at least n+1. Negate both root and even if a is a root node.

Input a node label a of length at least n+1. Negate even if the node a occurs at an even height in the tree.

Input a node label a of length at least 1, and flags root and even describing whether a is a root and at an even level, respectively. Negate isparent if a has a parent of color color in the tree.

The qubit ismatch is an ancilla, and really is either 0 or 1. They are jointly used to control uncomputation, so that the following sequence will compute and then uncompute testIsParent:

ismatch <- qinit 0
testIsParent (a, root, even, isparent, color, n, 1, ismatch)
testIsParent (a, root, even, isparent, color, n, 0, ismatch)
qterm 0 ismatch

Consider a node a, and negate ischild if a has a child node of color color. Also set direction to indicate whether it is a "left" or "right" child. Here, color is a boolean register of length 2, representing a color. This function is self-inverse.

Input a node label a of length at least n+2, and a flag isparent that has been initialized accordingly. Also input a register b of length at least n+2, initialized to |0〉. If isparent is set, set b to the node label of the parent of a. This is self-inverse.

Similar to setParent, but set b to the node label of the indicated child of a. Here a and b are quantum registers of length at least n+2, and f and g are boolean registers of length n.

A special case of setChild, where the child is inside the same binary tree (i.e., not via the welding).

A special case of setChild, where the child is in the opposite binary tree, i.e., we follow one of the welding edges.

Input a node label a, and a register b initialized to |0〉. If weldctrl is set, set b to the node connected to a by the welding function f. This is self-inverse. Here, a and b are quantum registers of length at least n+2, and f is a boolean register of length n.

Input a node label a, and a register b initialized to |0〉. If weldctrl is set, set b to the node connected to a by the welding function g. This is self-inverse. Here, a and b are quantum registers of length at least n+2, and g is a boolean register of length n.

This function implements integer addition. Input a quantum register input and a boolean register num, representing integers, and a quantum register out initialized to |0〉. If control is set, set out to input + num, otherwise do nothing. Here input and out are quantum registers of length at least n, num is a boolean register of length n.

A helper function for clearing the scratch space used by cAddNum.

Like cAddNum, except subtract instead of adding.

A helper function for clearing the scratch space used by cSubNum.

This function inputs two welding functions f and g, and returns the oracle defined by the preceding functions.

We call this the "orthodox" oracle, because the implementation follows its specification very closely. For example, it uses a very "imperative" programming style. For alternative implementations of this and other oracles, see the modules Quipper.Algorithms.BWT.Alternative and Quipper.Algorithms.BWT.Template.

Output the circuit for the quantum walk and a binary welded tree, for the given Oracle in the specified Format and using the specified GateBase. Use s time steps of length dt.

Output the circuit for the given Oracle and the given color (specified as an Int). Use the specified output Format and GateBase.