This is a version of Oracle that uses Qulist instead of Qureg. An oracle provides the following information: the tree depth n, the label length m, the number of edge colors k, the entrance label ENTRANCE, and for each color 0 ≤ c < k, a reversible circuit ORACLE_c(a,b,r).

Convert a Alternative.Oracle into a BWT.Oracle.

Do a quantum random walk on the binary welded tree given by the oracle, for s times steps of length dt. Return a bit list corresponding to the probable exit label. This is a more functional implementation of qrwbwt from the module BWT.

Note: This implementation does not rely on the oracle being self-inverse, and therefore only requires that

ORACLEc(a, 0, 0) = (a, vc(a), fc(a)), 

rather than the more general property

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

This gives us the freedom to build more efficient oracles, where appropriate.

Apply one round of the Hamiltonian for time step dt to a.

Apply the diffusion step to (a,b,r). Here a and b must be of equal length.

Apply the basis change from Figure 3 of \[Childs et al.\] to a, b, and h. Here a and b must be of equal length.

Compute the required number of iterations as a function of ε and dt.

Inputs: n is the tree depth, ε is the desired precision, dt is the simulation time step. Intermediate values: t is the simulation time. Output: s, the upper bound on the number of simulation time steps.

Note: \[Childs et al\] specifies that t should be chosen uniformly at random within the interval 0 < t ≤ n⁴/2ε. Here, for simplicity, we just use t = ⌊n⁴/2ε⌋. Also note that this function is for information only, as it is not actually used. Users should specify s directly.

A blackbox oracle for testing. This just produces a labelled box in place of the actual oracle circuit. The argument is the tree height.

This oracle, which works only for the fixed tree height 3, works by explicitly listing all the edges. It serves only to illustrate how the edge information is encoded. Listing all edges explicitly obviously would not scale well to larger graphs.

The type of nodes: a pair of a tree bit and a node address.

Convert integers to nodes, mainly for testing.

Convert nodes to integers, mainly for testing.

Convert a bit vector to a node.

Convert a node to a bit vector.

Input a node a and return the parent of a. We assume that a is not a root or invalid.

Input a node a and return the left or right child of a (depending on whether the childbit is False or True, respectively). Assumes that a is not a leaf.

bit_adder False is a one-bit adder, and bit_adder True is a one-bit subtracter (i.e., add the 2's complement of y).

Input an n+1-bit leaf node a:aa (without the tree bit; a is the highest bit and aa is the remaining n bits) and a sign s (where True = negative, False = positive). Return a:(aa + s * f). The first input is the n-bit welding vector f (a parameter to the oracle). Note that f is a parameter and s, aa are inputs.

Input an n+1-bit leaf node a:aa (without the tree bit), and return a:(aa ⊕ g). The first input is the n-bit welding vector g (a parameter to the oracle).

Input a leaf node a and return the left or right weld of a in the other tree (depending on whether the weldbit is False or True). Assumes that a is a leaf.

Input a node a and return the left or right child of a (depending on whether the childbit is False or True. This works for leaf and non-leaf nodes.

Input a node address (without the tree bit) and return the parity of the node level expressed as a boolean either False or True. Leaves have parity False, and other levels have alternating parities. In other words: count the number of leading zeros modulo 2.

Input a node address (without the tree bit) and return True iff the node address is invalid. In other words, return True iff the list consists of all 0's.

Input a node address (without the tree bit) and return True iff the node is a root or invalid. In other words, check whether all digits but the last are 0's.

v_function f g c a: returns vsub /c/, the label of the node connected to a by an edge of color c, or Nothing if there is no such node. The parameters f and g encode the welding functions, and are lists of length n. c is a color in the range 0..3, and a is an (n+2)-bit node label.

The type of nodes: a pair of a tree bit and a node address.

Like CNode, but uses qubits instead of classical bits.

Convert a Qulist to a QNode.

Convert a Bitlist to a CNode.

Exclusive or operation on bit vectors.

Input a node a and return the parent of a. We assume that a is not a root or invalid.

Input a node a and return the left or right child of a (depending on whether the childbit is False or True, respectively). Assumes that a is not a leaf.

bit_adder False is a one-bit adder, and bit_adder True is a one-bit subtracter (i.e., add the 2's complement of y).

Input an n+1-bit leaf node a:aa (without the tree bit; a is the highest bit and aa is the remaining n bits) and a sign s (where True = negative, False = positive). Return a:(aa + s * f). The first input is the n-bit welding vector f (a parameter to the oracle). Note that f is a parameter and s, aa are inputs.

Input an n+1-bit leaf node a:aa (without the tree bit), and return a:(aa ⊕ g). The first input is the n-bit welding vector g (a parameter to the oracle).

Input a leaf node a and return the left or right weld of a in the other tree (depending on whether the weldbit is False or True). Assumes that a is a leaf.

Input a node a and return the left or right child of a (depending on whether the childbit is False or True. This works for leaf and non-leaf nodes.

Input a node address (without the tree bit) and return the parity of the node level expressed as a boolean either False or True. Leaves have parity False, and other levels have alternating parities. In other words: count the number of leading zeros modulo 2.

Input a node address (without the tree bit) and return True iff the node address is invalid. In other words, return True iff the list consists of all 0's.

Input a node address (without the tree bit) and return True iff the node is a root or invalid. In other words, check whether all digits but the last are 0's.

cv_function f g c a: returns vsub /c/, the label of the node connected to a by an edge of color c, or Nothing if there is no such node. The parameters f and g encode the welding functions, and are lists of length n. c is a color in the range 0..3, and a is an (n+2)-bit node label.

We currently implement Maybe CNode as an indexed union, and specifically as (CNode,Bit). When Bit=True, the value of CNode is undefined (doesn't matter); in particular, this value may contain garbage.

The classical oracle implementation, packaged into the Oracle abstraction. This oracle has two parameters, namely the welding vectors f and g. Note: this oracle has not been optimized whatsoever.

Output the list of colored edges as computed by the classical v_function, for some arbitrary choice of f and g and n=3.

For debugging: circfun is similar to v_function, except it works by calling cv_function to assemble the circuit, then simulates it. This is for testing whether the assembled circuit is correct. Returns (Bool, Node) instead of Maybe Node, so that we can see any garbage that is output in case of an invalid node.

Output the list of colored edges as computed by simulating the circuit cv_function, for some arbitrary choice of f and g and n=3. This is like main_edges1, except it actually assembles and simulates the classical circuit.

Graphically output the classical oracle circuit for color c, using n from the oracle data structure, and for some arbitrary f and g.

Like main_oraclec, except it rewrites the classical circuit in terms of Toffoli gates.

Like main_oraclec, except it makes the classical circuit reversible first.

Output the top-level circuit for the binary welded tree algorithm with the classical oracle, using some arbitrary welding vectors f and g, and s=1.