As an alternative proposed more than 20 years ago to the main gate-based paradigm in Quantum Computing, Quantum Annealing has been gaining success in the last decade as a new approach for solving combinatorial problems, thanks to the development of quantum hardware such as D-Wave computers and “quantum-inspired” hardware (e.g., Fujitsu’s Digital Annealing Unit) which makes it possible to experiment on a variety of abstract or real-life problems. In the Quantum Annealing paradigm, combinatorial optimization problems can be described by Ising models and Ising Hamiltonians, the ground states of which correspond to the minimal solutions of the original problem. Interestingly, Ising models are equivalent to formulations in Quadratic Unconstrained Binary Optimization (QUBO). QUBO has become the standard input language for all quantum and quantum-inspired annealing hardware and is essential in developing the use of quantum computers for solving combinatorial problems. Many problems in AI can be formalized as combinatorial search problems and, thus, could be modeled in QUBO and solved by quantum annealing or quantum-inspired annealing techniques. Quantum annealing is therefore a new way to use the power of quantum computers to solve AI problems, a domain that will grow in size in the coming years as quantum technology is becoming more and more mature.

We will present in this tutorial how constrained optimization problems and constraint satisfaction problems can be modeled in QUBO and solved by quantum annealing, with the help of several examples. After introducing the basic concepts of quantum annealing, QUBO, CSPs and constrained optimization problems, we will first present several encoding schemes for integer variables and basic constraints in QUBO, with various concrete examples. Then we will detail how to encode more complex constraints such as linear equations and non-linear constraints, such as for instance the “permutation/all-different” constraint. We will describe QUBO models for well-known constraint problems such as N-queens, Magic Square, Costas Arrays, as well as for constrained optimization problems such as the travelling Salesman Problem (TSP) and the Quadratic Assignment Problem (QAP).

1. Quantum Computing: Basic notions

2. Introduction to Quantum Annealing

3. QUBO – Quadratic Unconstrained Binary Optimization

4. Constrained Optimization and Constraint Solving in QUBO

5. Examples & Experiments

Presenter: 

Philippe CODOGNET,     JFLI   – CNRS /      Sorbonne University / University of Tokyo