The Quipper System

Safe HaskellNone

Algorithms.TF.Main

Contents

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

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.

Sub

Show a specific subroutine.

Arith

Run simulation tests of the arithmetic subroutines.

OTest

Run simulation tests of the oracle.

data OracleSelect Source #

An enumeration type for selecting an oracle.

Constructors

Orthodox

The default oracle.

Blackbox

A blackbox oracle.

data QRamSelect Source #

A datatype for selecting a qRAM implementation.

Constructors

Standard_QRam

The default qRAM.

Alt_QRam

A slightly more efficient implementation.

data Subroutine Source #

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.

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.

subroutine_enum :: [(String, Subroutine)] Source #

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 #

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

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.