Safe Haskell | None |
---|

This module contains the implementation of the circuits for determining which player has won a completed game of Hex. Please see Algorithms.BF.Main for an overview of the boolean formula algorithm, or Algorithms.BF.BooleanFormula to see where these circuits are used in the overall implementation of the boolean formula algorithm. The functions defined in this module make heavy use of Quipper's "build_circuit" keyword, to automatically generate quantum circuits.

- qtrace :: [Bool] -> [Bool]
- template_qtrace :: Circ ([Qubit] -> Circ [Qubit])
- template_show :: Show a => Circ (a -> Circ String)
- template_head :: Circ ([a] -> Circ a)
- template_tail :: Circ ([a] -> Circ [a])
- template_length :: Circ ([a] -> Circ Int)
- template_take :: Circ (Int -> Circ ([Qubit] -> Circ [Qubit]))
- template_drop :: Circ (Int -> Circ ([Qubit] -> Circ [Qubit]))
- template_replicate :: Circ (Int -> Circ (BoolParam -> Circ [BoolParam]))
- template_map :: Circ ((a -> Circ a) -> Circ ([a] -> Circ [a]))
- template_integer :: Int -> Circ Int
- template_symb_minus_ :: Circ (Int -> Circ (Int -> Circ Int))
- template_symb_plus_ :: Circ (Int -> Circ (Int -> Circ Int))
- template_symb_oangle_ :: Circ (Int -> Circ (Int -> Circ Bool))
- template_symb_oangle_symb_equal_ :: Circ (Int -> Circ (Int -> Circ Bool))
- template_div :: Circ (Int -> Circ (Int -> Circ Int))
- cand :: Bool -> Bool -> Bool
- template_cand :: Circ (Bool -> Circ (Bool -> Circ Bool))
- template_symb_cangle_ :: Circ (Int -> Circ (Int -> Circ Bool))
- template_symb_exclamation_symb_exclamation_ :: Circ ([a] -> Circ (Int -> Circ a))
- template_mod :: Circ (Int -> Circ (Int -> Circ Int))
- template_zip :: Circ ([Qubit] -> Circ ([Qubit] -> Circ [(Qubit, Qubit)]))
- template_unzip :: Circ ([(Qubit, Qubit)] -> Circ ([Qubit], [Qubit]))
- template_or :: Circ ([Qubit] -> Circ Qubit)
- type HexBoardParam = ([BoolParam], [BoolParam])
- newBools :: [BoolParam] -> [Bool]
- template_newBools :: Circ ([BoolParam] -> Circ [Qubit])
- bools2int :: [Bool] -> Int
- bools2int' :: [Bool] -> Int
- int2bools :: Int -> Int -> [Bool]
- int2bools' :: Int -> Int -> [Bool]
- int2bools'' :: Int -> [Bool]
- lookup :: [Bool] -> [Bool] -> Bool
- template_lookup :: Circ ([Qubit] -> Circ ([Qubit] -> Circ Qubit))
- update :: [Bool] -> [Bool] -> [Bool]
- template_update :: Circ ([Qubit] -> Circ ([Qubit] -> Circ [Qubit]))
- test_update :: [Qubit] -> [Qubit] -> Circ [Qubit]
- addressed_perform :: QData qa => [qa] -> [Qubit] -> (qa -> Circ b) -> Circ b
- update_pos :: Int -> [Bool] -> Bool -> [Bool]
- template_update_pos :: Circ (Int -> Circ ([Qubit] -> Circ (Qubit -> Circ [Qubit])))
- testpos :: Int -> [Bool] -> [Bool] -> [Bool] -> Int -> [Bool]
- template_testpos :: Circ (Int -> Circ ([Qubit] -> Circ ([Qubit] -> Circ ([Qubit] -> Circ (Int -> Circ [Qubit])))))
- test_positions :: Int -> Int -> Int -> [Bool] -> [Bool] -> [Bool] -> ([Bool], [Bool])
- template_test_positions :: Circ (Int -> Circ (Int -> Circ (Int -> Circ ([Qubit] -> Circ ([Qubit] -> Circ ([Qubit] -> Circ ([Qubit], [Qubit])))))))
- while_for :: Int -> Int -> Int -> [Bool] -> [Bool] -> [Bool] -> ([Bool], [Bool])
- template_while_for :: Circ (Int -> Circ (Int -> Circ (Int -> Circ ([Qubit] -> Circ ([Qubit] -> Circ ([Qubit] -> Circ ([Qubit], [Qubit])))))))
- while :: Int -> Int -> [Bool] -> [Bool] -> [Bool] -> [Bool]
- template_while :: Circ (Int -> Circ (Int -> Circ ([Qubit] -> Circ ([Qubit] -> Circ ([Qubit] -> Circ [Qubit])))))
- swapBool :: (Bool, Bool) -> (Bool, Bool)
- template_swapBool :: Circ ((Qubit, Qubit) -> Circ (Qubit, Qubit))
- flood_fill :: Int -> [Bool] -> [Bool] -> [Bool]
- template_flood_fill :: Circ (Int -> Circ ([Qubit] -> Circ ([Qubit] -> Circ [Qubit])))
- checkwin_red' :: [Bool] -> Bool
- template_checkwin_redsymb_quote_ :: Circ ([Qubit] -> Circ Qubit)
- checkwin_red :: Int -> [Bool] -> Bool
- template_checkwin_red :: Circ (Int -> Circ ([Qubit] -> Circ Qubit))
- checkwin_red_c :: Int -> [Qubit] -> Circ Qubit
- movesT :: Int -> [[Bool]] -> [Bool] -> [Bool] -> BoolParam -> Bool
- template_movesT :: Circ (Int -> Circ ([[Qubit]] -> Circ ([Qubit] -> Circ ([Qubit] -> Circ (BoolParam -> Circ Qubit)))))
- hexT :: HexBoardParam -> BoolParam -> Int -> [[Bool]] -> Bool
- template_hexT :: Circ (([BoolParam], [BoolParam]) -> Circ (BoolParam -> Circ (Int -> Circ ([[Qubit]] -> Circ Qubit))))
- newBoolParam :: Bool -> BoolParam
- newBoolParams :: [Bool] -> [BoolParam]
- hex_oracle_c :: ([Bool], [Bool]) -> Int -> Int -> [[Qubit]] -> Circ Qubit
- hex_oracle :: ([Bool], [Bool]) -> Int -> Int -> ([[Qubit]], Qubit) -> Circ ([[Qubit]], Qubit)
- hex_oracle_dummy :: ([[Qubit]], Qubit) -> Circ ([[Qubit]], Qubit)
- checkwin_red_circuit :: Int -> ([Qubit], Qubit) -> Circ ([Qubit], Qubit)

