Quipper.Algorithms.TF.QWTFP

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 2ⁿ of nodes of G and the size 2^r of Hamming graph tuples.

Main TF algorithm

a1_QWTFP :: QWTFP_spec -> Circ (Bit, CNode, IntMap CNode, IntMap (IntMap Bit))

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

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

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

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

a5_SETUP :: QWTFP_spec -> IntMap QNode -> Circ (IntMap QNode, IntMap (IntMap Qubit))

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

a6_QWSH :: QWTFP_spec -> IntMap QNode -> QDInt -> QNode -> IntMap (IntMap Qubit) -> Circ (IntMap QNode, QDInt, QNode, IntMap (IntMap Qubit))

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

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

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

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

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

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 Quipper.Algorithms.TF.Alternative.

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

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

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

a11_FetchE :: QDInt -> IntMap (IntMap Qubit) -> IntMap Qubit -> Circ (QDInt, IntMap (IntMap Qubit), IntMap Qubit)

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

a12_FetchStoreE :: QDInt -> IntMap (IntMap Qubit) -> IntMap Qubit -> Circ (QDInt, IntMap (IntMap Qubit), IntMap Qubit)

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

a13_UPDATE :: QWTFP_spec -> IntMap QNode -> QNode -> IntMap Qubit -> Circ (IntMap QNode, QNode, IntMap Qubit)

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)

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

standard_qram :: Qram

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

The inner quantum walk

type GCQWRegs = (IntMap QDInt, QDInt, QDInt, IntMap Qubit, QDInt, Qubit)

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

a15_TestTriangleEdges

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.

a16_TriangleTestT :: IntMap (IntMap Qubit) -> Circ (IntMap (IntMap Qubit), Qubit)

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.

a17_TriangleTestTw

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.

a18_TriangleEdgeSearch

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.

a19_GCQWalk

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.

a20_GCQWStep :: QWTFP_spec -> IntMap QNode -> IntMap (IntMap Qubit) -> QNode -> GCQWRegs -> Circ (IntMap QNode, IntMap (IntMap Qubit), QNode, GCQWRegs)

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