Certified bounds on optimization problems in quantum theory

Younes Naceur; Jie Wang; Victor Magron; Antonio Acín

doi:10.22331/q-2026-10-28-2254

Certified bounds on optimization problems in quantum theory

Younes Naceur^1,2, Jie Wang³, Victor Magron^2,4, and Antonio Acín^1,5

¹ICFO - Institut de Ciencies Fotoniques, The Barcelona Institute of Science and Technology, Av. Carl Friedrich Gauss 3, 08860 Castelldefels (Barcelona), Spain
²LAAS-CNRS - Laboratoire d’Analyse et d’Architecture des Systèmes, Centre National de la Recherche Scientifique, Toulouse, France
³State Key Laboratory of Mathematical Sciences, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing, China
⁴Institute of Mathematics, Toulouse, France
⁵ICREA - Institució Catalana de Recerca i Estudis Avançats, 08010 Barcelona, Spain

Published:	2026-10-28, volume 10, page 2254
Editor:	Mateus Araújo
Eprint:	arXiv:2512.17713v2
Doi:	https://doi.org/10.22331/q-2026-10-28-2254
Citation:	Quantum 10, 2254 (2026).

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.

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.

Popular summary

How strongly can quantum behavior differ from classical behavior? What properties can a quantum system have at its lowest energy? Answering such questions often requires finding bounds on what quantum physics allows. Powerful numerical optimization methods can estimate these bounds, but numerical methods work with finite precision and might yield invalidated bounds.

We introduce a practical method for turning numerical bounds on polynomial quantum optimization problems into mathematically exact certificates. Starting from an approximate solution, we enforce the required algebraic relations in exact arithmetic, and establish the exact certificate from the numerical one. The resulting certificate establishes a certified bound that can be checked using exact arithmetic.

We demonstrate the method on Bell inequalities and ground-state observables of quantum many-body systems, and extend it to calculations that exploit sparsity and symmetry. Our methods help bridge the gap between efficient numerical computation and reliable mathematical proof systems.

► BibTeX data