# Documentation

qtrace :: [Bool] -> [Bool] Source #

A dummy gate, that when lifted will add a quantum trace to the circuit.

template_qtrace :: Circ ([Qubit] -> Circ [Qubit]) Source #

A hand-lifted version of qtrace, adds a named "trace" gate to the circuit.

template_show :: Show a => Circ (a -> Circ String) Source #

A hand-lifted version of the Prelude `show`

function.

template_length :: Circ ([a] -> Circ Int) Source #

A hand-lifted function to get the `length`

of a list.

template_take :: Circ (Int -> Circ ([Qubit] -> Circ [Qubit])) Source #

A hand-lifted version of the `take`

function, specialized to lists of qubits.

template_drop :: Circ (Int -> Circ ([Qubit] -> Circ [Qubit])) Source #

A hand-lifted version of the `drop`

function, specialized to lists of qubits.

template_map :: Circ ((a -> Circ a) -> Circ ([a] -> Circ [a])) Source #

A hand-lifted version of the `map`

function.

template_cand :: Circ (Bool -> Circ (Bool -> Circ Bool)) Source #

A hand-lifted version of the `cand`

function.

template_symb_exclamation_symb_exclamation_ :: Circ ([a] -> Circ (Int -> Circ a)) Source #

A hand-lifted version of the `!!`

