quipper-algorithms-0.9.0.0: A set of algorithms implemented in Quipper.

Safe HaskellNone
LanguageHaskell98

Quipper.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 qshape 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 #

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