Optimal bounds on the positivity of a matrix from a few moments

Abstract

In many contexts one encounters Hermitian operators $M$ on a Hilbert space whose dimension is so large that it is impossible to write down all matrix entries in an orthonormal basis. How does one determine whether such $M$ is positive semidefinite? Here we approach this problem by deriving asymptotically optimal bounds to the distance to the positive semidefinite cone in Schatten $p$-norm for all integer $p\in [1,\infty )$, assuming that we know the moments $\mathbf{tr}(M^k)$ up to a certain order $k=1,\dots ,m$. We then provide three methods to compute these bounds and relaxations thereof: the sos polynomial method (a semidefinite program), the Handelman method (a linear program relaxation), and the Chebyshev method (a relaxation not involving any optimization). We investigate the analytical and numerical performance of these methods and present a number of example computations, partly motivated by applications to tensor networks and to the theory of free spectrahedra.

arXiv comment2 Mathematica files are attached. v2: some typos corrected. v3: very close to published version

References in corpus (9)

• Efficient classical simulation of slightly entangled quantum computations
• A Practical Introduction to Tensor Networks: Matrix Product States and Projected Entangled Pair States
• Matrix Product Density Operators: Simulation of finite-T and dissipative systems
• A positive tensor network approach for simulating open quantum many-body systems
• Purifications of multipartite states: limitations and constructive methods
• Matrix product operators and states: NP-hardness and undecidability
• The matricial relaxation of a linear matrix inequality
• Fundamental limitations in the purifications of tensor networks
• Spectrahedral Containment and Operator Systems with Finite-Dimensional Realization

Cited by in corpus (3)

• Symmetry-resolved entanglement detection using partial transpose moments
• Optimal Entanglement Certification from Moments of the Partial Transpose
• Halos and undecidability of tensor stable positive maps