QUANTUM VS CLASSICAL SIMULATED ANNEALING FOR THE N-QUEENS PROBLEM

Abstract

ABSTRACT Classical and quantum solvers were implemented to compare their efficiency and scalability when solving the N-Queens problem with excluded diagonals. This problem is NP-complete (Nondeterministic Polynomial-complete), meaning it belongs to a class of problems for which solutions can be verified quickly, however, the time to find those solutions scales exponentially with the size of the board. The classical solver was implemented using FORTRAN, while D-Wave’s quantum computers implementing quantum annealing were used for the quantum solver. Additionally, a simulation of quantum annealing was performed for a very small search problem using Python. During quantum annealing, it is important to stay in the adiabatic regime to avoid jumping to the next energy level. Therefore, a review of the Landau-Zener formula was included. This formula explains the relationship between the anneal time and the distance between energy levels. The number of solutions to the N-Queens problem grows exponentially with the board size. Therefore, a more interesting variation is the N-Queens problem with excluded diagonals, which significantly reduces the number of solutions and is proven to be NP-complete. The classical solver was used to study the statistics of solution times and to classify and select problems based on the number of excluded diagonals and board sizes. The problems with the least number of solutions were used to test the quantum solver. This method was able to find solutions for boards up to size 10 × 10 with excluded diagonals. To find a solution the anneal time remains constant, while the embedding time grows exponentially. Embedding refers to the process of mapping the problem onto the QPU topology. Unfortunately, this embedding is also an NP search problem which until now, has to be solved with a classical algorithm. VII The hybrid solver provided by D-Wave was also studied. It demonstrated significantly greater capabilities, finding solutions for boards up to size 50×50 with excluded diagonals. This solver implements decomposition methods to break the problem into smaller, less dependent sub-problems, which require fewer qubits and connections. These sub-problems can then be solved with quantum annealing and recombined into a solution of the original problem. The results showed that quantum annealing could be a promising method since the anneal time does not grow with the problem size. But, current topologies still struggle to solve even relatively small problems. The hybrid solver, on the other hand, can solve much larger problems. However, for the N-Queens problem, the classical solver was still more efficient and could handle even larger problems. VIII