A Rigorous Quantum Framework for Inequality-Constrained and Multi-Objective Binary Optimization
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866911440687857664 |
|---|---|
| author | Egginger, Sebastian Kirova, Kristina Bruckner, Sonja Hillmich, Stefan Kueng, Richard |
| author_facet | Egginger, Sebastian Kirova, Kristina Bruckner, Sonja Hillmich, Stefan Kueng, Richard |
| contents | Encoding combinatorial optimization problems into physically meaningful Hamiltonians with tractable energy landscapes forms the foundation of quantum optimization. Numerous works have studied such efficient encodings for the class of Quadratic Unconstrained Binary Optimization (QUBO) problems. However, many real-world tasks are constrained, and handling equality and, in particular, inequality constraints on quantum computers remains a major challenge. In this letter, we show that including inequality constraints is equivalent to solving a multi-objective optimization. This insight motivates the Multi-Objective Quantum Approximation (MOQA) framework, which approximates the maximum via smaller $p$-norms and comes with rigorous performance guarantees. MOQA operates directly at the Hamiltonian level and is compatible with, but not restricted to, ground-state solvers such as quantum adiabatic annealing, the Quantum Approximate Optimization Algorithm (QAOA), or imaginary-time evolution. Moreover, it is not limited to quadratic functions. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_13983 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Rigorous Quantum Framework for Inequality-Constrained and Multi-Objective Binary Optimization Egginger, Sebastian Kirova, Kristina Bruckner, Sonja Hillmich, Stefan Kueng, Richard Quantum Physics Encoding combinatorial optimization problems into physically meaningful Hamiltonians with tractable energy landscapes forms the foundation of quantum optimization. Numerous works have studied such efficient encodings for the class of Quadratic Unconstrained Binary Optimization (QUBO) problems. However, many real-world tasks are constrained, and handling equality and, in particular, inequality constraints on quantum computers remains a major challenge. In this letter, we show that including inequality constraints is equivalent to solving a multi-objective optimization. This insight motivates the Multi-Objective Quantum Approximation (MOQA) framework, which approximates the maximum via smaller $p$-norms and comes with rigorous performance guarantees. MOQA operates directly at the Hamiltonian level and is compatible with, but not restricted to, ground-state solvers such as quantum adiabatic annealing, the Quantum Approximate Optimization Algorithm (QAOA), or imaginary-time evolution. Moreover, it is not limited to quadratic functions. |
| title | A Rigorous Quantum Framework for Inequality-Constrained and Multi-Objective Binary Optimization |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2510.13983 |