Semidefinite programming hierarchies for constrained bilinear optimization

Autor: Mario Berta, Omar Fawzi, Volkher B. Scholz, Francesco Borderi
Rok vydání: 2021
Předmět:
Convex hull
Technology
Operations Research
General Mathematics
Dimension (graph theory)
Mathematics
Applied
FOS: Physical sciences
Bilinear interpolation
Quantum error correction
De Finetti theorems
01 natural sciences
0102 Applied Mathematics
0103 physical sciences
Convergence (routing)
Semidefinite programming
0101 mathematics
010306 general physics
0802 Computation Theory and Mathematics
Mathematics
Discrete mathematics
Quantum Physics
Science & Technology
Operations Research & Management Science
0103 Numerical and Computational Mathematics
010102 general mathematics
Separability problem
State (functional analysis)
Computer Science
Software Engineering
Bilinear optimization
Product (mathematics)
Physical Sciences
Computer Science
Quantum Physics (quant-ph)
Software
Sum-of-squares hierarchies
Zdroj: Mathematical Programming. 194:781-829
ISSN: 1436-4646
0025-5610
Popis: We give asymptotically converging semidefinite programming hierarchies of outer bounds on bilinear programs of the form $\mathrm{Tr}\big[M(X\otimes Y)\big]$, maximized with respect to semidefinite constraints on $X$ and $Y$. Applied to the problem of quantum error correction this gives hierarchies of efficiently computable outer bounds on the optimal fidelity for any message dimension and error model. The first level of our hierarchies corresponds to the non-signalling assisted fidelity previously studied by [Leung & Matthews, IEEE Trans.~Inf.~Theory 2015], and positive partial transpose constraints can be added and used to give a sufficient criterion for the exact convergence at a given level of the hierarchy. To quantify the worst case convergence speed of our hierarchies, we derive novel quantum de Finetti theorems that allow imposing linear constraints on the approximating state. In particular, we give finite de Finetti theorems for quantum channels, quantifying closeness to the convex hull of product channels as well as closeness to local operations and classical forward communication assisted channels. As a special case this constitutes a finite version of Fuchs-Schack-Scudo's asymptotic de Finetti theorem for quantum channels. Finally, our proof methods also allow us to answer an open question from [Brand��o & Harrow, STOC 2013] by improving the approximation factor of de Finetti theorems with no symmetry from $O(d^{k/2})$ to $\mathrm{poly}(d,k)$, where $d$ denotes local dimension and $k$ the number of copies.
33 pages, New Title, v3
Databáze: OpenAIRE
Externí odkaz: