Quipper.Algorithms.TF.Main

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₁ , e₂ , e₃} 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:

• Quipper.Algorithms.TF.Main: Command line interface.
• Quipper.Algorithms.TF.Definitions: Some general purpose definitions.
• Quipper.Algorithms.TF.QWTFP: The implementation of the main Triangle Finding algorithm.
• Quipper.Algorithms.TF.Oracle: The implementation of the oracle for the Triangle Finding algorithm.
• Quipper.Algorithms.TF.Alternatives: Some alternative implementations of some of the subroutines.
• Quipper.Algorithms.TF.Simulate: Functions for simulating, testing, and debugging oracles.

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: log₂ of the tuple size of the Hamming graph. (Default value: 2.)

Option processing

data WhatToShow

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

Show WhatToShow

Defined in Quipper.Algorithms.TF.Main

Methods

showsPrec :: Int -> WhatToShow -> ShowS

show :: WhatToShow -> String

showList :: [WhatToShow] -> ShowS

data OracleSelect

An enumeration type for selecting an oracle.

Constructors

Orthodox

The default oracle.

Blackbox

A blackbox oracle.

Instances

Show OracleSelect

Defined in Quipper.Algorithms.TF.Main

Methods

showsPrec :: Int -> OracleSelect -> ShowS

show :: OracleSelect -> String

showList :: [OracleSelect] -> ShowS

data QRamSelect

A datatype for selecting a qRAM implementation.

Constructors

Standard_QRam

The default qRAM.

Alt_QRam

A slightly more efficient implementation.

Instances

Show QRamSelect

Defined in Quipper.Algorithms.TF.Main

Methods

showsPrec :: Int -> QRamSelect -> ShowS

show :: QRamSelect -> String

showList :: [QRamSelect] -> ShowS

data Subroutine

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

Show Subroutine

Defined in Quipper.Algorithms.TF.Main

Methods

showsPrec :: Int -> Subroutine -> ShowS

show :: Subroutine -> String

showList :: [Subroutine] -> ShowS

data Options

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

Constructors

Options

Fields

• what :: WhatToShow

  What kind of thing to output.

• s :: Subroutine

  What specific subroutine to output.

• format :: Format

  The output format.

• gatebase :: GateBase

  What kind of gates to decompose into.

• oracle :: OracleSelect

  Which kind of oracle to use.

• qram :: QRamSelect

  Which qram implementation to use.

• l :: Int

  Parameter l.

• n :: Int

  Parameter n.

• r :: Int

  Parameter r.

Instances

Show Options

Defined in Quipper.Algorithms.TF.Main

Methods

showsPrec :: Int -> Options -> ShowS

show :: Options -> String

showList :: [Options] -> ShowS

defaultOptions :: Options

The default options.

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

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

oracle_enum :: [(String, OracleSelect)]

An enumeration of available oracles and their names.

subroutine_enum :: [(String, Subroutine)]

An enumeration of available subroutines and their names.

dopts :: [String] -> IO Options

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

usage :: IO ()

Print usage message to stdout.

The Triangle Finding Algorithm main function

main :: IO ()

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

spec_of_options :: Options -> QWTFP_spec

Compute the appropriate problem specification for the given options.

qram_select :: QRamSelect -> Qram

Maps a QRamSelect element to the corresponding Qram object.