Sudoku at the Intersection of Classical and Quantum Computing

Abstract

Even when quantum computers are widely available, it is unlikely that we will simply use them to solve all our problems. Rather we would use each computer for the types of problems it is best suited for. Indeed some problems may have different elements favourable to each type of computation, in which case a natural question which arises is where to draw the line between classical and quantum computation. Of course quantum computing is still in its infancy and there is a myriad of obstacles to overcome before we get to this point. Most practical quantum computers built so far solve only the smallest of problems and are intended primarily as proofs of concept. Perhaps the exception to this rule is the quantum annealing architecture developed by D-Wave. In this paper we investigate how to solve Sudoku – a popular NPcomplete puzzle game – using the quantum annealing architecture developed by D-Wave. What makes this problem interesting is that because it is primarily designed for humans to solve, it is prone to solution through techniques of logical deduction, which can often be efficiently implemented on classical computers, yet because it is NP-complete, there are instances which remain very hard to solve whose solutions can only reasonably be found through search. This makes it an ideal candidate problem for solution by quantum annealing. We therefore use a hybrid quantum-classical approach which first applies basic logic simplifications to the Sudoku and then transforms what remains of the problem into a form solvable by D-Wave’s Chimera architecture. Due to various hardware limitations inherent in their machines, in particular low qubit numbers as well as limited connectivity and precision, there are a number of problems which must be overcome in the process of preparing a problem for solution by the quantum hardware. We discuss these problems and their solutions in detail.