Comparing QUBO Models of the Magic Square Problem for Quantum Annealing

Philippe Codognet

Abstract QUBO (quadratic unconstrained binary optimization) has become the modeling language for quantum annealing and quantum‐inspired annealing solvers. We present different approaches in QUBO for the magic square problem and the quadratic assignment problem (QAP), which can be modeled by linear equations and a permutation constraint over integer variables. Different ways of encoding integers by Booleans in QUBO amount to models, the implementation of which could have very different performance. Experiments performed on the Fixstars Amplify Annealer Engine, a quantum‐inspired annealing solver, show that, compared to the classical one‐hot encoding, using unary encoding for integers performs slightly better for the QAP and much better for magic square.

Vrinda Mehta, Hans A. De Raedt, Kristel F. L. Michielsen +1 more

Philippe Codognet

We present experiments in solving combinatorial optimization and constraint satisfaction problems by means of Quantum Annealing. We describe how to model classic constraint problems such as N-queens and Magic Square as well as hard combinatorial problems such as the Costas Array Problem or the Quadratic Assignment Problem in terms of QUBO (Quadratic Unconstrained Binary Optimization). QUBO is the input language of quantum computers based on quantum annealing such as the D-Wave systems and of the ”quantum-inspired” but classical devices such as Fujitsu’s Digital Annealing Unit or Hitachi’s CMOS Annealing Machine. We present preliminary results for solving these combinatorial optimization and constraint satisfaction problems by implementation on the D-Wave quantum computer.

Philippe Codognet, Éric Monfroy

Florian Richoux, Jean-François Baffier, Philippe Codognet

Darren M. Chitty, James Charles, Alberto Moraglio +1 more

Quantum computers are early-stage technology, but are progressing rapidly. Here, we compare metaheuristics with a quantum annealer (QA), a quantum computer tailored to solve combinatorial optimisation problems formulated as a Quadratic Unconstrained Binary Optimisation (QUBO) problem. Formulating non-trivial optimisation problems as QUBOs is a challenge, so it is to ensure that the direct comparison of classical and quantum search algorithms is conducted fairly. This paper illustrates the use of a streamlined methodology to derive a QUBO for a classical optimisation problem – the Steiner tree problem – and provides comprehensive experiments comparing D-WAVE pure QA and hybrid QA with classical methods including Simulated Annealing and Genetic Algorithms. We find that the pure QA suffers from considerable qubit noise but the hybrid QA is on a par with traditional methods.