Semidefinite programming hierarchies for constrained bilinear optimization
arXiv:1810.12197 · doi:10.1007/s10107-021-01650-1
Abstract
We give asymptotically converging semidefinite programming hierarchies of outer bounds on bilinear programs of the form , maximized with respect to semidefinite constraints on and . 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 to , where denotes local dimension and the number of copies.
arXiv comment33 pages, New Title, v3
References in corpus (46)
- Quantum entanglement
- Mixed State Entanglement and Quantum Error Correction
- Distributed Entanglement
- Unknown Quantum States: The Quantum de Finetti Representation
- A complete family of separability criteria
- Everything You Always Wanted to Know About LOCC (But Were Afraid to Ask)
- Information Spectrum Approach to Second-Order Coding Rate in Channel Coding
- Distinguishing separable and entangled states
- Post-selection technique for quantum channels with applications to quantum cryptography
- Quantum Channel Capacity of Very Noisy Channels
- Quantum conditional mutual information and approximate Markov chains
- Sandwiched Rényi Divergence Satisfies Data Processing Inequality
- Approximate quantum error correction can lead to better codes
- One-and-a-half quantum de Finetti theorems
- Faithful Squashed Entanglement
- Hypercontractivity, Sum-of-Squares Proofs, and their Applications
- The Quantum Reverse Shannon Theorem based on One-Shot Information Theory
- Randomized Benchmarking with Confidence
- Operational criterion and constructive checks for the separability of low rank density matrices
- Convergent relaxations of polynomial optimization problems with non-commuting variables
- A de Finetti representation for finite symmetric quantum states
- Optimizing quantum process tomography with unitary 2-designs
- Optimum Quantum Error Recovery using Semidefinite Programming
- Iterative Optimization of Quantum Error Correcting Codes
- Correlation Detection and an Operational Interpretation of the Renyi Mutual Information
- Tema Con Variazioni: Quantum Channel Capacity
- On the power of PPT-preserving and non-signalling codes
- The power of symmetric extensions for entanglement detection
- Quantum Coding with Finite Resources
- Quantum Conditional Mutual Information, Reconstructed States, and State Redistribution
- Semidefinite programming strong converse bounds for classical capacity
- No-Signalling Assisted Zero-Error Capacity of Quantum Channels and an Information Theoretic Interpretation of the Lovasz Number
- Structured Near-Optimal Channel-Adapted Quantum Error Correction
- Quantum Error Correction via Convex Optimization
- A linear program for the finite block length converse of Polyanskiy-Poor-Verdú via non-signalling codes
- A de Finetti Representation Theorem for Quantum Process Tomography
- Extendibility limits the performance of quantum processors
- Distinguishing multi-partite states by local measurements
- Quantum Bilinear Optimization
- Channel-Optimized Quantum Error Correction
- Finite de Finetti theorem for conditional probability distributions describing physical theories
- A semidefinite programming upper bound of quantum capacity
- de Finetti reductions for correlations
- Algorithmic Aspects of Optimal Channel Coding
- Limitations of semidefinite programs for separable states and entangled games
- 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 -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
- -Positive Maps: New Characterizations and a Generation Method
- Structure of quantum measurements implementable with one round of classical communication