We correct an error in the proof of Theorem 11 in our paper “Approximate Degradable Quantum Channels”, IEEE Trans. Inf. Theory, vol. 63, no. 12, pp. 7832-7844, 2017, concerning an upper bound on the private capacity of an approximate anti-degradable channel. Furthermore, we show how to obtain a tighter bound for the quantum capacity.

The capacity of noisy quantum channels characterizes the highest rate at which information can be reliably transmitted and it is therefore of practical as well as fundamental importance. Capacities of classical channels are computed using alternating optimization schemes, called Blahut-Arimoto algorithms. In this work, we generalize classical Blahut-Arimoto algorithms to the quantum setting. In particular, we give efficient iterative schemes to compute the capacity of channels with classical input and quantum output, the quantum capacity of less noisy channels, the thermodynamic capacity of quantum channels, as well as the entanglement-assisted capacity of quantum channels. We give rigorousa priorianda posterioribounds on the estimation error by employing quantum entropy inequalities and demonstrate fast convergence of our algorithms in numerical experiments.

We generalize alternating optimization algorithms of Blahut-Arimoto type to the quantum setting. In particular, we give iterative algorithms to compute the mutual information of quantum channels, the thermodynamic capacity of quantum channels, the coherent information of less noisy quantum channels, and the Holevo quantity of classical-quantum channels. Our convergence analysis is based on quantum entropy inequalities and leads to a priori additive ε-approximations after O (ε-1log N) iterations, where N denotes the input dimension of the channel. We complement our analysis with an a posteriori stopping criterion which allows us to terminate the algorithm after significantly fewer iterations compared to the a priori criterion in numerical examples. Finally, we discuss heuristics to accelerate the convergence.

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.

Quantum-proof randomness extractors are an important building block for classical and quantum cryptography as well as device independent randomness amplification and expansion. Furthermore, they are also a useful tool in quantum Shannon theory. It is known that some extractor constructions are quantum-proof whereas others are provably not [Gavinsky et al., STOC'07]. We argue that the theory of operator spaces offers a natural framework for studying to what extent extractors are secure against quantum adversaries: we first phrase the definition of extractors as a bounded norm condition between normed spaces, and then show that the presence of quantum adversaries corresponds to a completely bounded norm condition between operator spaces. From this, we show that very high min-entropy extractors as well as extractors with small output are always (approximately) quantum-proof. We also study a generalization of extractors called randomness condensers. We phrase the definition of condensers as a bounded norm condition and the definition of quantum-proof condensers as a completely bounded norm condition. Seeing condensers as bipartite graphs, we then find that the bounded norm condition corresponds to an instance of a well-studied combinatorial problem, called bipartite densest subgraph. Furthermore, using the characterization in terms of operator spaces, we can associate to any condenser a Bell inequality (two-player game), such that classical and quantum strategies are in one-to-one correspondence with classical and quantum attacks on the condenser. Hence, we get for every quantum-proof condenser (which includes in particular quantum-proof extractors) a Bell inequality that cannot be violated by quantum mechanics.

Degradable quantum channels are an important class of completely positive trace-preserving maps. Among other properties, they offer a single-letter formula for the quantum and the private classical capacity and are characterized by the fact that a complementary channel can be obtained from the channel by applying a degrading channel. In this paper, we introduce the concept of approximate degradable channels, which satisfy this condition up to some finite ε ≥ 0. That is, there exists a degrading channel which upon composition with the channel is ε-close in the diamond norm to the complementary channel. We show that for any fixed channel the smallest such ε can be efficiently determined via a semidefinite program. Moreover, these approximate degradable channels also approximately inherit all other properties of degradable channels. As an application, we derive improved upper bounds to the quantum and private classical capacity for certain channels of interest in quantum communication.

We propose constellations of finitely-many coherent states for high-rate quantum and classical communication over the thermal noise Bosonic Gaussian channel. Our constructions are based on constellations for the classical additive white Gaussian noise (AWGN) channel, and we adapt the results of Wu and Verdú [Allerton 2010, pp. 620] for the AWGN to determine achievable rates of classical and quantum information transmission for the thermal noise channel. Several constellations allow classical rates approaching the classical capacity, recently determined by Giovannetti et al. [Nature Photonics 8, 796 (2014)], while in the quantum case the rates approach the Gaussian coherent information. The constellations can also be used for private transmission of classical information at the coherent information rate.

Degradable quantum channels are an important class of completely positive trace-preserving maps. Among other properties, they offer a single-letter formula for the quantum and the private classical capacity and are characterized by the fact that the complementary channel can be obtained from the channel by applying a degrading map. In this work we introduce the concept of approximate degradable channels, which satisfy this condition up to some finite ε ≥ 0. That is, there exists a degrading map which upon composition with the channel is ε-close in the diamond norm to the complementary channel. We show that for any fixed channel the smallest such ε can be efficiently determined via a semidefinite program. Moreover, these approximate degradable channels also approximately inherit all other properties of degradable channels. As an application, we derive improved upper bounds to the quantum and private classical capacity for certain channels of interest in quantum communication.

Many constructions of randomness extractors are known to work in the presence of quantum side information, but there also exist extractors which do not [Gavinsky et al., STOC'07]. Here we find that spectral extractors with a bound on the second largest eigenvalue - considered as an operator on the Hilbert-Schmidt class - are quantum-proof. We then discuss fully quantum extractors and call constructions that also work in the presence of quantum correlations decoupling. As in the classical case we show that spectral extractors are decoupling. The drawback of classical and quantum spectral extractors is that they always have a long seed, whereas there exist classical extractors with exponentially smaller seed size. For the quantum case, we show that there exists an extractor with extremely short seed size d = O(log(1/ε)), where ε > 0 denotes the quality of the randomness. In contrast to the classical case this is independent of the input size and min-entropy and matches the simple lower bound d ≥ log(1/ε).