Quantum Battleship

See slideshow: https://docs.google.com/presentation/d/1Xv02K2xEivy99bZq3q9toStlX1cy-V3Z_xaGNfohmqo/edit?usp=sharing

Inspiration

Inspired by the Elitzur-Vaidman Bomb Tester, this project uses the same theories, along with the Zeno effect, to predict the location of every battleship on a grid without ever striking them.

What it does

Much like the bomb tester, the program sends a photon to the tile with a very small chance of striking. Without observing the photon, this chance is increased slightly and sent again and again. If a ship exists on the tile, the superposition collapses to zero each time and the chance of striking never increases. Otherwise, the chance of striking approaches 1, and eventually we will know that the tile is safe.

How we built it

This project was built in Python 3 using Qiskit. It is simulated using the AER Simulator, and run on an IBM quantum computer using the IBM Quantum Platform.

Challenges we ran into

Initially we took a completely different approach to the problem. We sent strikes to each tile in a column or row, and then measured the superposition similarly to the Elitzur-Vaidman Bomb Tester. This was only marginally better than randomly guessing tiles. We eventually discovered the Zeno effect, and after implementing that had much better success. Due to restarting near the end, the program is very successful, but not perfectly efficient. It works great with the simulator, but slows down significantly when run on physical quantum hardware.

Accomplishments that we're proud of

After discovering the Zeno effect, we implemented it very quickly and successfully. We solved the prompt given to us despite having no background using Qiskit or ever programming something like this. During the first few hours of the hackathon, our laptops were blank as we tried to wrap out heads around the difficult concepts at hand. To think that we went from that to not only having a working project, but one that is incredibly successful is unbelievable.

What we learned

We came into this project with no prior knowledge on Qiskit or programming quantum computers. We learned how gates work, how to simulate qubits, how to measure and think about superpositions, and how quantum computers can approach problems in completely unique ways. We specifically learned a lot about the Zeno effect, and the properties of superposition.

What's next for Qiskit Battleship

Next, we will continue to improve the programs efficiency. It overall is very successful and accurate, but the same results could be achieved much faster with some rewriting of code. Additionally, more tuning could be done, but the success rate is high enough currently that it is not an issue.