On good encodings for quantum annealer and digital optimization solvers
Abstract Several optimization solvers inspired by quantum annealing have been recently developed, either running on actual quantum hardware or simulating it on traditional digital computers. Industry and academics look at their potential in solving hard combinatorial optimization problems. Formally,...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Nature Portfolio
2023-04-01
|
| Series: | Scientific Reports |
| Online Access: | https://doi.org/10.1038/s41598-023-32232-0 |
| _version_ | 1797850064694018048 |
|---|---|
| author | Alberto Ceselli Marco Premoli |
| author_facet | Alberto Ceselli Marco Premoli |
| author_sort | Alberto Ceselli |
| collection | DOAJ |
| description | Abstract Several optimization solvers inspired by quantum annealing have been recently developed, either running on actual quantum hardware or simulating it on traditional digital computers. Industry and academics look at their potential in solving hard combinatorial optimization problems. Formally, they provide heuristic solutions for Ising models, which are equivalent to quadratic unconstrained binary optimization (QUBO). Constraints on solutions feasibility need to be properly encoded. We experiment on different ways of performing such an encoding. As benchmark we consider the cardinality constrained quadratic knapsack problem (CQKP), a minimal extension of QUBO with one inequality and one equality constraint. We consider different strategies of constraints penalization and variables encoding. We compare three QUBO solvers: quantum annealing on quantum hardware (D-Wave Advantage), probabilistic algorithms on digital hardware and mathematical programming solvers. We analyze their QUBO resolution quality and time, and the persistence values extracted in the quantum annealing sampling process. Our results show that a linear penalization of CQKP inequality improves current best practice. Furthermore, using such a linear penalization, persistence values produced by quantum hardware in a generic way allow to match a specific CQKP metric from literature. They are therefore suitable for general purpose variable fixing in core algorithms for combinatorial optimization. |
| first_indexed | 2024-04-09T18:55:25Z |
| format | Article |
| id | doaj.art-e1266b8797fc46e2bfccb9d5c0399505 |
| institution | Directory Open Access Journal |
| issn | 2045-2322 |
| language | English |
| last_indexed | 2024-04-09T18:55:25Z |
| publishDate | 2023-04-01 |
| publisher | Nature Portfolio |
| record_format | Article |
| series | Scientific Reports |
| spelling | doaj.art-e1266b8797fc46e2bfccb9d5c03995052023-04-09T11:15:50ZengNature PortfolioScientific Reports2045-23222023-04-0113111010.1038/s41598-023-32232-0On good encodings for quantum annealer and digital optimization solversAlberto Ceselli0Marco Premoli1Department of Computer Science, Università degli Studi di MilanoDepartment of Computer Science, Università degli Studi di MilanoAbstract Several optimization solvers inspired by quantum annealing have been recently developed, either running on actual quantum hardware or simulating it on traditional digital computers. Industry and academics look at their potential in solving hard combinatorial optimization problems. Formally, they provide heuristic solutions for Ising models, which are equivalent to quadratic unconstrained binary optimization (QUBO). Constraints on solutions feasibility need to be properly encoded. We experiment on different ways of performing such an encoding. As benchmark we consider the cardinality constrained quadratic knapsack problem (CQKP), a minimal extension of QUBO with one inequality and one equality constraint. We consider different strategies of constraints penalization and variables encoding. We compare three QUBO solvers: quantum annealing on quantum hardware (D-Wave Advantage), probabilistic algorithms on digital hardware and mathematical programming solvers. We analyze their QUBO resolution quality and time, and the persistence values extracted in the quantum annealing sampling process. Our results show that a linear penalization of CQKP inequality improves current best practice. Furthermore, using such a linear penalization, persistence values produced by quantum hardware in a generic way allow to match a specific CQKP metric from literature. They are therefore suitable for general purpose variable fixing in core algorithms for combinatorial optimization.https://doi.org/10.1038/s41598-023-32232-0 |
| spellingShingle | Alberto Ceselli Marco Premoli On good encodings for quantum annealer and digital optimization solvers Scientific Reports |
| title | On good encodings for quantum annealer and digital optimization solvers |
| title_full | On good encodings for quantum annealer and digital optimization solvers |
| title_fullStr | On good encodings for quantum annealer and digital optimization solvers |
| title_full_unstemmed | On good encodings for quantum annealer and digital optimization solvers |
| title_short | On good encodings for quantum annealer and digital optimization solvers |
| title_sort | on good encodings for quantum annealer and digital optimization solvers |
| url | https://doi.org/10.1038/s41598-023-32232-0 |
| work_keys_str_mv | AT albertoceselli ongoodencodingsforquantumannealeranddigitaloptimizationsolvers AT marcopremoli ongoodencodingsforquantumannealeranddigitaloptimizationsolvers |