Quipper.Algorithms.BF.Hex

This module contains the implementation of the circuits for determining which player has won a completed game of Hex. Please see Quipper.Algorithms.BF.Main for an overview of the boolean formula algorithm, or Quipper.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.

Documentation

qtrace :: [Bool] -> [Bool]

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

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

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

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

A hand-lifted version of the Prelude show function.

template_head :: Circ ([a] -> Circ a)

A hand-lifted function to get the head of a list.

template_tail :: Circ ([a] -> Circ [a])

A hand-lifted function to get the tail of a list.

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

A hand-lifted function to get the length of a list.

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

A hand-lifted version of the take function, specialized to lists of qubits.

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

A hand-lifted version of the drop function, specialized to lists of qubits.

template_replicate :: Circ (Int -> Circ (BoolParam -> Circ [BoolParam]))

A hand-lifted version of the replicate function, specialized to create lists of BoolParam.

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

A hand-lifted version of the map function.

template_integer :: Int -> Circ Int

Int is not changed along the conversion.

template_symb_minus_ :: Circ (Int -> Circ (Int -> Circ Int))

A hand-lifted version of the - function, specialized to Int.

template_symb_plus_ :: Circ (Int -> Circ (Int -> Circ Int))

A hand-lifted version of the + function, specialized to Int.

template_symb_oangle_ :: Circ (Int -> Circ (Int -> Circ Bool))

A hand-lifted version of the < function, specialized to Int.

template_symb_oangle_symb_equal_ :: Circ (Int -> Circ (Int -> Circ Bool))

A hand-lifted version of the <= function, specialized to Int.

template_div :: Circ (Int -> Circ (Int -> Circ Int))

A hand-lifted version of the div function, specialized to Int.

cand :: Bool -> Bool -> Bool

A function synonym for &&.

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

A hand-lifted version of the cand function.

template_symb_cangle_ :: Circ (Int -> Circ (Int -> Circ Bool))

A hand-lifted version of the > function, specialized to Int.

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

A hand-lifted version of the !! function.

template_mod :: Circ (Int -> Circ (Int -> Circ Int))

A hand-lifted version of the mod function, specialized to Int.

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

A hand-lifted version of the zip function, specialized to lists of qubits.

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

A hand-lifted version of the unzip function, specialized to a list of pairs of qubits.

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

A hand-lifted version of the or function, specialized to a list of qubits.

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

The Hex board consists of boolean parameters.

newBools :: [BoolParam] -> [Bool]

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

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

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

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

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

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

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]

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

int2bools'' :: Int -> [Bool]

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

lookup :: [Bool] -> [Bool] -> Bool

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

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

Hand-lifted version of lookup that uses addressed_perform to look up a qubit at the given address.

update :: [Bool] -> [Bool] -> [Bool]

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

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

Hand-lifted version of update that uses addressed_perform to negate a qubit at the given address.

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

An unencapsulated version of template_update, for testing purposes.

addressed_perform

Arguments

:: 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]

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

template_update_pos :: Circ (Int -> Circ ([Qubit] -> Circ (Qubit -> Circ [Qubit])))

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 Quipper.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]

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

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

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

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

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

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

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

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

Swap the position of two boolean values within a pair.

template_swapBool :: Circ ((Qubit, Qubit) -> Circ (Qubit, Qubit))

A hand-lifted version of the swapBool function, which uses a swap operation to swap the state of two qubits within a pair.

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

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

template_flood_fill :: Circ (Int -> Circ ([Qubit] -> Circ ([Qubit] -> Circ [Qubit])))

checkwin_red' :: [Bool] -> Bool

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.

template_checkwin_redsymb_quote_ :: Circ ([Qubit] -> Circ Qubit)

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

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.

template_checkwin_red :: Circ (Int -> Circ ([Qubit] -> Circ Qubit))

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

An unencapsulated version of the checkwin_red circuit.

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

A recursive sub-algorithm of hexT 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)))))

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

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

newBoolParam :: Bool -> BoolParam

A function to convert a boolean to a boolean parameters

newBoolParams :: [Bool] -> [BoolParam]

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

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

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)

An embedding of hex_oracle_c into a reversible circuit, where all ancillas are uncomputed automatically.

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

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

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

An embedding of checkwin_red_c into a reversible circuit, where all ancillas are uncomputed automatically.