The Quipper System

Algorithms.TF.QWTFP

Description

This module provides an implementation of the Quantum Walk for the Triangle Finding Problem.

The algorithm works by performing a Grover-based quantum walk on a larger graph H, called the Hamming graph associated to G. We refer to this part of the algorithm as the outer walk. The subroutine used to check whether a triangle has been found is itself a quantum walk, the inner walk.

The overall algorithm is parameterized on integers l, n and r specifying respectively the length l of the integers used by the oracle, the number 2n of nodes of G and the size 2r of Hamming graph tuples.

Synopsis

# Main TF algorithm

Algorithm 1. Do a quantum walk on the Hamming graph associated with G. Returns a quadruple (testTMeasure, wMeasure, TMeasure, EMeasure) where wMeasure contains a node of the triangle with the other two nodes in TMeasure.

# Utility subroutines

a2_ZERO :: QShape a qa ca => a -> Circ qa Source #

Algorithm 2. Initialize the qubits in a register to a specified state. Defined using the more generic qinit.

a3_INITIALIZE :: QShape a qa ca => a -> Circ qa Source #

Algorithm 3. Initialize to a specified state then apply a Hadamard gate to the qubits in a register.

a4_HADAMARD :: QData qa => qa -> Circ qa Source #

Algorithm 4. Apply a Hadamard gate to every qubit in the given quantum data. Defined using the more generic map_hadamard.

Algorithm 5. Set up the register ee with the edge information for the nodes contained in tt.

## The outer quantum walk and the standard Qram

Algorithm 6. Do a quantum walk step on the Hamming graph.

a7_DIFFUSE :: QData qa => qa -> Circ qa Source #

Algorithm 7. Diffuse a piece of quantum data, in the Grover search sense of reflecting about the average.

Note: relies on shape q corresponding to the “all false” state.

a8_FetchT :: QData qa => QDInt -> IntMap qa -> qa -> Circ (QDInt, IntMap qa, qa) Source #

Algorithm 8. Perform a quantum-addressed fetch operation. This fetches the i-th element from tt into ttd. Precondition: ttd = 0.

This could be implemented more efficiently using the qRAM implementation in Alternatives.

a9_StoreT :: QData qa => QDInt -> IntMap qa -> qa -> Circ (QDInt, IntMap qa, qa) Source #

Algorithms 9. Perform a quantum-addressed store operation: store ttd into the i-th element from tt. Analogous to a8_FetchT.

a10_FetchStoreT :: QData qa => QDInt -> IntMap qa -> qa -> Circ (QDInt, IntMap qa, qa) Source #

Algorithm 10. Perform a quantum-addressed swap: swap ttd with the i-th element of tt. Analogous to a8_FetchT and a9_StoreT.

Algorithm 11. Perform a quantum-addressed fetch operation. This is a somewhat specialized addressed fetching operation.

Algorithm 12. Perform a quantum-addressed swap. Analogous to a11_FetchE.

Algorithm 13. Given a list of nodes tt, a distinguished node ttd, and a list of bits eed, either:

• store the edge information for (ttd,tt) into eed, if eed is initially 0; or
• zero eed, if it initially holds the edge information.

a14_SWAP :: QCData qa => qa -> qa -> Circ (qa, qa) Source #

Algorithm 14. Swap two registers of equal size. This is a generic function and works for any quantum data type.

The qRAM operations from Algorithms 8–10 wrapped into a Qram object.

## The inner quantum walk

A type to hold the Graph Collision Quantum Walk Registers (tau, iota, sigma, eew, cTri, triTestT), used in a20_GCQWStep.

Arguments

 :: QWTFP_spec The ambient oracle. -> IntMap QNode tt, an R-tuple of nodes. -> IntMap (IntMap Qubit) ee, a cache of the edge information between nodes in tt. -> Circ (IntMap QNode, IntMap (IntMap Qubit), QNode, Qubit, Qubit) Return (tt, ee, w, triTestT,triTestTw).

Algorithm 15: TestTriangleEdges. Test whether the nodes tt contain a pair that can be extended to a triangle in the graph. Used as the test function in the outer quantum walk. Seeks triangles in two different ways:

1. Entirely within the nodes tt. If found, set qubit triTestT.
2. With two vertices from tt, a third anywhere in the graph. If found, set qubit triTestTw, and return the third vertex as w. This is implemented using an “inner quantum walk” to seek w.

Algorithm 16: TriangleTestT ee triTestT. Search exhaustively over the array ee of edge data, seeking a triangle. Whenever one is found, flip the qubit triTestT.

Arguments

 :: QWTFP_spec The ambient oracle. -> IntMap QNode tt, an R-tuple of nodes. -> IntMap (IntMap Qubit) ee, a cache of the edge data for T. -> QNode w, another node. -> Circ (IntMap QNode, IntMap (IntMap Qubit), QNode, Qubit) return (tt,ee,w,triTestTw).

Algorithm 17: TriangleTestTw ee triTestTw. Search exhaustively for a pair of nodes in tt that form a triangle with w. Whenever a triangle found, flip qubit triTestTw.

Arguments

 :: QWTFP_spec The ambient oracle. -> IntMap QNode tt, an R-tuple of nodes. -> IntMap (IntMap Qubit) ee, a cache of edge data for R. -> Qubit triTestT, test qubit recording if a triangle has already been found. -> Circ (IntMap QNode, IntMap (IntMap Qubit), QNode, Qubit) Return (tt, ee, w, regs).

Algorithm 18: TriangleEdgeSearch. Use Grover search to seek a node w that forms a triangle with some pair of nodes in tt, unless a triangle has already been found (recorded in triTestT), in which case do nothing.

Arguments

 :: QWTFP_spec The ambient oracle. -> IntMap QNode tt, an R-tuple of nodes. -> IntMap (IntMap Qubit) ee, a cache of the edge data for tt. -> QNode w, a node. -> Qubit triTestT, test qubit to record if a triangle has already been found. -> Circ (IntMap QNode, IntMap (IntMap Qubit), QNode, Qubit, QDInt) Return (tt,ee,w,triTestT,cTri).

Algorithm 19: GCQWalk (“Graph Collision Quantum Walk”)

Perform graph collision on the R-tuple tt and the node w, to determine (with high probability) whether w forms a triangle with some pair of nodes in tt.

Algorithm 20: GCQWStep Take one step in the graph collision walk (used in a19_GCQWalk above). Uses many auxiliary registers. The arguments are, in this order:

• The ambient oracle.
• tt, an R-tuple of nodes.
• ee, a cache of the edge data for tt.
• w, a node.
• regs, various workspace/output registers.
• ttd, eed, taud, eewd, and eedd, local ancillas.

The function returns (tt, ee, w, regs).