Quantum Computational Speedup For The Minesweeper Problem

Abstract: Quantum computing is a young but intriguing field of science. It combines quantum mechanics with information theory and computer science to potentially solve certain formerly computationally expensive tasks more efficiently. Classical computers are based on bits that can take on the value zero or one. The values are distinguished by voltage differences in transistors. Quantum computers are instead based on quantum bits, or qubits, that are represented physically by something that exhibits quantum properties, like for example electrons. Qubits also take on the value zero or one, which could correspond to spin up and spin down of an electron. However, qubits can also be in a superposition state between the quantum states corresponding to the value zero and one. This property is what causes quantum computers to be able to outperform classical computers at certain tasks. One of these tasks is searching through an unstructured database. Whereas a classical computer in the worst case has to search through the whole database in order to find the sought element, i.e. the computation time is proportional to the size of the problem, it can be shown that a quantum computer can find the solution in a time proportional to the square root of the size of the problem. This report aims to illustrate the advantages of quantum computing by explicitly solving the classical Windows game Minesweeper, which can be reduced to a problem resembling the unstructured database search problem. It is shown that solving Minesweeper with a quantum algorithm gives a quadratic speedup compared to solving it with a classical algorithm. The report also covers introductory material to quantum mechanics, quantum gates, the particular quantum algorithm Grover's algorithm and complexity classes, which is necessary to grasp in order to understand how Minesweeper can be solved on a quantum computer.