Even if the debate is still going on whether quantum supremacy has already been achieved or not, it is clear that quantum computing will have a profound impact on computer science in the next 10 years. In the domains of combinatorial optimization and problem solving, which are ubiquitous in AI, the use of quantum computers to solve concrete problems has started to raise tremendous interest, in both the gate-based paradigm with the Quantum Approximate Optimization Algorithm and in the adiabatic computing paradigm with Quantum Annealing (QA). QA is an alternative type of computation in which problems are encoded in quantum Hamiltonians (energy functions) and quantum dynamics is used to find solutions (ground states of minimal energy). QA can be seen as derived from simulated annealing, but taking advantage of the quantum tunneling effect to overcome energy barriers and therefore escape local minima during the computation.
Quantum computers such as the D-Wave systems are implementing those ideas in hardware, as well as quantum-inspired devices based on classical electronics such as Fujitsu’s Digital Annealing Unit. From a programming point of view, the use of QA computers for solving combinatorial problems is getting easier by the general adoption of the Quadratic Unconstrained Binary Optimization (QUBO) formalism. QUBO has become a standard input language for all “Ising Machines” developed by D-Wave, NTT, Fujitsu, Hitachi, Toshiba, Fixstars Amplify and NEC. We will describe in this tutorial how constraint satisfaction and constrained optimization problems can be encoded in QUBO and solved by Quantum Annealing. This will be demonstrated with several non-trivial examples from the domains of Constraint Satisfaction Problems (N-queens, Magic Squares, Costas Arrays) and constrained Optimization (Traveling Salesman Problem, Quadratic Assignment Problem).
