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 12 references indexed in Scilit:
- Black Box Optimization Using QUBO and the Cross Entropy Method2023
- Understanding domain-wall encoding theoretically and experimentallyPhilosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences, 2022
- Quantum annealing and computation: challenges and perspectivesPhilosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences, 2022
- Penalty and partitioning techniques to improve performance of QUBO solversDiscrete Optimization, 2022
- Performance Comparison of Typical Binary-Integer Encodings in an Ising MachineIEEE Access, 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
- Discrete optimization using quantum annealing on sparse Ising modelsFrontiers in Physics, 2014
- Ising formulations of many NP problemsFrontiers in Physics, 2014