Mapping NP-hard and NP-complete optimisation problems to Quadratic Unconstrained Binary Optimisation problems
arXiv:1911.08043
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.
arXiv comment14 pages, 6 figures
References in corpus (7)
- Ising formulations of many NP problems
- A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
- Defining and detecting quantum speedup
- Anderson localization casts clouds over adiabatic quantum optimization
- A case study in programming a quantum annealer for hard operational planning problems
- Quantum Optimization of Fully-Connected Spin Glasses
- Does Adiabatic Quantum Optimization Truly Fail for NP-complete problems?