@article{Naceur2026certifiedbounds,
  doi = {10.22331/q-2026-10-28-2254},
  url = {https://doi.org/10.22331/q-2026-10-28-2254},
  title = {Certified bounds on optimization problems in quantum theory},
  author = {Naceur, Younes and Wang, Jie and Magron, Victor and Ac{\'{i}}n, Antonio},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {10},
  pages = {2254},
  month = oct,
  year = {2026}
}

► References

[1] Miguel Navascués, Stefano Pironio, and Antonio Acín. ``Bounding the set of quantum correlations''. Phys. Rev. Lett. 98, 010401 (2007).
https://doi.org/10.1103/PhysRevLett.98.010401

[2] Jie Wang, Jacopo Surace, Irénée Frérot, Benoı̂t Legat, Marc-Olivier Renou, Victor Magron, and Antonio Acín. ``Certifying ground-state properties of many-body systems''. Physical Review X 14, 031006 (2024).
https://doi.org/10.1103/physrevx.14.031006

[3] Mateus Araújo, Cyril Branciard, Fabio Costa, Adrien Feix, Christina Giarmatzi, and Časlav Brukner. ``Witnessing causal nonseparability''. New Journal of Physics 17, 102001 (2015).
https://doi.org/10.1088/1367-2630/17/10/102001

[4] Armin Tavakoli, Emmanuel Zambrini Cruzeiro, Roope Uola, and Alastair A. Abbott. ``Bounding and Simulating Contextual Correlations in Quantum Theory''. PRX Quantum 2, 020334 (2021).
https://doi.org/10.1103/PRXQuantum.2.020334

[5] Miguel Navascués, Stefano Pironio, and Antonio Acín. ``A convergent hierarchy of semidefinite programs characterizing the set of quantum correlations''. New Journal of Physics 10, 073013 (2008).
https://doi.org/10.1088/1367-2630/10/7/073013

[6] Stefano Pironio, Miguel Navascués, and Antonio Acín. ``Convergent relaxations of polynomial optimization problems with noncommuting variables''. SIAM Journal on Optimization 20, 2157–2180 (2010).
https://doi.org/10.1137/090760155

[7] Igor Klep, Victor Magron, and Janez Povh. ``Sparse noncommutative polynomial optimization''. Mathematical Programming 193, 789–829 (2022).
https://doi.org/10.1007/s10107-020-01610-1

[8] Jie Wang and Victor Magron. ``Exploiting term sparsity in noncommutative polynomial optimization''. Computational Optimization and Applications 80, 483–521 (2021).
https://doi.org/10.1007/s10589-021-00301-7

[9] Cordian Riener, Thorsten Theobald, Lina Jansson Andrén, and Jean B. Lasserre. ``Exploiting symmetries in SDP-relaxations for polynomial optimization''. Mathematics of Operations Research 38, 122–141 (2013).
https://doi.org/10.1287/moor.1120.0558

[10] Hamza Fawzi, Omar Fawzi, and Samuel O. Scalet. ``Certified algorithms for equilibrium states of local quantum Hamiltonians''. Nature Communications 15, 7394 (2024).
https://doi.org/10.1038/s41467-024-51592-3

[11] Mateus Araújo, Igor Klep, Andrew J. P. Garner, Tamás Vértesi, and Miguel Navascués. ``First-order optimality conditions for non-commutative optimization problems''. Foundations of Computational Mathematics (2026). arXiv:2311.18707.
https://doi.org/10.1007/s10208-026-09761-x
arXiv:2311.18707

[12] Sabine Burgdorf, Kristijan Cafuta, Igor Klep, and Janez Povh. ``The tracial moment problem and trace-optimization of polynomials''. Mathematical Programming 137, 557–578 (2013).
https://doi.org/10.1007/s10107-011-0505-8

[13] Igor Klep, Victor Magron, Jurij Volčič, and Jie Wang. ``State polynomials: positivity, optimization and nonlinear Bell inequalities''. Mathematical Programming 207, 645–691 (2024).
https://doi.org/10.1007/s10107-023-02024-5

[14] Mateus Araújo, Andrew J. P. Garner, and Miguel Navascues. ``Non-commutative optimization problems with differential constraints''. Quantum 10, 2169 (2026). arXiv:2408.02572.
https://doi.org/10.22331/q-2026-07-22-2169
arXiv:2408.02572

[15] Flavio Baccari, Christian Gogolin, Peter Wittek, and Antonio Acín. ``Verifying the output of quantum optimizers with ground-state energy lower bounds''. Phys. Rev. Res. 2, 043163 (2020).
https://doi.org/10.1103/PhysRevResearch.2.043163

[16] Bissan Ghaddar, Juan C. Vera, and Miguel F. Anjos. ``A dynamic inequality generation scheme for polynomial programming''. Mathematical Programming 156, 21–57 (2016).
https://doi.org/10.1007/s10107-015-0870-9

[17] Monique Laurent. ``Sums of squares, moment matrices and optimization over polynomials''. In Mihai Putinar and Seth Sullivant, editors, Emerging applications of algebraic geometry. Volume 149 of The IMA Volumes in Mathematics and its Applications, pages 157–270. Springer, New York, NY (2009).
https://doi.org/10.1007/978-0-387-09686-5_7

[18] J. W. Helton and Scott McCullough. ``A Positivstellensatz for non-commutative polynomials''. Transactions of the American Mathematical Society 356, 3721–3737 (2004).
https://doi.org/10.1090/s0002-9947-04-03433-6

[19] Andrew C. Doherty, Yeong-Cherng Liang, Ben Toner, and Stephanie Wehner. ``The quantum moment problem and bounds on entangled multi-prover games''. In Proceedings of the 2008 IEEE 23rd Annual Conference on Computational Complexity. Pages 199–210. CCC '08USA (2008). IEEE Computer Society.
https://doi.org/10.1109/CCC.2008.26

[20] Sabine Burgdorf, Igor Klep, and Janez Povh. ``Optimization of Polynomials in Non-Commuting Variables''. SpringerBriefs in Mathematics. Springer International Publishing. Cham (2016).
https://doi.org/10.1007/978-3-319-33338-0

[21] Victor Magron and Jie Wang. ``Sparse polynomial optimization: theory and practice''. World Scientific. (2023).
https://doi.org/10.1142/q0382

[22] Andrew C. Doherty, Pablo A. Parrilo, and Federico M. Spedalieri. ``Complete family of separability criteria''. Phys. Rev. A 69, 022308 (2004).
https://doi.org/10.1103/PhysRevA.69.022308

[23] Xiao-Dong Yu, Timo Simnacher, Nikolai Wyderka, H. Chau Nguyen, and Otfried Gühne. ``A complete hierarchy for the pure state marginal problem in quantum mechanics''. Nature Communications 12, 1012 (2021).
https://doi.org/10.1038/s41467-020-20799-5

[24] Marco Cattaneo, Matteo A. C. Rossi, Keijo Korhonen, Elsi-Mari Borrelli, Guillermo García-Pérez, Zoltán Zimborás, and Daniel Cavalcanti. ``Self-consistent quantum measurement tomography based on semidefinite programming''. Phys. Rev. Res. 5, 033154 (2023).
https://doi.org/10.1103/PhysRevResearch.5.033154

[25] Alejandro Pozas-Kerstjens, Rafael Rabelo, Łukasz Rudnicki, Rafael Chaves, Daniel Cavalcanti, Miguel Navascués, and Antonio Acín. ``Bounding the sets of classical and quantum correlations in networks''. Phys. Rev. Lett. 123, 140503 (2019).
https://doi.org/10.1103/PhysRevLett.123.140503

[26] Hirokazu Anai. ``On solving semidefinite programming by quantifier elimination''. RIMS Kôkyûroku 1038, 154–162 (1998). url: https://www.kurims.kyoto-u.ac.jp/ kyodo/kokyuroku/contents/pdf/1038-21.pdf.
https://www.kurims.kyoto-u.ac.jp/~kyodo/kokyuroku/contents/pdf/1038-21.pdf

[27] Christopher W. Brown and James H. Davenport. ``The complexity of quantifier elimination and cylindrical algebraic decomposition''. In Proceedings of the 2007 international symposium on Symbolic and algebraic computation. Pages 54–60. Waterloo Ontario Canada (2007). ACM.
https://doi.org/10.1145/1277548.1277557

[28] Yurii Nesterov and Arkadii Nemirovskii. ``Interior-point polynomial algorithms in convex programming''. Number 13 in SIAM Studies in Applied and Numerical Mathematics. SIAM. Philadelphia, Pa (1994).
https://doi.org/10.1137/1.9781611970791

[29] Victor Magron, Mohab Safey El Din, and Markus Schweighofer. ``Algorithms for weighted sum of squares decomposition of non-negative univariate polynomials''. Journal of Symbolic Computation 93, 200–220 (2019).
https://doi.org/10.1016/j.jsc.2018.06.005

[30] Victor Magron, Mohab Safey El Din, Markus Schweighofer, and Trung Hieu Vu. ``Exact SOHS decompositions of trigonometric univariate polynomials with Gaussian coefficients''. In Proceedings of the 2022 International Symposium on Symbolic and Algebraic Computation. Pages 325–332. (2022).
https://doi.org/10.1145/3476446.3535480

[31] Przemysław Koprowski, Victor Magron, and Tristan Vaccon. ``Pourchet's theorem in action: decomposing univariate nonnegative polynomials as sums of five squares''. In Proceedings of the 2023 International Symposium on Symbolic and Algebraic Computation. Pages 425–433. (2023).
https://doi.org/10.1145/3597066.3597072

[32] Helfried Peyrl and Pablo A Parrilo. ``Computing sum of squares decompositions with rational coefficients''. Theoretical Computer Science 409, 269–281 (2008).
https://doi.org/10.1016/j.tcs.2008.09.025

[33] Erich L. Kaltofen, Bin Li, Zhengfeng Yang, and Lihong Zhi. ``Exact certification in global polynomial optimization via sums-of-squares of rational functions with rational coefficients''. Journal of Symbolic Computation 47, 1–15 (2012).
https://doi.org/10.1016/j.jsc.2011.08.002

[34] Victor Magron and Mohab Safey El Din. ``On exact Reznick, Hilbert-Artin and Putinar's representations''. Journal of Symbolic Computation 107, 221–250 (2021).
https://doi.org/10.1016/j.jsc.2021.03.005

[35] Victor Magron and Mohab Safey El Din. ``RealCertify: a Maple package for certifying non-negativity''. ACM Communications in Computer Algebra 52, 34–37 (2018).
https://doi.org/10.1145/3282678.3282681

[36] V. Magron, X. Allamigeon, S. Gaubert, and B. Werner. ``Formal proofs for Nonlinear Optimization''. Journal of Formalized Reasoning 8, 1–24 (2015). arXiv:1404.7282.
https://doi.org/10.6092/issn.1972-5787/4319
arXiv:1404.7282

[37] Antoine Oustry, Claudia d'Ambrosio, Leo Liberti, and Manuel Ruiz. ``Certified and accurate SDP bounds for the ACOPF problem''. Electric Power Systems Research 212, 108278 (2022).
https://doi.org/10.1016/j.epsr.2022.108278

[38] Jessica Bavaresco, Mio Murao, and Marco Túlio Quintino. ``Strict hierarchy between parallel, sequential, and indefinite-causal-order strategies for channel discrimination''. Phys. Rev. Lett. 127, 200504 (2021).
https://doi.org/10.1103/PhysRevLett.127.200504

[39] Victor Magron, Mohab Safey El Din, and Trung-Hieu Vu. ``Sum of squares decompositions of polynomials over their gradient ideals with rational coefficients''. SIAM Journal on Optimization 33, 63–88 (2023).
https://doi.org/10.1137/21M1436245

[40] Lorenzo Baldi, Teresa Krick, and Bernard Mourrain. ``An effective positivstellensatz over the rational numbers for finite semialgebraic sets''. Mathematics of Computation (2025).
https://doi.org/10.1090/mcom/4153

[41] Nando Leijenhorst and David de Laat. ``Solving clustered low-rank semidefinite programs arising from polynomial optimization''. Mathematical Programming Computation 16, 503–534 (2024).
https://doi.org/10.1007/s12532-024-00264-w

[42] Maho Nakata. ``A numerical evaluation of highly accurate multiple-precision arithmetic version of semidefinite programming solver: SDPA-GMP, -QD and -DD''. In Proceedings of the IEEE International Symposium on Computer-Aided Control System Design. Pages 29–34. (2010).
https://doi.org/10.1109/CACSD.2010.5612693

[43] Kristijan Cafuta, Igor Klep, and Janez Povh. ``Rational sums of hermitian squares of free noncommutative polynomials''. Ars Mathematica Contemporanea 9, 243–259 (2015).
https://doi.org/10.26493/1855-3974.518.768

[44] Fredrik Johansson. ``Arb: efficient arbitrary-precision midpoint-radius interval arithmetic''. IEEE Transactions on Computers 66, 1281–1292 (2017).
https://doi.org/10.1109/TC.2017.2690633

[45] MOSEK ApS. ``MOSEK optimizer api for Julia 11.0.30''. (2025). url: https://docs.mosek.com/11.0/juliaapi/index.html.
https://docs.mosek.com/11.0/juliaapi/index.html

[46] John F. Clauser, Michael A. Horne, Abner Shimony, and Richard A. Holt. ``Proposed experiment to test local hidden-variable theories''. Phys. Rev. Lett. 23, 880–884 (1969).
https://doi.org/10.1103/PhysRevLett.23.880

[47] Tsuyoshi Ito, Hiroshi Imai, and David Avis. ``Bell inequalities stronger than the clauser-horne-shimony-holt inequality for three-level isotropic states''. Phys. Rev. A 73, 042109 (2006).
https://doi.org/10.1103/PhysRevA.73.042109

[48] Timotej Hrga, Igor Klep, and Janez Povh. ``Certifying Optimality of Bell Inequality Violations: Noncommutative Polynomial Optimization through Semidefinite Programming and Local Optimization''. SIAM Journal on Optimization 34, 1341–1373 (2024).
https://doi.org/10.1137/22M1473340

[49] Károly F Pál and Tamás Vértesi. ``Quantum Bounds on Bell inequalities''. Physical Review A 79, 022120 (2009).
https://doi.org/10.1103/PhysRevA.79.022120

[50] Károly F. Pál and Tamás Vértesi. ``Maximal violation of a bipartite three-setting, two-outcome Bell inequality using infinite-dimensional quantum systems''. Phys. Rev. A 82, 022116 (2010).
https://doi.org/10.1103/PhysRevA.82.022116

[51] Antonio Acín, Serge Massar, and Stefano Pironio. ``Randomness versus nonlocality and entanglement''. Phys. Rev. Lett. 108, 100402 (2012).
https://doi.org/10.1103/PhysRevLett.108.100402

[52] Nicolas Gigena, Ekta Panwar, Giovanni Scala, Mateus Araújo, Máté Farkas, and Anubhav Chaturvedi. ``Self-testing tilted strategies for maximal loophole-free nonlocality''. npj Quantum Information 11, 82 (2025).
https://doi.org/10.1038/s41534-025-01029-6

[53] Alexander Weiße and Holger Fehske. ``Exact Diagonalization Techniques''. In Computational Many-Particle Physics. Pages 529–544. Springer Berlin Heidelberg (2008).
https://doi.org/10.1007/978-3-540-74686-7_18

[54] Dian Wu, Riccardo Rossi, Filippo Vicentini, Nikita Astrakhantsev, Federico Becca, Xiaodong Cao, Juan Carrasquilla, Francesco Ferrari, Antoine Georges, Mohamed Hibat-Allah, Masatoshi Imada, Andreas M. Läuchli, Guglielmo Mazzola, Antonio Mezzacapo, Andrew Millis, Javier Robledo Moreno, Titus Neupert, Yusuke Nomura, Jannes Nys, Olivier Parcollet, Rico Pohle, Imelda Romero, Michael Schmid, J. Maxwell Silvester, Sandro Sorella, Luca F. Tocchio, Lei Wang, Steven R. White, Alexander Wietek, Qi Yang, Yiqi Yang, Shiwei Zhang, and Giuseppe Carleo. ``Variational benchmarks for quantum many-body problems''. Science 386, 296–301 (2024).
https://doi.org/10.1126/science.adg9774

[55] J. Ignacio Cirac, David Pérez-García, Norbert Schuch, and Frank Verstraete. ``Matrix product states and projected entangled pair states: Concepts, symmetries, theorems''. Rev. Mod. Phys. 93, 045003 (2021).
https://doi.org/10.1103/RevModPhys.93.045003

[56] Jie Wang, David Jansen, Irénée Frérot, Marc-Olivier Renou, Victor Magron, and Antonio Acín. ``Scalable ground-state certification of quantum spin systems via structured noncommutative polynomial optimization''. SciPost Physics 21, 074 (2026). arXiv:2604.01555.
https://doi.org/10.21468/SciPostPhys.21.3.074
arXiv:2604.01555

[57] Chanchal K. Majumdar and Dipan K. Ghosh. ``On Next-Nearest-Neighbor Interaction in Linear Chain. I''. J. Math. Phys. 10, 1388–1398 (1969).
https://doi.org/10.1063/1.1664978

[58] Aharon Ben-Tal and Arkadi Nemirovski. ``Lectures on modern convex optimization: Analysis, algorithms, and engineering applications''. Society for Industrial and Applied Mathematics. (2001).
https://doi.org/10.1137/1.9780898718829

Cited by

[1] Gerard Anglès Munné and Felix Huber, "SDP bounds on quantum codes: rational certificates", arXiv:2603.19901, (2026).

[2] Younes Naceur and Llorenç Balada Gaggioli, "Reachability and optimal-time certificates for quantum control", arXiv:2606.24645, (2026).

[3] Artus Krohn-Grimberghe, "Exact certification of a positive-order Rényi additivity violation for an explicit channel pair", arXiv:2608.17376, (2026).

The above citations are from SAO/NASA ADS (last updated successfully 2026-10-28 14:35:44). The list may be incomplete as not all publishers provide suitable and complete citation data.

Could not fetch Crossref cited-by data during last attempt 2026-10-28 14:35:41: Could not fetch cited-by data for 10.22331/q-2026-10-28-2254 from Crossref. This is normal if the DOI was registered recently.

This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.