On the state of QUBO solving
accepted for publication
- It is regularly claimed that quantum computers will bring breakthrough progress in solving challenging combinatorial optimization problems relevant in practice. In particular, Quadratic Unconstrained Binary Optimization (QUBO) problems are said to be the model of choice for use in (adiabatic) quantum systems during the noisy intermediate- scale quantum (NISQ) era. Even the first commercial quantum-based systems are advertised to solve such problems. Theoretically, any Integer Program can be converted into a QUBO. In practice, however, there are some caveats, as even for problems that can be nicely modeled as a QUBO, this might not be the most effective way to solve them. We review the state of QUBO solving on digital and quantum computers and provide insights regarding current benchmark instances and modeling.
Additional Services
| Author: | Thorsten KochORCiD, Daniel Rehfeldt, Yuji Shinano |
|---|---|
| Document Type: | In Proceedings |
| Parent Title (English): | Operations Research Proceedings 2023 |
| Year of first publication: | 2023 |
