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.
- 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.
- 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.
- 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