Safe Haskell | None |
---|

Alternative implementations for the binary welded tree algorithm. The purpose of these is to experiment with and potentially illustrate a more functional programming style.

- data Oracle = Oracle {}
- convert_oracle :: Oracle -> Oracle
- qrwbwt :: Oracle -> Timestep -> Int -> Circ Bitlist
- hamiltonian :: Timestep -> Oracle -> Qulist -> Circ ()
- time_step :: Timestep -> (Qulist, Qulist, Qubit) -> Circ ()
- basischange :: (Qulist, Qulist, Qubit) -> Circ ()
- compute_steps :: Int -> Double -> Double -> Int
- oracle_blackbox :: Int -> Oracle
- oracle_simple :: Oracle
- type Node = (Bool, [Bool])
- node_of_int :: Int -> Int -> Node
- int_of_node :: Node -> Int
- node_of_boollist :: [Bool] -> Node
- boollist_of_node :: Node -> [Bool]
- parent :: Node -> Node
- childintree :: Node -> Bool -> Node
- bit_adder :: Bool -> (Bool, Bool, Bool) -> (Bool, Bool)
- doweld1 :: Boollist -> Bool -> [Bool] -> [Bool]
- doweld0 :: Boollist -> [Bool] -> [Bool]
- weld :: Boollist -> Boollist -> Node -> Bool -> Node
- child :: Boollist -> Boollist -> Node -> Bool -> Node
- level_parity :: [Bool] -> Bool
- is_zero :: [Bool] -> Bool
- is_root :: [Bool] -> Bool
- v_function :: Boollist -> Boollist -> Int -> Node -> Maybe Node
- type CNode = (Bit, Bitlist)
- type QNode = (Qubit, [Qubit])
- qnode_of_qulist :: Qulist -> QNode
- cnode_of_bitlist :: Bitlist -> CNode
- cboollist_xor :: Bitlist -> Bitlist -> Circ Bitlist
- cparent :: CNode -> Circ CNode
- cchildintree :: CNode -> Bit -> Circ CNode
- cbit_adder :: Bit -> (Bit, Bit, Bit) -> Circ (Bit, Bit)
- cdoweld1 :: Boollist -> Bit -> Bitlist -> Circ Bitlist
- cdoweld0 :: Boollist -> Bitlist -> Circ Bitlist
- cweld :: Boollist -> Boollist -> CNode -> Bit -> Circ CNode
- cchild :: Boollist -> Boollist -> CNode -> Bit -> Circ CNode
- clevel_parity :: Bitlist -> Circ Bit
- cis_zero :: Bitlist -> Circ Bit
- cis_root :: Bitlist -> Circ Bit
- cv_function :: Boollist -> Boollist -> Int -> CNode -> Circ (CNode, Bit)
- oracle_classical :: Boollist -> Boollist -> Oracle
- main_edges1 :: IO ()
- circfun :: Boollist -> Boollist -> Int -> Node -> (Node, Bool)
- main_edges2 :: IO ()
- main_oraclec :: Format -> Oracle -> Int -> IO ()
- main_oracle2 :: Format -> Oracle -> Int -> IO ()
- main_oracle3 :: Format -> Oracle -> Int -> IO ()
- main_qrwbwt :: IO ()

# Oracle abstraction

convert_oracle :: Oracle -> Oracle Source #

Convert a Alternative.`Oracle`

into a BWT.`Oracle`

.

# Top-level algorithm

qrwbwt :: Oracle -> Timestep -> Int -> Circ Bitlist Source #

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

ORACLE_{c}(a, 0, 0) = (a, v_{c}(a), f_{c}(a)),

rather than the more general property

ORACLE_{c}(a, b, r) = (a, b ⊕ v_{c}(a), r ⊕ f_{c}(a)).

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

hamiltonian :: Timestep -> Oracle -> Qulist -> Circ () Source #

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

time_step :: Timestep -> (Qulist, Qulist, Qubit) -> Circ () Source #

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

basischange :: (Qulist, Qulist, Qubit) -> Circ () Source #

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_steps :: Int -> Double -> Double -> Int Source #

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*^{4}/2ε.
Here, for simplicity, we just use *t* = ⌊*n*^{4}/2ε⌋. Also note
that this function is for information only, as it is not actually
used. Users should specify *s* directly.

# Oracle implementations

## Blackbox oracle

oracle_blackbox :: Int -> Oracle Source #

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

## A simple "exponential" oracle.

oracle_simple :: Oracle Source #

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.

## Alternate implementations of the "orthodox" oracle

### Classical implementation

In this section, we first implement the oracle function
*v _{c}(a)* as a classical boolean function. This implementation
is just for reference, and attempts to be neither efficient nor
quantum. It can, however, be used as a specification to test the
actual quantum oracles against.

Both the classical circuit implementation (below) and the Template Haskell implementation (in the module BWT.Template) were derived from this.

We start with several auxiliary functions.

int_of_node :: Node -> Int Source #

Convert nodes to integers, mainly for testing.

node_of_boollist :: [Bool] -> Node Source #

Convert a bit vector to a node.

boollist_of_node :: Node -> [Bool] Source #

Convert a node to a bit vector.

parent :: Node -> Node Source #

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

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

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.

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

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

level_parity :: [Bool] -> Bool Source #

is_root :: [Bool] -> Bool Source #

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 :: Boollist -> Boollist -> Int -> Node -> Maybe Node Source #

: returns `v_function`

f g c a*v*sub /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.

### Auxiliary functions

### Classical circuit implementation

We now implement the oracle function v_{c}(a) as a classical
circuit, with *c* as a parameter. We don't try to be clever or
efficient yet. The implementation follows the "classical
implementation" above, but must be reformulated due to the need to
work within the `Circ`

monad.

cparent :: CNode -> Circ CNode Source #

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

cdoweld1 :: Boollist -> Bit -> Bitlist -> Circ Bitlist Source #

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.

cdoweld0 :: Boollist -> Bitlist -> Circ Bitlist Source #

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

cis_root :: Bitlist -> Circ Bit Source #

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 :: Boollist -> Boollist -> Int -> CNode -> Circ (CNode, Bit) Source #

: returns `cv_function`

f g c a*v*sub /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

as an indexed union, and
specifically as `Maybe`

`CNode`

`(`

. When `CNode`

,`Bit`

)*Bit*=`True`

, the value of
`CNode`

is undefined (doesn't matter); in particular, this value
may contain garbage.

### Oracle abstraction

oracle_classical :: Boollist -> Boollist -> Oracle Source #

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.

# Testing functions

main_edges1 :: IO () Source #

Output the list of colored edges as computed by the classical
`v_function`

, for some arbitrary choice of *f* and *g* and *n*=3.

circfun :: Boollist -> Boollist -> Int -> Node -> (Node, Bool) Source #

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 `(`

instead of `Bool`

, `Node`

)

, so
that we can see any garbage that is output in case of an invalid
node.`Maybe`

`Node`

main_edges2 :: IO () Source #

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.

main_oraclec :: Format -> Oracle -> Int -> IO () Source #

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

main_oracle2 :: Format -> Oracle -> Int -> IO () Source #

Like `main_oraclec`

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

main_oracle3 :: Format -> Oracle -> Int -> IO () Source #

Like `main_oraclec`

, except it makes the classical circuit
reversible first.

main_qrwbwt :: IO () Source #

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.