Quipper.Algorithms.BWT.Template

The BWT Oracle, written in a classical, functional manner and automatically transformed to a quantum circuit using Quipper's "build_circuit" mechanism.

Circuit building functions

This section contains an implementation of the oracle as a collection of ordinary functional programs. Each function in this section is decorated with the build_circuit keyword (see Quipper.Internal.CircLifting). Therefore, circuits are automatically generated; for example, the circuit corresponding to the function v_function is automatically built and given the name template_v_function.

General operations on booleans

boollist_xor :: [Bool] -> [Bool] -> [Bool]

Exclusive or operation on bit vectors.

template_boollist_xor :: Circ ([Qubit] -> Circ ([Qubit] -> Circ [Qubit]))

bit_adder :: Bool -> (Bool, Bool, Bool) -> (Bool, Bool)

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

template_bit_adder :: Circ (Qubit -> Circ ((Qubit, Qubit, Qubit) -> Circ (Qubit, Qubit)))

Encoding the BWT oracle on booleans and lists of booleans

parent :: Node -> Node

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

template_parent :: Circ ((a, [Qubit]) -> Circ (a, [Qubit]))

childintree :: Node -> Bool -> Node

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.

template_childintree :: Circ ((a1, [a2]) -> Circ (a2 -> Circ (a1, [a2])))

doweld1 :: Boollist -> Bool -> [Bool] -> [Bool]

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.

template_doweld1 :: Circ ([Qubit] -> Circ (Qubit -> Circ ([Qubit] -> Circ [Qubit])))

doweld0 :: Boollist -> [Bool] -> [Bool]

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

template_doweld0 :: Circ ([Qubit] -> Circ ([Qubit] -> Circ [Qubit]))

weld :: Boollist -> Boollist -> Node -> Bool -> Node

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.

template_weld :: Circ ([Qubit] -> Circ ([Qubit] -> Circ ((Qubit, [Qubit]) -> Circ (Qubit -> Circ (Qubit, [Qubit])))))

child :: Boollist -> Boollist -> Node -> Bool -> Node

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.

template_child :: Circ ([Qubit] -> Circ ([Qubit] -> Circ ((Qubit, [Qubit]) -> Circ (Qubit -> Circ (Qubit, [Qubit])))))

level_parity :: [Bool] -> Bool

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.

template_level_parity :: Circ ([Qubit] -> Circ Qubit)

is_zero :: [Bool] -> Bool

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.

template_is_zero :: Circ ([Qubit] -> Circ Qubit)

is_root :: [Bool] -> Bool

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.

template_is_root :: Circ ([Qubit] -> Circ Qubit)

v_function

Arguments

:: BoolParam

First color bit.

-> BoolParam

Second color bit.

-> Boollist

Vector f from Equation (26).

-> Boollist

Vector g from Equation (27).

-> Node

Entry node a.

-> (Bool, Node)

(True, exit node) or (False, garbage).

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.

template_v_function :: Circ (BoolParam -> Circ (BoolParam -> Circ ([Qubit] -> Circ ([Qubit] -> Circ ((Qubit, [Qubit]) -> Circ (Qubit, (Qubit, [Qubit])))))))

Wrapping it into the Oracle data type

The following functions package the circuit generated by v_function into a data structure of type Oracle.

Colors

type Color = Int

A color is a number between 0 and 3.

colorToBoolParam :: Color -> (BoolParam, BoolParam)

Convert an integer representation of a color into the two-bit representation.

Functions for using the generated oracle

classical_BWT_oracle

Arguments

:: Color

The color.

-> ([Qubit], [Qubit], QNode)

The two welding vectors and a node a.

-> Circ (Qubit, QNode)

Output (r,b).

This is the irreversible classical circuit generated from v_function. This is basically the same as template_v_function, except that excessive uses of Circ are removed from the type, and the inputs and outputs have been reorganized.

reversible_BWT_oracle

Arguments

:: Color

Color.

-> (([Qubit], [Qubit], QNode), (Qubit, QNode))

(f, g, a, r, b).

-> Circ (([Qubit], [Qubit], QNode), (Qubit, QNode))

Output (f, g, a, r, b).

This is the reversible circuit automatically generated from classical_BWT_oracle.

reversible_BWT_oracle_optim

Arguments

:: Color

Color.

-> (([Qubit], [Qubit], QNode), (Qubit, QNode))

(f, g, a, r, b).

-> Circ (([Qubit], [Qubit], QNode), (Qubit, QNode))

Output (f, g, a, r, b).

This is the reversible circuit automatically generated from classical_BWT_oracle, and optimized with peep-hole optimization.

oracle_template :: [Bool] -> [Bool] -> Oracle

The template oracle, packaged into the Oracle abstraction. Note that this circuit is automatically generated from the classical functions above, but is completely unoptimized. This oracle has two parameters, namely the welding vectors f and g.

oracle_template_optim :: [Bool] -> [Bool] -> Oracle

The template oracle, optimized.