| Safe Haskell | None |
|---|
Quipper.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:
- Quipper.Algorithms.BWT.Main: Command line interface.
- Quipper.Algorithms.BWT.Definitions: Some general-purpose definitions.
- Quipper.Algorithms.BWT.BWT: The implementation of the main Binary Welded Tree algorithm and oracle, using a more-or-less imperative programming style.
- Quipper.Algorithms.BWT.Alternative: Alternate implementations of the main algorithm and various oracles, using a more functional programming style.
- Quipper.Algorithms.BWT.Template: Another oracle implementation, using Quipper's "build_circuit" feature to automatically extract a quantum circuit from a classical functional program.
- Quipper.Algorithms.BWT.Simulate: Functions for simulating, testing, and debugging oracles.
Synopsis
- data WhatToShow
- data OracleSelect
- data Options = Options {}
- defaultOptions :: Options
- options :: [OptDescr (Options -> IO Options)]
- oracle_enum :: [(String, OracleSelect)]
- dopts :: [String] -> IO Options
- usage :: IO ()
- main :: IO ()
- oracle_of_options :: Options -> Oracle
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. |
Instances
| Show WhatToShow # | |
Defined in Quipper.Algorithms.BWT.Main Methods showsPrec :: Int -> WhatToShow -> ShowS # show :: WhatToShow -> String # showList :: [WhatToShow] -> ShowS # | |
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. |
Instances
| Show OracleSelect # | |
Defined in Quipper.Algorithms.BWT.Main Methods showsPrec :: Int -> OracleSelect -> ShowS # show :: OracleSelect -> String # showList :: [OracleSelect] -> ShowS # | |
A data type to hold values set by command line options.
Constructors
| Options | |
Fields
| |
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.