Semidefinite programming hierarchies for constrained bilinear optimization

Abstract

We give asymptotically converging semidefinite programming hierarchies of outer bounds on bilinear programs of the form $\mathrm{Tr}[M(X\otimes Y)]$, 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

References in corpus (10)

• A complete family of separability criteria
• Post-selection technique for quantum channels with applications to quantum cryptography
• One-and-a-half quantum de Finetti theorems
• Optimizing quantum process tomography with unitary 2-designs
• Optimum Quantum Error Recovery using Semidefinite Programming
• Structured Near-Optimal Channel-Adapted Quantum Error Correction
• Quantum Error Correction via Convex Optimization
• Extendibility limits the performance of quantum processors
• Finite de Finetti theorem for conditional probability distributions describing physical theories
• Jointly constrained semidefinite bilinear programming with an application to Dobrushin curves

Cited by in corpus (22)

• Semidefinite programming relaxations for quantum correlations
• Resource theory of unextendibility and non-asymptotic quantum capacity
• Dimension-free entanglement detection in multipartite Werner states
• The $2T$-qutrit, a two-mode bosonic qutrit
• Quantifying the performance of approximate teleportation and quantum error correction via symmetric two-PPT-extendibility
• Synergies Between Operations Research and Quantum Information Science
• Evolving Quantum Circuits
• Quantifying the unextendibility of entanglement
• Schrödinger as a Quantum Programmer: Estimating Entanglement via Steering
• Learning Properties of Quantum States Without the I.I.D. Assumption
• Computable entanglement cost under positive partial transpose operations
• Extendible quantum measurements and limitations on classical communication
• Quantum channel coding: Approximation algorithms and strong converse exponents
• Relative entropy bounds for sampling with and without replacement
• Witnessing environment dimension through temporal correlations
• Certifying nonlocal properties of noisy quantum operations
• Unextendible entanglement of quantum channels
• A de Finetti theorem for quantum causal structures
• Monogamy of highly symmetric states
• Classical communication cost of a bipartite quantum channel assisted by non-signalling correlations
• $k$-Positive Maps: New Characterizations and a Generation Method
• Structure of quantum measurements implementable with one round of classical communication