One for All: Universal Quantum Conic Programming Framework for Hard-Constrained Combinatorial Optimization Problems
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866929571800023040 |
|---|---|
| author | Binkowski, Lennart Osborne, Tobias J. Schwiering, Marvin Schwonnek, René Ziegler, Timo |
| author_facet | Binkowski, Lennart Osborne, Tobias J. Schwiering, Marvin Schwonnek, René Ziegler, Timo |
| contents | We present a unified quantum-classical framework for addressing NP-complete constrained combinatorial optimization problems, generalizing the recently proposed Quantum Conic Programming (QCP) approach. Accordingly, it inherits many favorable properties of the original proposal such as mitigation of the effects of barren plateaus and avoidance of NP-hard parameter optimization. By collecting the entire classical feasibility structure in a single constraint, we enlarge QCP's scope to arbitrary hard-constrained problems. Yet, we prove that the additional restriction is mild enough to still allow for an efficient parameter optimization via the formulation of a generalized eigenvalue problem (GEP) of adaptable dimension. Our rigorous proof further fills some apparent gaps in prior derivations of GEPs from parameter optimization problems. We further detail a measurement protocol for formulating the classical parameter optimization that does not require us to implement any (time evolution with a) problem-specific objective Hamiltonian or a quantum feasibility oracle. Lastly, we prove that, even under the influence of noise, QCP's parameterized ansatz class always captures the optimum attainable within its generated subcone. All of our results hold true for arbitrarily-constrained combinatorial optimization problems. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_00435 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | One for All: Universal Quantum Conic Programming Framework for Hard-Constrained Combinatorial Optimization Problems Binkowski, Lennart Osborne, Tobias J. Schwiering, Marvin Schwonnek, René Ziegler, Timo Quantum Physics We present a unified quantum-classical framework for addressing NP-complete constrained combinatorial optimization problems, generalizing the recently proposed Quantum Conic Programming (QCP) approach. Accordingly, it inherits many favorable properties of the original proposal such as mitigation of the effects of barren plateaus and avoidance of NP-hard parameter optimization. By collecting the entire classical feasibility structure in a single constraint, we enlarge QCP's scope to arbitrary hard-constrained problems. Yet, we prove that the additional restriction is mild enough to still allow for an efficient parameter optimization via the formulation of a generalized eigenvalue problem (GEP) of adaptable dimension. Our rigorous proof further fills some apparent gaps in prior derivations of GEPs from parameter optimization problems. We further detail a measurement protocol for formulating the classical parameter optimization that does not require us to implement any (time evolution with a) problem-specific objective Hamiltonian or a quantum feasibility oracle. Lastly, we prove that, even under the influence of noise, QCP's parameterized ansatz class always captures the optimum attainable within its generated subcone. All of our results hold true for arbitrarily-constrained combinatorial optimization problems. |
| title | One for All: Universal Quantum Conic Programming Framework for Hard-Constrained Combinatorial Optimization Problems |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2411.00435 |