Semidefinite programming hierarchies for constrained bilinear optimization

• Published in: Mathematical programming 2022-07, Vol.194 (1-2), p.781-829
• Main Authors: Berta, Mario, Borderi, Francesco, Fawzi, Omar, Scholz, Volkher B.
• Format: Article
• Language: English
• Subjects: Approximation; Asymptotic methods; Asymptotic properties; Atoms; Calculus of Variations and Optimal Control; Optimization; Channels; Combinatorics; Computational geometry; Constraints; Convergence; Convexity; Error correction; Error correction & detection; Error-correcting codes; Full Length Paper; Hierarchies; Information theory; Mathematical and Computational Physics; Mathematical Methods in Physics; Mathematics; Mathematics and Statistics; Mathematics of Computing; Numerical Analysis; Optimization; Physics; Quantum computing; Quantum phenomena; Quantum Physics; Semidefinite programming; Theorems; Theoretical
• ISSN: 0025-5610; 1436-4646
• DOI: 10.1007/s10107-021-01650-1

We give asymptotically converging semidefinite programming hierarchies of outer bounds on bilinear programs of the form Tr [ H ( D ⊗ E ) ] , maximized with respect to semidefinite constraints on D and E . Applied to the problem of approximate error correction in quantum information theory, this gives hierarchies of efficiently computable outer bounds on the success probability of approximate quantum error correction codes in any dimension. The first level of our hierarchies corresponds to a previously studied relaxation (Leung and Matthews in IEEE Trans Inf Theory 61(8):4486, 2015) and positive partial transpose constraints can be added 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 sum-of-squares 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 answer a question of Brandão and Harrow (Proceedings of the forty-fourth annual ACM symposium on theory of computing, STOC’12, p 307, 2012) by improving the approximation factor of de Finetti theorems with no symmetry from O ( d k / 2 ) to poly ( d , k ) , where d denotes local dimension and k the number of copies.