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.