Certified bounds on optimization problems in quantum theory

Younes Naceur, Jie Wang, Victor Magron, Antonio AcínarXiv 2025 · DOI · arXiv

Certified bounds on optimization problems in quantum theory

Abstract

Quantum information theory frequently relies on Semidefinite Programming (SDP) to establish bounds on physical quantities, such as Bell inequality violations. However, standard numerical solvers utilize floating-point arithmetic, which can introduce rounding errors that compromise the mathematical rigor of the resulting bounds. This paper presents a framework for transforming numerical SDP outputs into exact, algebraically verifiable mathematical proofs using a "round-project-lift" procedure. By generating Sum-of-Hermitian-Squares (SOHS) certificates with rational coefficients, the authors provide certified bounds for Bell inequalities and many-body quantum systems, ensuring scientific validity in the presence of numerical imprecision.

Introduction

In the study of quantum systems, determining the fundamental limits of physical phenomena—such as the maximum violation of a Bell inequality or the ground-state energy of a many-body Hamiltonian—is a central task. These problems are often tackled using the Navascués-Pironio-Acín (NPA) hierarchy, which relaxes complex non-convex optimizations into a sequence of Semidefinite Programs (SDPs). While SDPs can be solved efficiently, the reliance on floating-point arithmetic in standard solvers poses a challenge for formal certification. A numerical bound that is even slightly lower than the true mathematical optimum is technically incorrect, potentially leading to false physical conclusions.

Methodology: The Round-Project-Lift Procedure

To bridge the gap between numerical efficiency and mathematical rigor, the authors propose a post-processing algorithm that converts approximate SDP outputs into rigorous Sum-of-Hermitian-Squares (SOHS) certificates. The core of the certification method is a three-step geometric transformation of the numerical Gram matrix $G_0$ obtained from an SDP solver.

Geometric representation of the three-step certification procedure: (1) rounding to rationals, (2) projection onto the affine subspace $\mathcal{L}$, and (3) lifting back into the positive-semidefinite (PSD) cone.
  1. Rounding: The floating-point numerical Gram matrix $G_0$ is converted into a rational matrix $\tilde{G}_0$. This step moves the solution into the domain of exact arithmetic but may initially violate the problem's constraints.
  2. Projection: The rational matrix $\tilde{G}_0$ is projected onto the affine subspace $\mathcal{L}$ defined by the equality constraints of the original physics problem. This "Frobenius-optimal" projection ensures the certificate corresponds to the intended physical model.
  3. Lifting: If the projection $\mathcal{P}(\tilde{G}_0)$ falls outside the positive-semidefinite (PSD) cone, it is no longer a valid certificate of positivity. The authors apply a "lifting" step, adding a calculated multiple of the identity matrix to push the solution back into the PSD cone. While this adds a small penalty to the final bound, it guarantees the bound's validity.

This framework is further optimized for sparse and symmetry-adapted hierarchies, which are essential for large-scale quantum simulations. The authors demonstrate that sparse rationalized bounds can actually be tighter than dense ones because the lifting penalty depends on the size of the matrix blocks.

Key Results

The authors evaluated their framework against several benchmarks, including the A2–A89 catalog of Bell inequalities and the J1–J2 Heisenberg chain.

  • Restoring Rigor: A critical finding was that numerical solvers frequently produce bounds that are slightly lower than the global optimum. For the A2-A89 inequalities, a significant portion of numerical results were found to be scientifically invalid without certification. For the standard CHSH inequality, the tool correctly adjusted a numerical bound of ~2.82842712 to a rational value strictly above $2\sqrt{2}$.
  • Many-Body Physics: The method successfully certified ground-state energy bounds for systems up to $N=50$ sites. Interestingly, the "bound shift" (the gap between numerical and certified values) decreased as the system size grew, suggesting the method scales gracefully for highly symmetric problems.
  • Interior Solutions: For degenerate problems where solvers terminate "inside" the feasible region, a secondary tightening technique was introduced to produce certified bounds that outperform raw numerical outputs.

Discussion and Future Work

The "round-project-lift" procedure provides a robust pathway for turning numerical approximations into formal mathematical proofs in quantum theory. While the use of rational arithmetic introduces computational overhead—as fractions with large numerators and denominators are slower to process—the ability to provide certified, rigorous bounds is indispensable for high-stakes physics. Future research may focus on more sophisticated lifting techniques and extending the framework to other optimization hierarchies, such as trace-optimization, to further minimize the gap between numerical results and certified bounds.

Summary updated

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 rely on floating-point methods, 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 rigorous framework for extracting exact rational bounds on non-commutative optimization problems from 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.
BibTeX
@misc{naceur2025certified,
  author = {Younes Naceur and Jie Wang and Victor Magron and Antonio Acín},
  title = {{Certified bounds on optimization problems in quantum theory}},
  year = {2025},
  eprint = {2512.17713},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2512.17713},
}
Figure