The Quipper System

Safe HaskellNone

Algorithms.TF.QWTFP

Contents

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

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

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.

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

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)) Source #

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.

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

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) Source #

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) Source #

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.

standard_qram :: Qram Source #

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) Source #

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

a15_TestTriangleEdges Source #

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) Source #

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 Source #

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 Source #

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 Source #

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) Source #

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