Alleviating the quantum Big-$M$ problem
| Autor: | Alessandroni, Edoardo, Ramos-Calderer, Sergi, Roth, Ingo, Traversi, Emiliano, Aolita, Leandro |
|---|---|
| Rok vydání: | 2023 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | 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 $\Delta$, 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 $\Delta$ 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. Comment: 11 pages, 3 figures |
| Databáze: | arXiv |
| Externí odkaz: |
|