Mapping NP-hard and NP-complete optimisation problems to Quadratic Unconstrained Binary Optimisation problems

2019/11/18 by Bas Lodewijks, Lodewijks, Bas
Computer Science · Mathematics · Physics and Astronomy · #Advanced Optimization Algorithms Research #Commutative Algebra and Its Applications #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Physical sciences #Polynomial and algebraic computation #Quantum Computing Algorithms and Architecture #Quantum Physics (quant-ph) #Statistical Mechanics (cond-mat.stat-mech) #cond-mat.stat-mech #cs.CC #cs.DS #quant-ph

paper · pdf · doi:10.48550/arxiv.1911.08043

14 pages, 6 figures

openalex publication_date 2019/11/18 · arxiv created 2020/08/03 · arxiv updated 2020/08/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We discuss several mappings from well-known NP-hard problems to Quadratic Unconstrained Binary Optimisation problems which are treated incorrectly by Lucas. We provide counterexamples and correct the mappings. We also extend the body of QUBO formulations of NP-complete and NP-hard optimisation problems by discussing additional problems.

Related

• Logical and Inequality Implications for Reducing the Size and Complexity of Quadratic Unconstrained Binary Optimization Problems
• Quadratic Unconstrained Binary Optimization Problem Preprocessing: Theory and Empirical Analysis
• Computational Complexity of Quadratic Unconstrained Binary Optimization
• Constraint Programming to Discover One-Flip Local Optima of Quadratic Unconstrained Binary Optimization Problems
• How to Approximate any Objective Function via Quadratic Unconstrained Binary Optimization