Penalty and partitioning techniques to improve performance of QUBO solvers
Discrete Optimization · 2022-05 · 44 · 100594
DOI: 10.1016/j.disopt.2020.100594 ↗Kurz gefasst
Fachartikel in der Zeitschrift Discrete Optimization, 2022-05. Verfasst von Amit Verma und 1 weiteren Autor:innen. Die Arbeit wurde bisher 75-mal zitiert (Crossref) und nennt 22 Literaturangaben.
Abstract (Originalsprache)
Quadratic Unconstrained Binary Optimization (QUBO) modeling has become a unifying framework for solving a wide variety of both unconstrained as well as constrained optimization problems. More recently, QUBO (or equivalent − 1 ∕ + 1 Ising Spin) models are a requirement for quantum annealing computers. Noisy Intermediate-Scale Quantum (NISQ) computing refers to classical computing preparing or compiling problem instances for compatibility with quantum hardware architectures. The process of converting a constrained problem to a QUBO compatible quantum annealing problem is an important part of the quantum compiler architecture and specifically when converting constrained models to unconstrained the choice of penalty magnitude is not trivial because using a large penalty to enforce constraints can overwhelm the solution landscape, while having too small a penalty allows infeasible optimal solutions. In this paper we present NISQ approaches to bound the magnitude of the penalty scalar M and demonstrate efficacy on a benchmark set of problems having a single equality constraint and present a QUBO partitioning approach validated by experimentation.
Zitieren
APA
Verma, A., & Lewis, M. (2022). Penalty and partitioning techniques to improve performance of QUBO solvers. Discrete Optimization, 44, 100594. https://doi.org/10.1016/j.disopt.2020.100594
Vancouver
Verma A, Lewis M. Penalty and partitioning techniques to improve performance of QUBO solvers. Discrete Optimization. 2022;44:100594. doi:10.1016/j.disopt.2020.100594
BibTeX
@article{Verma2022,
author = {Verma, Amit and Lewis, Mark},
title = {Penalty and partitioning techniques to improve performance of QUBO solvers},
journal = {Discrete Optimization},
year = {2022},
volume = {44},
pages = {100594},
doi = {10.1016/j.disopt.2020.100594}
}
EUVIMED