{-# LANGUAGE CPP #-} #if __GLASGOW_HASKELL__ < 710 {-# OPTIONS -fcontext-stack=50 #-} #else {-# OPTIONS -freduction-depth=50 #-} #endif -- | -- 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/[sub 1] , /e/[sub 2] , /e/[sub 3]} 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. module Quipper.Algorithms.TF.Main where import Quipper import Quipper.Libraries.Arith import Quipper.Libraries.Decompose import Quipper.Algorithms.TF.Definitions import Quipper.Algorithms.TF.Oracle import Quipper.Algorithms.TF.QWTFP import Quipper.Algorithms.TF.Simulate import Quipper.Algorithms.TF.Alternatives import Quipper.Utils.CommandLine import System.Console.GetOpt import System.Environment import System.Exit import System.IO import Control.Monad import Data.List import Data.Char import qualified Data.IntMap as IntMap ---------------------------------------------------------------------- -- * Documentation -- $ 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[sub 2] of the tuple size of the Hamming graph. -- (Default value: 2.) -- -- * Option processing -- -- | An enumeration type for determining what the main function should do. data WhatToShow = Circuit -- ^Show the whole circuit. | Oracle -- ^Show only the oracle. | Sub -- ^Show a specific subroutine. | Arith -- ^Run simulation tests of the arithmetic subroutines. | OTest -- ^Run simulation tests of the oracle. deriving Show -- | An enumeration type for selecting an oracle. data OracleSelect = Orthodox -- ^The default oracle. | Blackbox -- ^A blackbox oracle. deriving Show -- | A datatype for selecting a qRAM implementation. data QRamSelect = Standard_QRam -- ^ The default qRAM. | Alt_QRam -- ^ A slightly more efficient implementation. deriving Show -- | An enumeration type for selecting a subroutine. data Subroutine = A2 -- ^Algorithm 2: Zero. | A3 -- ^Algorithm 3: Initialize. | A4 -- ^Algorithm 4: Hadamard. | A5 -- ^Algorithm 5: Setup. | A6 -- ^Algorithm 6: QWSH. | A7 -- ^Algorithm 7: Diffuse. | A8 -- ^Algorithm 8: FetchT. | A9 -- ^Algorithm 9: StoreT. | A10 -- ^Algorithm 10: FetchStoreT. | A11 -- ^Algorithm 11: FetchE. | A12 -- ^Algorithm 12: FetchStoreE. | A13 -- ^Algorithm 13: Update. | A14 -- ^Algorithm 14: SWAP. | A15 -- ^Algorithm 15: TestTriangleEdges (inner quantum walk). | A16 -- ^Algorithm 16: TriangleTestT. | A17 -- ^Algorithm 17: TriangleTestTw. | A18 -- ^Algorithm 18: TriangleEdgeSearch. | A19 -- ^Algorithm 19: GCQWalk. | A20 -- ^Algorithm 20: GCQWStep. | O2 -- ^Algorithm O2: ConvertNODE. | O3 -- ^Algorithm O3: TestEqual. | O4 -- ^Algorithm O4: Pow17. | O5 -- ^Algorithm O5: Mod3. | O6 -- ^Algorithm O6: Sub. | O7 -- ^Algorithm O7: Add. | O8 -- ^Algorithm O8: Mul. deriving Show -- | A data type to hold values set by command line options. data Options = Options { what :: WhatToShow, -- ^What kind of thing to output. s :: Subroutine, -- ^What specific subroutine to output. format :: Format, -- ^The output format. gatebase :: GateBase, -- ^What kind of gates to decompose into. oracle :: OracleSelect, -- ^Which kind of oracle to use. qram :: QRamSelect, -- ^Which qram implementation to use. l :: Int, -- ^Parameter 'l'. n :: Int, -- ^Parameter 'n'. r :: Int -- ^Parameter 'r'. } deriving Show -- | The default options. defaultOptions :: Options defaultOptions = Options { what = Circuit, s = O7, format = Preview, gatebase = Logical, oracle = Blackbox, qram = Standard_QRam, l = 4, n = 3, r = 2 } -- | The list of command line options, in the format required by 'getOpt'. options :: [OptDescr (Options -> IO Options)] options = [ -- Generic options Option ['h'] ["help"] (NoArg help) "print usage info and exit", Option ['f'] ["format"] (ReqArg format "") "output format for circuits (default: preview)", Option ['g'] ["gatebase"] (ReqArg gatebase "") "type of gates to decompose into (default: logical)", -- Triangle finding parameters Option ['l'] ["l"] (ReqArg lll "") "parameter l (default: 4)", Option ['n'] ["n"] (ReqArg nnn "") "parameter n (default: 3)", Option ['r'] ["r"] (ReqArg rrr "") "parameter r (default: 2)", -- Main circuits Option ['C'] ["QWTFP"] (NoArg (what Circuit)) "output the whole circuit (default)", Option ['O'] ["oracle"] (NoArg (what Oracle)) "output only the oracle", -- Subroutine option Option ['s'] ["subroutine"] (ReqArg sub "") "output the chosen subroutine (default: adder)", -- QRAM option Option ['Q'] [] (NoArg (qram Alt_QRam)) "use alternative qRAM implementation", -- Oracle option Option ['o'] [] (ReqArg oracle "") "select oracle to use (default: blackbox)", -- Testing options Option ['A'] ["arith"] (NoArg (what Arith)) "test/simulate the arithmetic routines", Option ['T'] ["oracletest"] (NoArg (what OTest)) "test/simulate the oracle" ] where what :: WhatToShow -> Options -> IO Options what w o = return o { what = w } sub :: String -> Options -> IO Options sub str o = do case match_enum subroutine_enum str of [(_, f)] -> return o { what = Sub, s = f } [] -> optfail ("Unknown subroutine -- " ++ str ++ "\n") _ -> optfail ("Ambiguous subroutine -- " ++ str ++ "\n") qram :: QRamSelect -> Options -> IO Options qram q o = return o { qram = q } lll :: String -> Options -> IO Options lll string o = case parse_int string of Just l | l >= 1 -> return o { l = l } _ -> optfail ("Invalid value for parameter l -- " ++ string ++ "\n") nnn :: String -> Options -> IO Options nnn string o = case parse_int string of Just n | n >= 1 -> return o { n = n } _ -> optfail ("Invalid value for parameter n -- " ++ string ++ "\n") rrr :: String -> Options -> IO Options rrr string o = case parse_int string of Just r | r >= 1 -> return o { r = r } _ -> optfail ("Invalid value for parameter r -- " ++ string ++ "\n") format :: String -> Options -> IO Options format str o = do case match_enum format_enum str of [(_, f)] -> return o { format = f } [] -> optfail ("Unknown format -- " ++ str ++ "\n") _ -> optfail ("Ambiguous format -- " ++ str ++ "\n") gatebase :: String -> Options -> IO Options gatebase str o = do case match_enum gatebase_enum str of [(_, f)] -> return o { gatebase = f } [] -> optfail ("Unknown gate base -- " ++ str ++ "\n") _ -> optfail ("Ambiguous gate base -- " ++ str ++ "\n") oracle :: String -> Options -> IO Options oracle str o = do case match_enum oracle_enum str of [(_, f)] -> return o { oracle = f } [] -> optfail ("Unknown oracle -- " ++ str ++ "\n") _ -> optfail ("Ambiguous oracle -- " ++ str ++ "\n") help :: Options -> IO Options help o = do usage exitSuccess -- | An enumeration of available oracles and their names. oracle_enum :: [(String, OracleSelect)] oracle_enum = [ ("orthodox", Orthodox), ("blackbox", Blackbox) ] -- | An enumeration of available subroutines and their names. subroutine_enum :: [(String, Subroutine)] subroutine_enum = [ ("zero", A2), ("initialize", A3), ("hadamard", A4), ("setup", A5), ("qwsh", A6), ("diffuse", A7), ("fetcht", A8), ("storet", A9), ("fetchstoret", A10), ("fetche", A11), ("fetchstoree", A12), ("update", A13), ("swap", A14), ("a15", A15), ("a16", A16), ("a17", A17), ("a18", A18), ("gcqwalk", A19), ("gcqwstep", A20), ("convertnode", O2), ("testequal", O3), ("pow17", O4), ("mod3", O5), ("sub", O6), ("add", O7), ("mult", O8) ] -- | Process /argv/-style command line options into an 'Options' structure. dopts :: [String] -> IO Options dopts argv = case getOpt Permute options argv of (o, [], []) -> (foldM (flip id) defaultOptions o) (_, _, []) -> optfail "Too many non-option arguments\n" (_, _, errs) -> optfail (concat errs) -- | Print usage message to 'stdout'. usage :: IO () usage = do putStr (usageInfo header options) putStr (show_enum "format" format_enum) putStr (show_enum "gatebase" gatebase_enum) putStr (show_enum "oracle" oracle_enum) putStr (show_enum "subroutine" subroutine_enum) where header = "Usage: tf [OPTION...]" -- ---------------------------------------------------------------------- -- * The Triangle Finding Algorithm main function -- | Main function: read options, then execute the appropriate task. main :: IO() main = do argv <- getArgs options <- dopts argv let spec = spec_of_options options let p = ceiling (logBase 2 (fromIntegral (2^9 `choose` 3))) case options of Options { oracle = oracle, what = what, format = format, gatebase = gatebase, n = n, r = r, l = l, s = s} -> case what of Circuit -> print_generic format $ decompose_generic gatebase $ a1_QWTFP spec Oracle -> print_generic format (decompose_generic gatebase $ proj3 spec) node_shape node_shape qubit Arith -> arithmetic_tests l OTest -> oracle_tests n l Sub -> case s of A2 -> print_generic format (decompose_generic gatebase $ a2_ZERO (replicate n False)) A3 -> print_generic format (decompose_generic gatebase $ a3_INITIALIZE (replicate n False)) A4 -> print_generic format (decompose_generic gatebase $ a4_HADAMARD) (replicate n qubit) A5 -> print_generic format (decompose_generic gatebase $ a5_SETUP spec) tt_shape A6 -> print_generic format (decompose_generic gatebase $ a6_QWSH spec) tt_shape (qdint_shape r) node_shape ee_shape A7 -> print_generic format (decompose_generic gatebase $ a7_DIFFUSE) node_shape A8 -> print_generic format (decompose_generic gatebase $ a8_FetchT) (qdint_shape r) tt_shape node_shape A9-> print_generic format (decompose_generic gatebase $ a9_StoreT) (qdint_shape r) tt_shape node_shape A10-> print_generic format (decompose_generic gatebase $ a10_FetchStoreT) (qdint_shape r) tt_shape node_shape A11-> print_generic format (decompose_generic gatebase $ a11_FetchE) (qdint_shape r) ee_shape eed_shape A12-> print_generic format (decompose_generic gatebase $ a12_FetchStoreE) (qdint_shape r) ee_shape eed_shape A13-> print_generic format (decompose_generic gatebase $ a13_UPDATE spec) tt_shape node_shape eed_shape A14-> print_generic format (decompose_generic gatebase $ a14_SWAP) node_shape node_shape A15 -> print_generic format (decompose_generic gatebase $ a15_TestTriangleEdges spec) tt_shape ee_shape A16 -> print_generic format (decompose_generic gatebase $ a16_TriangleTestT) ee_shape A17 -> print_generic format (decompose_generic gatebase $ a17_TriangleTestTw spec) tt_shape ee_shape node_shape A18 -> print_generic format (decompose_generic gatebase $ a18_TriangleEdgeSearch spec) tt_shape ee_shape qubit A19 -> print_generic format (decompose_generic gatebase $ a19_GCQWalk spec) tt_shape ee_shape node_shape qubit A20 -> print_generic format (decompose_generic gatebase $ a20_GCQWStep spec) tt_shape ee_shape node_shape gcqw_shape O2 -> print_generic format (decompose_generic gatebase $ \u -> o2_ConvertNode l u (2^(n-1))) node_shape O3 -> print_generic format (decompose_generic gatebase $ o3_TestEqual) (qinttf_shape l) (qinttf_shape l) O4 -> print_generic format (decompose_generic gatebase $ o4_POW17) (qinttf_shape l) O5 -> print_generic format (decompose_generic gatebase $ o5_MOD3) (qinttf_shape l) O6 -> print_generic format (decompose_generic gatebase $ \u -> o6_SUB u (2^(n-1))) (qinttf_shape l) O7 -> print_generic format (decompose_generic gatebase $ o7_ADD) (qinttf_shape l) (qinttf_shape l) O8 -> print_generic format (decompose_generic gatebase $ o8_MUL) (qinttf_shape l) (qinttf_shape l) where rbar = max ((2 * r) `div` 3) 1 proj3 (a,b,c,d) = c node_shape = (replicate n qubit) tt_shape = (intMap_replicate (2^r) node_shape) ee_shape = (IntMap.fromList [(j,intMap_replicate j qubit) | j <- [0..((2^r)-1)]]) eed_shape = (intMap_replicate (2^r) qubit) gcqw_shape = (intMap_replicate (2^rbar) (qdint_shape r), (qdint_shape rbar), (qdint_shape r), (intMap_replicate (2^rbar) qubit), (qdint_shape (2*rbar - 1)), qubit) -- | Compute the appropriate problem specification for the given options. spec_of_options :: Options -> QWTFP_spec spec_of_options Options { oracle = Orthodox, n = n, r = r, l = l, qram = qram} = (n,r, (\u v edge -> do (u,v,edge) <- o1_ORACLE l u v edge; return edge), qram_select qram) spec_of_options Options { oracle = Blackbox, n = n, r = r, qram = qram} = (n,r,placeholder_oracle,qram_select qram) -- | Maps a 'QRamSelect' element to the corresponding 'Qram' object. qram_select :: QRamSelect -> Qram qram_select Standard_QRam = standard_qram qram_select Alt_QRam = alt_qram