The Quipper System

Algorithms.TF.Simulate

Description

This module contains functions for simulating and debugging the Triangle Finding Oracle and its subroutines.

Synopsis

# Native and simulated arithmetic functions

For each arithmetic routine implemented in the Triangle Finding Oracle, we give two parallel implementations: one using Haskell’s arithmetic, and one by simulating the circuit execution.

These can then be cross-checked against each other for correctness.

Increment an m-bit Quipper integer (mod 2m). Native Haskell.

Increment an m-bit Quipper integer (mod 2m). Simulated from increment.

Increment an m-bit Triangle Finding integer (mod 2m–1). Native Haskell.

Increment an m-bit TF integer (mod 2m–1). Simulated from increment_TF.

Double an m-bit TF integer (mod 2m–1). Native Haskell.

Double an m-bit TF integer (mod 2m–1). Simulated from double_TF.

Add two IntTFs. Native Haskell.

Add two IntTFs. Simulated from o7_ADD.

Multiply two IntTFs. Native Haskell.

Multiply two IntTFs. Simulated from o8_MUL.

Raise an IntTF to the 17th power. Native Haskell.

Raise an IntTF to the 17th power. Simulated from o4_POW17.

Compute the reduction, mod 3, of lower-order bits of an IntTF. Native Haskell.

Compute the reduction, mod 3, of lower-order bits of an IntTF. Simulated from o5_MOD3.

Compute the reduction, mod 3, of lower-order bits of an IntTF. Simulated from o5_MOD3_alt.

# Native and simulated oracle functions

oracle_haskell :: Int -> [Bool] -> [Bool] -> Bool Source #

Oracle: compute the edge information between two nodes. Native Haskell.

oracle_simulate :: Int -> [Bool] -> [Bool] -> Bool Source #

Oracle: compute the edge information between two nodes. Simulated from o1_ORACLE.

oracle_aux_haskell :: Int -> [Bool] -> [Bool] -> (([Bool], [Bool]), (IntTF, IntTF, IntTF, IntTF, IntTF, IntTF), (Bool, Bool, Bool, Bool, Bool, Bool, Bool)) Source #

oracle_aux_simulate :: Int -> [Bool] -> [Bool] -> (([Bool], [Bool]), (IntTF, IntTF, IntTF, IntTF, IntTF, IntTF), (Bool, Bool, Bool, Bool, Bool, Bool, Bool)) Source #

Oracle auxiliary information. Simulated from o1_ORACLE_aux.

show_oracle_details :: Show a => (([Bool], [Bool]), (a, a, a, a, a, a), (Bool, Bool, Bool, Bool, Bool, Bool, Bool)) -> String Source #

A specialized show for oracle auxiliary data.

convertNode_haskell :: Int -> [Bool] -> IntTF Source #

Conversion of a node to an integer. Native Haskell.

convertNode_simulate :: Int -> [Bool] -> IntTF Source #

Conversion of a node to an integer. Simulated from o2_ConvertNode.

# Testing functions

Various small test suites, checking the simulated circuit arithmetic functions against their Haskell equivalents.

Give full table of values for increment functions.

Give full table of values for the increment_TF functions.

Give full table of values for the double_TF functions.

addTF_table :: Int -> [String] Source #

Give full table of values for the TF addition (o7_ADD) functions.

multTF_table :: Int -> [String] Source #

Give full table of values for the TF multiplication (o8_MUL) functions.

pow17_table :: Int -> [String] Source #

Give full table of values for the pow17 functions.

mod3_table :: Int -> [String] Source #

Give full table of values for the mod3 functions.

oracle_table :: Int -> Int -> [String] Source #

Give full table of values for the oracle.

Give a full table of values for o1_ORACLE_aux.

convertNode_table :: Int -> Int -> [String] Source #

Give full table of values for the ConvertNode functions.

A compilation of the various tests above, to be called by Main.

oracle_tests :: Int -> Int -> IO () Source #

A suite of tests for the oracle, to be called by Main.