The sum-of-squares hierarchy on the sphere and applications in quantum information theory
From MaRDI portal
Publication:2235150
DOI10.1007/S10107-020-01537-7zbMATH Open1478.90077arXiv1908.05155OpenAlexW2968911711MaRDI QIDQ2235150FDOQ2235150
Authors: Kun Fang, Hamza Fawzi 
Publication date: 20 October 2021
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Abstract: We consider the problem of maximizing a homogeneous polynomial on the unit sphere and its hierarchy of Sum-of-Squares (SOS) relaxations. Exploiting the polynomial kernel technique, we obtain a quadratic improvement of the known convergence rate by Reznick and Doherty & Wehner. Specifically, we show that the rate of convergence is no worse than in the regime where is the level of the hierarchy and the dimension, solving a problem left open in the recent paper by de Klerk & Laurent (arXiv:1904.08828). Importantly, our analysis also works for matrix-valued polynomials on the sphere which has applications in quantum information for the Best Separable State problem. By exploiting the duality relation between sums of squares and the DPS hierarchy in quantum information theory, we show that our result generalizes to nonquadratic polynomials the convergence rates of Navascu'es, Owari & Plenio.
Full work available at URL: https://arxiv.org/abs/1908.05155
Recommendations
- Applying a generalization of Schur-Weyl duality to problems in quantum information and estimation
- Quantum entanglement, sum of squares, and the log rank conjecture
- A family of norms with applications in quantum information theory
- Quantum Orlicz Spaces in Information Geometry
- Quantum information metric on \(\mathbb{R} \times S^{d-1}\)
- A geometrization of quantum mutual information
- Quantumness, generalized spherical 2-design, and symmetric informationally complete POVM
- Convex geometry of quantum resource quantification
- Information geometry and the quantum estimation problem
- Some applications of hypercontractive inequalities in quantum information theory
Semidefinite programming (90C22) Entanglement measures, concurrencies, separability criteria (81P42) Polynomial optimization (90C23)
Cites Work
- A Survey of the S-Lemma
- Global optimization with polynomials and the problem of moments
- Uniform denominators in Hilbert's seventeenth problem
- On the Field of Values of a Matrix
- Title not available (Why is that?)
- Bounds for extreme zeros of some classical orthogonal polynomials
- Positive maps of low dimensional matrix algebras
- Polynomial optimization on odd-dimensional spheres
- Classical deterministic complexity of Edmonds' Problem and quantum entanglement
- Zeros of Gegenbauer and Hermite polynomials and connection coefficients
- On the Equivalence of Algebraic Approaches to the Minimization of Forms on the Simplex
- The complexity of optimizing over a simplex, hypercube or sphere: a short survey
- Quantum information. An introduction to basic theoretical concepts and experiments
- One-and-a-half quantum de Finetti theorems
- A most compendious and facile quantum de Finetti theorem
- Quantum de Finetti theorems under local measurements with applications
- Convexity properties of the cone of nonnegative polynomials
- Testing product states, quantum Merlin-Arthur games and tensor optimization
- A quasipolynomial-time algorithm for the quantum separability problem
- Hypercontractivity, sum-of-squares proofs, and their applications
- Separability and distillability in composite quantum systems - a primer
- Extreme Eigenvalues of Toeplitz Matrices Associated with Certain Orthogonal Polynomials
- Quantum entanglement, sum of squares, and the log rank conjecture
- Remarks on the extreme eigenvalues of Toeplitz forms associated with orthogonal polynomials
Cited In (28)
- On the energy-constrained diamond norm and its application in quantum information theory
- Sum-of-squares certificates for maxima of random tensors on the sphere
- Homogenization for polynomial optimization with unbounded sets
- Homogeneous polynomials and spurious local minima on the unit sphere
- An inexact projected gradient method with rounding and lifting by nonlinear programming for solving rank-one semidefinite relaxation of polynomial optimization
- The moment-SOS hierarchy: applications and related topics
- Exponential Convergence of Sum-of-Squares Hierarchies for Trigonometric Polynomials
- Sum-of-Squares Hierarchies for Polynomial Optimization and the Christoffel--Darboux Kernel
- Real algebraic geometry with a view toward Koopman operator methods. Abstracts from the workshop held March 12--17, 2023
- Finite convergence of moment-SOS relaxations with nonreal radical ideals
- Near-optimal analysis of Lasserre's univariate measure-based bounds for multivariate polynomial optimization
- An effective version of Schmüdgen's Positivstellensatz for the hypercube
- Convergence analysis of a Lasserre hierarchy of upper bounds for polynomial minimization on the sphere
- Harmonic Hierarchies for Polynomial Optimization
- Degree Bounds for Putinar’s Positivstellensatz on the Hypercube
- Optimization on the Euclidean unit sphere
- On Łojasiewicz inequalities and the effective Putinar's Positivstellensatz
- Semidefinite programming hierarchies for constrained bilinear optimization
- Convergence rates for sums-of-squares hierarchies with correlative sparsity
- Sum-of-squares relaxations for polynomial min-max problems over simple sets
- A tight degree 4 sum-of-squares lower bound for the Sherrington-Kirkpatrick Hamiltonian
- Convergence rates of RLT and Lasserre-type hierarchies for the generalized moment problem over the simplex and the sphere
- Sum-of-squares hierarchies for binary polynomial optimization
- Sum-of-squares hierarchies for binary polynomial optimization
- On the effective Putinar's Positivstellensatz and moment approximation
- Optimality conditions for homogeneous polynomial optimization on the unit sphere
- Approximate real symmetric tensor rank
- Extremal cubics on the circle and the 2-sphere
This page was built for publication: The sum-of-squares hierarchy on the sphere and applications in quantum information theory
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2235150)
