The Quipper System

Algorithms.BWT.Main

Description

Authors: Peter Selinger, Benoît Valiron

An implementation of the Binary Welded Tree algorithm. This algorithm inputs an oracle encoding a graph of the following form:

The graph consists of two binary trees whose leaves are connected by two permutations as shown in the above illustration. Except for the roots of the two trees, all nodes have degree 3. The edges of the graph are colored with 4 different colors. The objective of the algorithm is to find the exit node (17 in the above illustration), given the entrance node (1 in the above illustration). This is done by a Trotterized quantum walk on the graph.

The algorithm is described in:

• A. M. Childs, R. Cleve, E. Deotto, E. Farhi, S. Gutmann, and D. A. Spielman. "Exponential algorithmic speedup by a quantum walk." Proceedings of the 35th Annual ACM Symposium on Theory of Computing, pp. 59–68, 2003. See also http://arxiv.org/abs/quant-ph/0209131.

The present implementation is based on detailed algorithm and oracle specifications that were provided to us by the IARPA QCS program and written by Travis Humble.

Modules:

Synopsis

# Command line interface

This module provides a command line interface for the Binary Welded Tree algorithm. This allows the user, for example, to plug in different oracles, show different parts of the circuit, select a gate base, simulate, select parameters such as n and s, and select different output formats.

# Option processing

An enumeration type for determining what the main function should do.

Constructors

 Circuit Show the whole circuit. Oracle Show only the oracle. Graph Show colored edges computed from oracle simulation. OracleC Show the "classical" oracle as a classical circuit. Simulate Run simulations of individual circuit fragments.

Instances

 # MethodsshowList :: [WhatToShow] -> ShowS #

An enumeration type for selecting an oracle.

Constructors

 Orthodox The "orthodox" oracle. Simple The "simple" oracle. Blackbox A blackbox oracle. Classical An oracle generated from classical program. Template An oracle automatically generated using Template Haskell. TemplateOptim An oracle automatically generated using Template Haskell, with peep-hole optimization.

Instances

 # MethodsshowList :: [OracleSelect] -> ShowS #

data Options Source #

A data type to hold values set by command line options.

Constructors

 Options Fieldswhat :: WhatToShowWhat kind of thing to output.format :: FormatThe output format.gatebase :: GateBaseWhat kind of gates to decompose into.oracle :: OracleSelectWhich kind of oracle to use.n :: IntThe tree height.c :: IntThe color to use with --oracle.s :: IntThe parameter s to use.dt :: TimestepThe parameter dt to use.

Instances

 # MethodsshowList :: [Options] -> ShowS #

The default options.

The list of command line options, in the format required by getOpt.

An enumeration of available oracles and their names.

dopts :: [String] -> IO Options Source #

Process argv-style command line options into an Options structure.

usage :: IO () Source #

Print usage message to stdout.

# The BWT main function

main :: IO () Source #

Main function: read options, then execute the appropriate task.

Compute the appropriate Oracle for the given options.