The input to the BF Algorithm is the description of an oracle to represent a given size of hex board, and a given size for the phase estimation register.

A type to define which Hex circuit to use.

Create an oracle description. This only requires x, y, and t to be specified, as the remaining values can be calculated. The number of moves remaining, s, is calculated as the total number of squares on the board, and m is calculated as the number of bits required to represent s+1.

A function to set the "Dummy" flag in the given oracle to the given HexCircuit value.

Update the start_board in the given oracle, with the given HexBoard. This also updates the oracle_s field of the oracle to be in line with the new start_board.

An oracle for a 9 by 7 Hex board, with the parameters: x=9, y=7, t=189. The calculated values are: s=63, m=6.

A smaller oracle for testing purposes. The numbers should be chosen such that x⋅y = 2ⁿ−1 for some n. Here, we set x=3 and y=5, to give x⋅y=15. We arbitrarily set the size of the phase estimation register to t=4.

A hex board is specified by a pair of lists of booleans. For a board of size x by y, each list should contain x⋅y elements. The first list is the "blue" bitmap, and the second is the "red" maskmap.

A function to determine how many moves have been made on a given HexBoard. This function assumes that the given HexBoard is valid, in the sense that no duplicate moves have been made.

A function to determine which spaces are still empty in the given HexBoard. This function assumes that the given HexBoard is valid, in the sense that no duplicate moves have been made. This function will return a list of all the empty spaces remaining, in strictly increasing order.

The phase estimation register is a simple register of qubits. This is kept separate from the rest of the BooleanFormulaRegister as it is this register which will be measured at the end of the algorithm.

The direction register is a simple register of qubits, made explicit here so we can see that a "position" is a list of directions.

A type synonym defined as the Qubit instance of a GenericDirectionRegister.

The rest of the boolean formula algorithm requires a register which is split into 3 main parts.

A type synonym defined as the Qubit instantiation of a GenericBooleanFormulaRegister.

A function to add labels to the wires that make up a BooleanFormulaRegister. These labels correspond to the parts of the register.

A type synonym defined as the Bool instantiation of a GenericBooleanFormulaRegister.

Helper function to simplify the QCData instance for BooleanFormulaRegister. Create a tuple from a GenericBooleanFormulaRegister.

Helper function to simplify the QCData instance for BooleanFormulaRegister. Create a GenericBooleanFormulaRegister from a tuple.

Create an initial classical BooleanFormulaRegister for a given oracle description. The position register is initialized in the zero state that represents being at label zero, or node rpp in the tree. The work qubits are all initialized to zero, as the first call to the oracle circuit will set them accordingly for the position we are currently in. The direction register is also set to zero as this is the direction in which the node rp is in. The given BooleanFormulaOracle is used to make sure the registers are of the correct size, i.e., number of qubits.

Create a shape parameter for a BooleanFormulaRegister of the correct size.

Initialize a BooleanFormulaRegister from a BooleanFormulaOracle.

The overall Boolean Formula Algorithm. It initializes the phase estimation register into an equal super-position of all 2^t states, and the other registers as defined previously. It then maps the exponentiated version of the unitary u, as per phase estimation, before applying the inverse QFT, and measuring the result.

The inverse quantum Fourier transform as a boxed subroutine.

"Map" the application of the exponentiated unitary u over the phase estimation register. That is, each qubit in the phase estimation register is used as a control over a call to the unitary u, exponentiated to the appropriate power.

Exponentiate the unitary u. In this implementation, this is achieved by repeated application of u.

The unitary u represents a single step in the walk on the NAND tree. A call to the oracle determines what type of node we are at (so we know which directions are valid to step to), the call to diffuse sets the direction register to be a super-position of all valid directions, the call to walk performs the step, and then the call to undo oracle has to clean up the work registers that were set by the call to the oracle. Note that the undo oracle step is not simply the inverse of the oracle, as we have walked since the oracle was called.

The circuit for u as a boxed subroutine.

Call the oracle to determine some extra information about where we are in the tree. Essentially, the special cases are when were are at one of the three "low height" nodes, or when we are at a node representing a complete game of Hex, and we need to determine if this is a leaf, by calling the hex circuit, which determines whether the node represents a completed game of hex in which the red player has won.

The circuit for the oracle as a boxed subroutine.

The controls to use, to see if we're at a "low height" node.

Diffuse the direction register, to be a super-position of all valid directions from the current node. Note, that this implementation of the boolean formula algorithm does not applying the correct weighting scheme to the NAND graph, which would require this function to diffuse with respect to the weighting scheme.

The circuit for diffuse as a boxed subroutine.

A datatype to use instead of passing integers to toParent and toChild to define what needs to be shifted. This is used as only three different shift widths are ever used in the algorithm.

Define a step on the NAND graph, in the direction specified by the direction register, and updates the direction register to be where we have stepped from. For this algorithm we have developed the if_then_elseQ construct, which gives us a nice way of constructing if/else statements acting on boolean statements over qubits (see Quipper.Libraries.QuantumIf).

The circuit for walk as a boxed subroutine.

Uncompute the various flags that were set by the initial call to the oracle. It has to uncompute the flags depending on where we were before the walk step, so isn't just the inverse of the oracle.

The circuit for undo_oracle as a boxed subroutine.

Define the circuit that updates the position register to be the parent node of the current position.

copy_from_to a b: Sets the state of qubit b to be the state of qubit a, (and the state of a is lost in the process, so this is not cloning). It falls short of swapping a and b, as we're not interested in preserving a.

Define the circuit that updates the position register to be the child node of the current position.

Shift every qubit in a register to the left by one.

Shift every qubit in a register to the right by one.

Displays the overall Boolean Formula circuit for a given oracle description.

Display just 1 time-step of the given oracle, i.e., one iteration of the u from exp_u, with no controls.

Display just 1 time-step of the walk algorithm for the given oracle, i.e., one iteration of walk, with no controls.

Display just 1 time-step of the diffuse algorithm for the given oracle, i.e., one iteration of diffuse, with no controls.

Display just 1 time-step of the oracle algorithm for the given oracle, i.e., one iteration of oracle, with no controls.

Display just 1 time-step of the undo_oracle algorithm for the given oracle, i.e., one iteration of undo_oracle, with no controls.

Display the circuit for the Hex algorithm, for the given oracle, i.e., one iteration of hex_oracle, with no controls.

Display the circuit for the Checkwin_red algorithm, for the given oracle, i.e., one iteration of checkwin_red_circuit, with no controls.

Approximation of how the algorithm would be run if we had a quantum computer: uses QuantumSimulation run_generic_io function. The output of the algorithm will be all False only in the instance that the Blue player wins the game.

Display the result of main_bf, i.e., either "Red Wins", or "Blue Wins" is the output.

Run whoWins for the given oracle, and its "initial" board.