function.

template_zip :: Circ ([Qubit] -> Circ ([Qubit] -> Circ [(Qubit, Qubit)])) Source #

A hand-lifted version of the `zip`

function, specialized to lists of qubits.

template_unzip :: Circ ([(Qubit, Qubit)] -> Circ ([Qubit], [Qubit])) Source #

A hand-lifted version of the `unzip`

function, specialized to a list of pairs of qubits.

template_or :: Circ ([Qubit] -> Circ Qubit) Source #

A hand-lifted version of the `or`

function, specialized to a list of qubits.

type HexBoardParam = ([BoolParam], [BoolParam]) Source #

The Hex board consists of boolean parameters.

newBools :: [BoolParam] -> [Bool] Source #

Convert a list of boolean parameters into a list of boolean inputs.

template_newBools :: Circ ([BoolParam] -> Circ [Qubit]) Source #

A hand-lifted function to convert a list of boolean parameters into a list of qubits initialized as ancillas is the given states.

bools2int :: [Bool] -> Int Source #

Convert a little-endian list of booleans into an integer by
reversing the list and calling the big-endian conversion function
`bools2int'`

.

bools2int' :: [Bool] -> Int Source #

Convert a big-endian list of booleans into an integer. This is mainly used for displaying a "position" register.

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

Convert an integer into a little-endian list of booleans of length *n*
by reversing the big-endian list created by the `int2bools'`

function.

int2bools' :: Int -> Int -> [Bool] Source #

Convert an integer into a big-endian list of booleans of length *n*.
| Note that the behavior when *x* is greater than 2^{n} - 1 is erroneous.

int2bools'' :: Int -> [Bool] Source #

Convert an integer into a big-endian list of booleans of minimal length.

lookup :: [Bool] -> [Bool] -> Bool Source #

This function is a stub, because a hand lifted version is given for creating the circuits.

template_lookup :: Circ ([Qubit] -> Circ ([Qubit] -> Circ Qubit)) Source #

Hand-lifted version of lookup that uses `addressed_perform`

to look up a qubit at the given address.

update :: [Bool] -> [Bool] -> [Bool] Source #

Update the board, by negating the boolean in board, at the given address.

template_update :: Circ ([Qubit] -> Circ ([Qubit] -> Circ [Qubit])) Source #

Hand-lifted version of update that uses `addressed_perform`

to negate a qubit at the given address.

test_update :: [Qubit] -> [Qubit] -> Circ [Qubit] Source #

An unencapsulated version of `template_update`

, for testing purposes.

:: QData qa | |

=> [qa] | Array of quantum data. |

-> [Qubit] | Index into the array. |

-> (qa -> Circ b) | An operation to be performed. |

-> Circ b |

Perform a given operation on a quantum-addressed element of an array of quantum data.

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

Update the boolean value at the given position, to the given value.

# Oracle implementation

The functions in this implementation follow a separation of the boolean formula algorithm into two parts. The first part consists of the algorithms defined in Algorithms.BF.BooleanFormula. The second part consists of the algorithms defined in this module. This separation relates to the first part defining the quantum parts of the algorithm, including the phase estimation, and the quantum walk, whereas the remaining four define the classical implementation of the circuit for determining which player has won a completed game of Hex, which is converted to a quantum circuit using Quipper's "build_circuit" keyword.

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

A helper function, used by the `flood_fill`

function, that
checks whether a given board position is currently vacant.

template_testpos :: Circ (Int -> Circ ([Qubit] -> Circ ([Qubit] -> Circ ([Qubit] -> Circ (Int -> Circ [Qubit]))))) Source #

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

Given a board position, this function will call
`testpos`

for each of its neighboring board positions.

template_test_positions :: Circ (Int -> Circ (Int -> Circ (Int -> Circ ([Qubit] -> Circ ([Qubit] -> Circ ([Qubit] -> Circ ([Qubit], [Qubit]))))))) Source #

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

This function calls `test_positions`

for every board position in strictly
increasing order.

