Semidefinite programming hierarchies for constrained bilinear optimization
Semidefinite programming hierarchies for constrained bilinear optimization
复制标题
约束双线性优化的半定规划层次结构
作者：
M. Berta;Francesco Borderi;Omar Fawzi;V. Scholz
We give asymptotically converging semidefinite programming hierarchies of outer bounds on bilinear programs of the form Tr[H(D⊗E)]documentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} egin{document}$${mathrm {Tr}}ig [H(Dotimes E)ig ]$$end{document}, 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(dk/2)documentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} egin{document}$$O(d^{k/2})$$end{document} to poly(d,k)documentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} egin{document}$${mathrm {poly}}(d,k)$$end{document}, where d denotes local dimension and k the number of copies.
We give asymptotically converging semidefinite programming hierarchies of outer bounds on bilinear programs of the form Tr[H(D⊗E)]documentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} egin{document}$${mathrm {Tr}}ig [H(Dotimes E)ig ]$$end{document}, 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(dk/2)documentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} egin{document}$$O(d^{k/2})$$end{document} to poly(d,k)documentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} egin{document}$${mathrm {poly}}(d,k)$$end{document}, where d denotes local dimension and k the number of copies.
影响因子：
8.6
作者：
F. Brandão;A. Harrow;J. Oppenheim;Sergii Strelchuk
通讯作者：
F. Brandão;A. Harrow;J. Oppenheim;Sergii Strelchuk
DOI：
10.1145/2488608.2488719
发表时间：
2013-06
期刊：
--
影响因子：
--
作者：
F. Brandão;A. Harrow
通讯作者：
F. Brandão;A. Harrow
影响因子：
2.4
作者：
F. Brandão;A. Harrow
通讯作者：
F. Brandão;A. Harrow