Comparing QUBO models for quantum annealing: integer encodings for permutation problems.
Saved in:
| Title: | Comparing QUBO models for quantum annealing: integer encodings for permutation problems. |
|---|---|
| Authors: | Codognet, Philippe1,2 (AUTHOR) codognet@is.s.u-tokyo.ac.jp |
| Source: | International Transactions in Operational Research. Jan2025, Vol. 32 Issue 1, p18-37. 20p. |
| Subjects: | Quadratic assignment problem, Quantum annealing, Magic squares, Modeling languages (Computer science), Constraint satisfaction |
| Abstract: | QUBO (quadratic unconstrained binary optimization) has become the modeling language for quantum annealing and quantum‐inspired annealing solvers. We present different approaches in QUBO for the magic square problem and the quadratic assignment problem (QAP), which can be modeled by linear equations and a permutation constraint over integer variables. Different ways of encoding integers by Booleans in QUBO amount to models, the implementation of which could have very different performance. Experiments performed on the Fixstars Amplify Annealer Engine, a quantum‐inspired annealing solver, show that, compared to the classical one‐hot encoding, using unary encoding for integers performs slightly better for the QAP and much better for magic square. [ABSTRACT FROM AUTHOR] |
| Copyright of International Transactions in Operational Research is the property of Wiley-Blackwell and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) | |
| Database: | Engineering Source |
|
Full text is not displayed to guests.
Login for full access.
|
|
| Abstract: | QUBO (quadratic unconstrained binary optimization) has become the modeling language for quantum annealing and quantum‐inspired annealing solvers. We present different approaches in QUBO for the magic square problem and the quadratic assignment problem (QAP), which can be modeled by linear equations and a permutation constraint over integer variables. Different ways of encoding integers by Booleans in QUBO amount to models, the implementation of which could have very different performance. Experiments performed on the Fixstars Amplify Annealer Engine, a quantum‐inspired annealing solver, show that, compared to the classical one‐hot encoding, using unary encoding for integers performs slightly better for the QAP and much better for magic square. [ABSTRACT FROM AUTHOR] |
|---|---|
| ISSN: | 09696016 |
| DOI: | 10.1111/itor.13471 |
