The Quipper System

Algorithms.TF.Main

Description

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 {e1 , e2 , e3} forming ∆ by querying f.

The algorithm works by performing a Grover-based 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 minor-closed 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 ACM-SIAM 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:

Synopsis

# 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 black-box 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 4-bit 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: log2 of the tuple size of the Hamming graph. (Default value: 2.)

# Option processing

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

Constructors

 Circuit Show the whole circuit. Oracle Show only the oracle. Sub Show a specific subroutine. Arith Run simulation tests of the arithmetic subroutines. OTest Run simulation tests of the oracle.

Instances

 # MethodsshowList :: [WhatToShow] -> ShowS #

An enumeration type for selecting an oracle.

Constructors

 Orthodox The default oracle. Blackbox A blackbox oracle.

Instances

 # MethodsshowList :: [OracleSelect] -> ShowS #

A datatype for selecting a qRAM implementation.

Constructors

 Standard_QRam The default qRAM. Alt_QRam A slightly more efficient implementation.

Instances

 # MethodsshowList :: [QRamSelect] -> ShowS #

An enumeration type for selecting a subroutine.

Constructors

 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.

Instances

 # MethodsshowList :: [Subroutine] -> ShowS #

data Options Source #

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

Constructors

 Options Fieldswhat :: WhatToShowWhat kind of thing to output.s :: SubroutineWhat specific subroutine to output. format :: FormatThe output format.gatebase :: GateBaseWhat kind of gates to decompose into.oracle :: OracleSelectWhich kind of oracle to use.qram :: QRamSelectWhich qram implementation to use.l :: IntParameter l.n :: IntParameter n.r :: IntParameter r.

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.

An enumeration of available subroutines 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 Triangle Finding Algorithm main function

main :: IO () Source #

Maps a QRamSelect element to the corresponding Qram object.