The Quipper System

Safe HaskellNone

Algorithms.BWT.Main

Contents

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

data WhatToShow Source #

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.

data OracleSelect Source #

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.

data Options Source #

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

Constructors

Options 

Fields

Instances

defaultOptions :: Options Source #

The default options.

options :: [OptDescr (Options -> IO Options)] Source #

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

oracle_enum :: [(String, OracleSelect)] Source #

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.

oracle_of_options :: Options -> Oracle Source #

Compute the appropriate Oracle for the given options.