Alleviating the quantum Big-M problem
Abstract A major obstacle for quantum optimizers is the reformulation of constraints as a quadratic unconstrained binary optimization (QUBO). Current QUBO translators exaggerate the weight M of the penalty terms. Classically known as the “Big-M” problem, the issue becomes even more daunting for quan...
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Nature Portfolio
2025-07-01
|
| Series: | npj Quantum Information |
| Online Access: | https://doi.org/10.1038/s41534-025-01067-0 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1849332218228375552 |
|---|---|
| author | Edoardo Alessandroni Sergi Ramos-Calderer Ingo Roth Emiliano Traversi Leandro Aolita |
| author_facet | Edoardo Alessandroni Sergi Ramos-Calderer Ingo Roth Emiliano Traversi Leandro Aolita |
| author_sort | Edoardo Alessandroni |
| collection | DOAJ |
| description | Abstract A major obstacle for quantum optimizers is the reformulation of constraints as a quadratic unconstrained binary optimization (QUBO). Current QUBO translators exaggerate the weight M of the penalty terms. Classically known as the “Big-M” problem, the issue becomes even more daunting for quantum solvers, since it affects the physical energy scale. We take a systematic, encompassing look at the quantum big-M problem, revealing NP-hardness in finding the optimal M and establishing bounds on the Hamiltonian spectral gap Δ as a function of the weight M, inversely related to the expected run-time of quantum solvers. We propose a practical translation algorithm, based on SDP relaxation, that outperforms previous methods in numerical benchmarks. Our algorithm gives values of Δ orders of magnitude greater, e.g. for portfolio optimization instances. Solving such instances with an adiabatic algorithm on 6-qubits of an IonQ device, we observe significant advantages in time to solution and average solution quality. Our findings are relevant to quantum and quantum-inspired solvers alike. |
| format | Article |
| id | doaj-art-78db042a0e1b42d79f04ad6bbb024c67 |
| institution | Kabale University |
| issn | 2056-6387 |
| language | English |
| publishDate | 2025-07-01 |
| publisher | Nature Portfolio |
| record_format | Article |
| series | npj Quantum Information |
| spelling | doaj-art-78db042a0e1b42d79f04ad6bbb024c672025-08-20T03:46:16ZengNature Portfolionpj Quantum Information2056-63872025-07-011111910.1038/s41534-025-01067-0Alleviating the quantum Big-M problemEdoardo Alessandroni0Sergi Ramos-Calderer1Ingo Roth2Emiliano Traversi3Leandro Aolita4Quantum Research Centre, Technology Innovation Institute (TII)Quantum Research Centre, Technology Innovation Institute (TII)Quantum Research Centre, Technology Innovation Institute (TII)Department of Information Systems, Data Analytics and Operations, ESSEC Business SchoolQuantum Research Centre, Technology Innovation Institute (TII)Abstract A major obstacle for quantum optimizers is the reformulation of constraints as a quadratic unconstrained binary optimization (QUBO). Current QUBO translators exaggerate the weight M of the penalty terms. Classically known as the “Big-M” problem, the issue becomes even more daunting for quantum solvers, since it affects the physical energy scale. We take a systematic, encompassing look at the quantum big-M problem, revealing NP-hardness in finding the optimal M and establishing bounds on the Hamiltonian spectral gap Δ as a function of the weight M, inversely related to the expected run-time of quantum solvers. We propose a practical translation algorithm, based on SDP relaxation, that outperforms previous methods in numerical benchmarks. Our algorithm gives values of Δ orders of magnitude greater, e.g. for portfolio optimization instances. Solving such instances with an adiabatic algorithm on 6-qubits of an IonQ device, we observe significant advantages in time to solution and average solution quality. Our findings are relevant to quantum and quantum-inspired solvers alike.https://doi.org/10.1038/s41534-025-01067-0 |
| spellingShingle | Edoardo Alessandroni Sergi Ramos-Calderer Ingo Roth Emiliano Traversi Leandro Aolita Alleviating the quantum Big-M problem npj Quantum Information |
| title | Alleviating the quantum Big-M problem |
| title_full | Alleviating the quantum Big-M problem |
| title_fullStr | Alleviating the quantum Big-M problem |
| title_full_unstemmed | Alleviating the quantum Big-M problem |
| title_short | Alleviating the quantum Big-M problem |
| title_sort | alleviating the quantum big m problem |
| url | https://doi.org/10.1038/s41534-025-01067-0 |
| work_keys_str_mv | AT edoardoalessandroni alleviatingthequantumbigmproblem AT sergiramoscalderer alleviatingthequantumbigmproblem AT ingoroth alleviatingthequantumbigmproblem AT emilianotraversi alleviatingthequantumbigmproblem AT leandroaolita alleviatingthequantumbigmproblem |