template_while_for :: Circ (Int -> Circ (Int -> Circ (Int -> Circ ([Qubit] -> Circ ([Qubit] -> Circ ([Qubit] -> Circ ([Qubit], [Qubit]))))))) Source #

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

This function is used by `flood_fill`

to perform an approximation of a while loop.
This starts with *newmap* containing only the blue pieces from the top row of the
Hex board, and fills in all contiguous regions, i.e., areas bounded by red pieces.
The resulting bitmap will only have blue pieces in the bottom row of the Hex board,
if blue has won. The number of times the loop will repeat is bounded by the size of
the Hex board.

template_while :: Circ (Int -> Circ (Int -> Circ ([Qubit] -> Circ ([Qubit] -> Circ ([Qubit] -> Circ [Qubit]))))) Source #

swapBool :: (Bool, Bool) -> (Bool, Bool) Source #

Swap the position of two boolean values within a pair.

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

Implements a `flood_fill`

algorithm on a representation of a Hex
board. Returning the "flooded" version of the board.

checkwin_red' :: [Bool] -> Bool Source #

A sub-algorithm of the `checkwin_red`

algorithm, which is given the bottom row of
booleans after the `flood_fill`

algorithm has been run, and checks to see if any of
them are `True`

.

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

Given a description of a valid Hex board, i.e., a board that represents a finished game, with a single piece on each square, will return a boolean value stating whether the red player has won.

checkwin_red_c :: Int -> [Qubit] -> Circ Qubit Source #

An unencapsulated version of the `checkwin_red`

circuit.

movesT :: Int -> [[Bool]] -> [Bool] -> [Bool] -> BoolParam -> Bool Source #

A recursive sub-algorithm of `hex`

that goes through each direction in the
position register and recursively updates the ancilla register representing
the *blueboard* and *redboard* depending on which player's turn it is. If a
position is already set in one of the ancilla registers, then the current player
has played an invalid move, and therefore loses. If we pass through the entire
position register, then we have a valid description of a Hex board split between
the *redboard* and *blueboard* registers, which can then be passed to `checkwin_red`

to see who has won (we actually only pass the *redboard* to `checkwin_red`

as every
square is now either a red piece or a blue piece, so no extra information is held
in the *blueboard* register).

template_movesT :: Circ (Int -> Circ ([[Qubit]] -> Circ ([Qubit] -> Circ ([Qubit] -> Circ (BoolParam -> Circ Qubit))))) Source #

hexT :: HexBoardParam -> BoolParam -> Int -> [[Bool]] -> Bool Source #

The overall hex function. This initializes two ancilla registers
to represent the *redboard* and the *blueboard*, and passes these to the recursive
`movesT`

function to determine which color has won the game of Hex.

template_hexT :: Circ (([BoolParam], [BoolParam]) -> Circ (BoolParam -> Circ (Int -> Circ ([[Qubit]] -> Circ Qubit)))) Source #

newBoolParam :: Bool -> BoolParam Source #

A function to convert a boolean to a boolean parameters

newBoolParams :: [Bool] -> [BoolParam] Source #

A function to convert a list of booleans to a list of boolean parameters.

hex_oracle_c :: ([Bool], [Bool]) -> Int -> Int -> [[Qubit]] -> Circ Qubit Source #

An interface to the lifted version of `hexT`

(i.e.,
`template_hexT`

), which unbinds the inputs from the `Circ`

monad.

hex_oracle :: ([Bool], [Bool]) -> Int -> Int -> ([[Qubit]], Qubit) -> Circ ([[Qubit]], Qubit) Source #

An embedding of `hex_oracle_c`

into a reversible circuit, where all
ancillas are uncomputed automatically.

hex_oracle_dummy :: ([[Qubit]], Qubit) -> Circ ([[Qubit]], Qubit) Source #

A dummy oracle is just a gate named HEX applied to the input qubits.

checkwin_red_circuit :: Int -> ([Qubit], Qubit) -> Circ ([Qubit], Qubit) Source #

An embedding of `checkwin_red_c`

into a reversible circuit, where all
ancillas are uncomputed automatically.