From Table Constraints to QUBO Models for Quantum Annealing

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

Philippe Codognet

We present experiments in solving constrained optimization and constraint satisfaction problems by means of Quantum Annealing in terms of QUBO (Quadratic Unconstrained Binary Optimization). We investigate different QUBO formulations for the encoding of integers into Booleans and for the encoding of the At-Most-One constraint, which is used in combinatorial problems requiring capacity constraints. We compare four different QUBO models and report experiments done on the D-Wave annealing computer and the "quantum-inspired" Fixstars Amplify Annealing Engine. For this, we consider a simple example taken from the domain of Constraint Satisfaction Problems (CSP), the N-queens problem, as its formulation involves multiple instances of the At-Most-One constraints.

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

Hadi Salloum, Сергей Савин, Yaroslav Aleksandrovich Kholodov +3 more

We study a proof-of-concept workflow that reformulates planar inverse kinematics (IK) for robotic manipulators as a Quadratic Unconstrained Binary Optimization (QUBO) using a linear binary discretization of joint angles and one-hot (big-M) constraints, and then solves the QUBO with quantum annealing on D-Wave hardware. We (i) define and report time-to-solution (TTS) rigorously, (ii) evaluate solution accuracy back in the original IK space via end-effector error and feasibility of one-hot constraints, and (iii) analyze embedding choices on Pegasus/Zephyr. On the tested two-link planar IK instances, Global Embedding on Zephyr uses fewer physical qubits and yields shorter access times than alternatives (see Tables 1,2), and a hybrid quantum-classical solver achieves lower TTS than classical QUBO baselines at larger Q sizes (see Figure 6). These results do not claim superiority over state-of-the-art continuous IK solvers; rather, they demonstrate that an IK-to-QUBO mapping can be executed on current quantum annealing systems with quantified accuracy and runtime, clarifying where such an approach may be useful as hardware improves.

Philippe Codognet

Philippe Codognet

Quantum Annealing 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). Quantum computers such as the D-Wave systems are indeed implementing those ideas in hardware, as well as "quantum-inspired" devices based on classical electronics such as Fujitsu’s Digital Annealing Unit. All those systems use the same modeling language: Quadratic Unconstrained Binary Optimization (QUBO). However, QUBO is a low-level language and for modeling combinatorial problems such as constraint satisfaction and constrained optimization problems, we need to introduce higher-level abstractions in order to define complex constraints.