Certified bounds on optimization problems in quantum theory
Abstract
Semidefinite relaxations of polynomial optimization have become a central tool for addressing the non-convex optimization problems over non-commutative operators that are ubiquitous in quantum information theory and, more in general, quantum physics. Yet, as these global relaxation methods are solved numerically, the bounds issued by the semidefinite solver can – and often do – exceed the global optimum, undermining their certifiability. To counter this issue, we introduce a framework for extracting rigorous certified bounds on non-commutative optimization problems from inexact numerical data, and apply it to several paradigmatic problems in quantum information theory. An extension to sparsity and symmetry-adapted semidefinite relaxations is also provided and compared to the general dense scheme. Our results establish rational post-processing as a practical route to reliable certification, pushing semidefinite optimization toward a certifiable standard for quantum information science.
Related
- Quantum lower bounds for convex optimization and real matrix-vector query problems
- Lower Bounds For Gradient-Free Convex Optimization And Convex-Concave Saddle-Point Problems
- Circuit Design Problems in Binary Polynomial Quantum Optimization
- Gaussian entanglement and quantum communication: geodesic optimization and multimode bounds
- Near-Optimal Quantum Lower Bounds for Convex Optimization via Fourier Rank
BibTeX
@article{naceur2026certified,
title = {{Certified bounds on optimization problems in quantum theory}},
author = {Younes Naceur and Jie Wang and Victor Magron and Antonio Acín},
journal = {Quantum},
year = {2026},
month = oct,
doi = {10.22331/q-2026-10-28-2254},
url = {https://quantum-journal.org/papers/q-2026-10-28-2254/},
note = {CC BY 4.0},
}
RIS
TY - JOUR
TI - Certified bounds on optimization problems in quantum theory
AU - Younes Naceur
AU - Jie Wang
AU - Victor Magron
AU - Antonio Acín
PY - 2026
DA - 2026/10/28
JO - Quantum
DO - 10.22331/q-2026-10-28-2254
UR - https://quantum-journal.org/papers/q-2026-10-28-2254/
AB - Semidefinite relaxations of polynomial optimization have become a central tool for addressing the non-convex optimization problems over non-commutative operators that are ubiquitous in quantum information theory and, more in general, quantum physics. Yet, as these global relaxation methods are solved numerically, the bounds issued by the semidefinite solver can – and often do – exceed the global optimum, undermining their certifiability. To counter this issue, we introduce a framework for extracting rigorous certified bounds on non-commutative optimization problems from inexact numerical data, and apply it to several paradigmatic problems in quantum information theory. An extension to sparsity and symmetry-adapted semidefinite relaxations is also provided and compared to the general dense scheme. Our results establish rational post-processing as a practical route to reliable certification, pushing semidefinite optimization toward a certifiable standard for quantum information science.
SN - 2521-327X
ER -