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.

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.)