Lessons Learned - Technical

There are several key technical lessons that we have learned after completing this project.

The significance of additional ancilla qubits when implementing oracles

Throughout this project, as well as through implementing the tasks in Part 1 of the challenge, we have gleamed the importance of ancilla qubits when implementing oracles.

For example, when implementing our marking oracle in "Battleship.ipynb", we use an ancilla register of two qubits: one to check the validity of the shape of the "large" ship, and another to check if the "large" ship is occupying a forbidden position on the board (i.e. overlapping with the "small ship). This is extremely convenient; not only because they can have easy and meaningful interpretation as granted by the programmer, but also because we can perform a controlled X gate on marking oracle's target qubit conditioned on this ancilla register--then flip these ancilla bits back by performing the inverse unitary operation. In Q#, this was accomplished nicely by taking advantage of the the "within...apply..." method.

The advantages of Q#'s syntax and level of abstraction

On a similar note, this project have also made us aware of several nice properties offered by Q#. For example, the ability to perform a Controlled variant of a gate, conditioned on some N-bit array or integer, is a distinct feature of Q# that allowed us to focus on implementing the algorithms rather than worrying about the underlying decomposition of these more complex gates into single and two-qubit unitaries.

Choosing an appropriate problem to solve for Grover's Algorithm

After searching for a suitable problem to tackle, we realized that many NP-type problems (easily verifiable but hard to solve) were prime candidates for Grover's Algorithm. We also realized that the class candidate problems was quite broad; in the end, we felt that our simplified version of Battleship's rules and setting allowed us to synthesize and practice several of the Challenge's key concepts. In general, we realized that any NP "game" that faces a given set of contraints is a good candidate for Grover's Algorithm, as those constraints motivate particular features of the oracle and ultimately about the possible behavior of the agents, allowed configurations of the players, and so on.