Safe Haskell  None 

Authors: Peter LeFanu Lumsdaine, Neil Julien Ross
An implementation of the Triangle Finding Algorithm. The Triangle Finding Problem is given by an undirected dense simple graph G containing exactly one triangle ∆. The graph is given by an oracle function f , such that, for any two nodes v, w of G, f(v,w)=1 if (v,w) is an edge of G and f(v,w)=0 otherwise. To solve such an instance of the problem is to find the set of vertices {e_{1} , e_{2} , e_{3}} forming ∆ by querying f.
The algorithm works by performing a Groverbased quantum walk on a larger graph H, called the Hamming graph associated to G. It is designed to find ∆ with high probability. The algorithm is parametric on an oracle defining the graph G. In our implementation, the oracle is a changeable part, but we have also implemented a particular predefined oracle.
The algorithm is described in:
 A. Childs and R. Kothari. "Quantum query complexity of minorclosed graph properties." In Proceedings of the 28th Symposium on Theoretical Aspects of Computer Science, pages 661–672, 2011.
 F. Magniez, M. Santha, and M. Szegedy. "Quantum algorithms for the triangle problem." In Proceedings of the 16th Annual ACMSIAM Symposium on Discrete Algorithms, pages 1109–1117, 2005.
The present implementation is based on detailed algorithm and oracle specifications that were provided to us by the IARPA QCS program and written by Richard Wisniewski.
Modules:
 Algorithms.TF.Main: Command line interface.
 Algorithms.TF.Definitions: Some general purpose definitions.
 Algorithms.TF.QWTFP: The implementation of the main Triangle Finding algorithm.
 Algorithms.TF.Oracle: The implementation of the oracle for the Triangle Finding algorithm.
 Algorithms.TF.Alternatives: Some alternative implementations of some of the subroutines.
 Algorithms.TF.Simulate: Functions for simulating, testing, and debugging oracles.
 data WhatToShow
 data OracleSelect
 data QRamSelect
 data Subroutine
 data Options = Options {
 what :: WhatToShow
 s :: Subroutine
 format :: Format
 gatebase :: GateBase
 oracle :: OracleSelect
 qram :: QRamSelect
 l :: Int
 n :: Int
 r :: Int
 defaultOptions :: Options
 options :: [OptDescr (Options > IO Options)]
 oracle_enum :: [(String, OracleSelect)]
 subroutine_enum :: [(String, Subroutine)]
 dopts :: [String] > IO Options
 usage :: IO ()
 main :: IO ()
 spec_of_options :: Options > QWTFP_spec
 qram_select :: QRamSelect > Qram
Documentation
This module provides a command line interface for the Triangle Finding Algorithm. This allows the user, for example, to plug in different oracles, show different parts of the circuit, select a gate base, simulate, and select various parameters.
 Example invocations:
./tf
Default options: the full a1_QWTFP
circuit, with
(l,n,r) = (4,3,2), and a blackbox oracle.
./tf oracle o Orthodox l 3 n 2 r 2
A manageable size to inspect the orthodox oracle.
./tf s mult l 4
The multiplier, for 4bit integers mod 15.
./tf help
Print detailed usage info (accepted options, etc.).
 Parameters:
l: the length of integers used in the oracle. (Default value: 4.)
n: the size of nodes in the graph. (Default value: 3.)
r: log_{2} of the tuple size of the Hamming graph. (Default value: 2.)
Option processing
data WhatToShow Source #
An enumeration type for determining what the main function should do.
data OracleSelect Source #
An enumeration type for selecting an oracle.
data QRamSelect Source #
A datatype for selecting a qRAM implementation.
Standard_QRam  The default qRAM. 
Alt_QRam  A slightly more efficient implementation. 
data Subroutine Source #
An enumeration type for selecting a subroutine.
A2  Algorithm 2: Zero. 
A3  Algorithm 3: Initialize. 
A4  Algorithm 4: Hadamard. 
A5  Algorithm 5: Setup. 
A6  Algorithm 6: QWSH. 
A7  Algorithm 7: Diffuse. 
A8  Algorithm 8: FetchT. 
A9  Algorithm 9: StoreT. 
A10  Algorithm 10: FetchStoreT. 
A11  Algorithm 11: FetchE. 
A12  Algorithm 12: FetchStoreE. 
A13  Algorithm 13: Update. 
A14  Algorithm 14: SWAP. 
A15  Algorithm 15: TestTriangleEdges (inner quantum walk). 
A16  Algorithm 16: TriangleTestT. 
A17  Algorithm 17: TriangleTestTw. 
A18  Algorithm 18: TriangleEdgeSearch. 
A19  Algorithm 19: GCQWalk. 
A20  Algorithm 20: GCQWStep. 
O2  Algorithm O2: ConvertNODE. 
O3  Algorithm O3: TestEqual. 
O4  Algorithm O4: Pow17. 
O5  Algorithm O5: Mod3. 
O6  Algorithm O6: Sub. 
O7  Algorithm O7: Add. 
O8  Algorithm O8: Mul. 
A data type to hold values set by command line options.
Options  

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.
subroutine_enum :: [(String, Subroutine)] Source #
An enumeration of available subroutines and their names.
dopts :: [String] > IO Options Source #
Process argvstyle command line options into an Options
structure.
The Triangle Finding Algorithm main function
spec_of_options :: Options > QWTFP_spec Source #
Compute the appropriate problem specification for the given options.
qram_select :: QRamSelect > Qram Source #
Maps a QRamSelect
element to the corresponding Qram
object.