Abstract We give asymptotically converging semidefinite programming hierarchies of outer bounds on bilinear programs of the form
Tr[H(D⊗E)] 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(dk/2) O ( d k / 2 ) to
poly(d,k) poly ( d , k ) , where d denotes local dimension and k the number of copies.
We derive converging hierarchies of efficiently computable semidefinite programming outer bounds on the optimal fidelity for the transmission of quantum information over noisy quantum channels. Based on positive partial transpose conditions we give a sufficient criterion for the exact convergence at any given level of the hierarchies. The worst case convergence speed of our hierarchies is quantified via positive semidefinite representable outer approximations on the set of separable Choi states, which are based on novel finite de Finetti theorems for quantum channels.
We study zero-error communication and exact simulation of quantum channels assisted by quantum no-signalling correlations. For a channel with Kraus operator space
K, we introduce a semidefinite programming parameter
Γ(K) that is exactly multiplicative under tensor products and upper-bounds
ΘNS(K), where
log2ΘNS(K)=C0,NS(K) and
C0,NS(K) denotes the asymptotic quantum no-signalling-assisted zero-error capacity. Among known upper bounds on
ΘNS given by semidefinite programs,
Γ is the tightest. We also prove that the previously introduced simulation lower bound
Σ−(K) is exactly multiplicative and satisfies
ΘNS(K)≤Γ(K)≤Σ−(K)≤Γ(K)2. Using this multiplicativity, we show that neither
S0,NS(K)=log2Σ−(K) nor its regularized extension
S0,NS(K)=limn→∞n−1log2Σ−(K⊗n) holds in general. This answers an open question about the asymptotic simulation cost
S0,NS(K). For classical-quantum channels, we obtain sharp bounds. If
r is the effective output dimension, then
ΘNS≤Γ≤(1+r1/2)ΘNS/2 and
Γ≤Σ−≤(1+r1/2)Γ/2. If
k is the minimum rank of the output support projections, then
Σ−/ΘNS≤[(1+r1/2)/(1+k1/2)]2, and this bound is sharp for every
1≤k≤r. Thus, we obtain the sharp bound
S0,NS−C0,NS≤2log2[(1+r1/2)/(1+k1/2)].
We study optimization programs given by a bilinear form over noncommutative variables subject to linear inequalities. Problems of this form include the entangled value of two-prover games, entanglement-assisted coding for classical channels, and quantum-proof randomness extractors. We introduce an asymptotically converging hierarchy of efficiently computable semidefinite programming (SDP) relaxations for this quantum optimization. This allows us to give upper bounds on the quantum advantage for all of these problems. Compared to previous work of Pironio, Navascués, and Acín [SIAM J. Optim., 20 (2010), pp. 2157--2180], our hierarchy has additional constraints. By means of examples, we illustrate the importance of these new constraints both in practice and for analytical properties. Moreover, this allows us to give a hierarchy of SDP outer approximations for the completely positive semidefinite cone introduced by Laurent and Piovesan.
Determining the optimal fidelity for the transmission of quantum information over noisy quantum channels is one of the central problems in quantum information theory. Recently, [Berta-Borderi-Fawzi-Scholz, Mathematical Programming, 2021] introduced an asymptotically converging semidefinite programming hierarchy of outer bounds for this quantity. However, the size of the semidefinite programs (SDPs) grows exponentially with respect to the level of the hierarchy, thus making their computation unscalable. In this work, by exploiting the symmetries in the SDP, we show that, for a fixed output dimension of the quantum channel, we can compute the SDP in time polynomial with respect to the level of the hierarchy and input dimension. As a direct consequence of our result, the optimal fidelity can be approximated with an accuracy of$\epsilon
in\mathrm {poly}(1/\epsilon, \text {input dimension})
time,comparedtothe\exp (1/\epsilon, \text {input dimension})$running time required for direct computation.
This thesis aims to improve our understanding of the structure of quantum entanglement and the limits of information processing with quantum systems. It presents new results relevant to three threads of quantum information: the theory of quantum entanglement, the communication capabilities of quantum channels, and the quantum zero-error information theory. \nIn the first part, we investigate the fundamental features of quantum entanglement and develop quantitative approaches to better exploit the power of entanglement. First, we introduce a computable and additive entanglement measure to quantify the amount of entanglement, which also plays an important role as the improved semidefinite programming (SDP) upper bound of distillable entanglement. Second, we show that the Rains bound is neither additive nor equal to the asymptotic relative entropy of entanglement. Third, we establish SDP lower bounds for the entanglement cost and demonstrate the irreversibility of asymptotic entanglement manipulation under positive-partial-transpose-preserving quantum operations, resolving a major open problem in quantum information theory. \nIn the second part, we develop a framework of semidefinite programs to evaluate the classical and quantum communication capabilities of quantum channels in both the non-asymptotic and asymptotic regimes. In particular, we establish the first general SDP strong converse bound on the classical capacity of an arbitrary quantum channel and give in particular the best known upper bound on the classical capacity of the amplitude damping channel. We further establish a finite resource analysis of classical communication over quantum erasure channels, including the first second-order expansion of classical capacity beyond entanglement-breaking channels. For quantum communication, we establish the best SDP-computable strong converse bound and refine it as the so-called max-Rains information. \nIn the third part, we investigate the quantum zero-error information theory. In contrast to the conventional Shannon theory, there is a very different-looking information theory when errors are required to be precisely zero, where the communication problem reduces to the analysis of the so-called confusability graph (noncommutative graph) of a classical channel (quantum channel). We develop an activated communication model and explore its novel properties. Notably, we separate the quantum Lovász number and the entanglement-assisted zero-error capacity, resolving an intriguing open problem in the area of zero-error information.