Discrete quadratic model QUBO solution landscapes
Preprint
Abstract
Many computational problems involve optimization over discrete variables with quadratic interactions. Known as discrete quadratic models (DQMs), these problems in general are NP-hard. Accordingly, there is increasing interest in encoding DQMs as quadratic unconstrained binary optimization (QUBO) models to allow their solution by quantum and quantum-inspired hardware with architectures and solution methods designed specifically for such problem types. However, converting DQMs to QUBO models often introduces invalid solutions to the solution space of the QUBO models. These solutions must be penalized by introducing appropriate constraints to the QUBO objective function that are weighted by a tunable penalty parameter to ensure that the global optimum is valid. However, selecting the strength of this parameter is non-trivial, given its influence on solution landscape structure. Here, we investigate the effects of choice of encoding and penalty strength on the structure of QUBO DQM solution landscapes and their optimization, focusing specifically on one-hot and domain-wall encodings.Keywords
All Related Versions
This publication has 19 references indexed in Scilit:
- Black Box Optimization Using QUBO and the Cross Entropy Method2023
- Ising machines as hardware solvers of combinatorial optimization problemsNature Reviews Physics, 2022
- Penalty and partitioning techniques to improve performance of QUBO solversDiscrete Optimization, 2022
- Prospects for quantum enhancement with diabatic quantum annealingNature Reviews Physics, 2021
- Effects of Quantum Noise on Quantum Approximate Optimization AlgorithmChinese Physics Letters, 2021
- Analog errors in quantum annealing: doom and hopenpj Quantum Information, 2019
- Domain wall encoding of discrete variables for quantum annealing and QAOAQuantum Science and Technology, 2019
- A transmon quantum annealer: decomposing many-body Ising constraints into pair interactionsQuantum Science and Technology, 2016
- Quantum annealing with manufactured spinsNature, 2011
- Towards a general theory of adaptive walks on rugged landscapesJournal of Theoretical Biology, 1987