Note: This content is accessible to all versions of every browser. However, this browser does not seem to support current Web standards, preventing the display of our site's design details.


Efficient Approximation of Quantum Channel Capacities


D. Sutter, T. Sutter, P. Mohajerin Esfahani, R. Renner

IEEE Transactions on Information Theory, vol. 62, no. 1, pp. 578-598, (arXiv 1407.8202)


We propose an iterative method for approximating the capacity of classical-quantum channels with a discrete input alphabet and a finite-dimensional output under additional constraints on the input distribution. Based on duality of convex programming, we derive explicit upper and lower bounds for the capacity. To provide an additive epsilon-close estimate to the capacity, the presented algorithm requires O((N v M) M^3 log(N)^(1/2) epsilon^-1) steps, where N denotes the input alphabet size and M the output dimension. We then generalize the method to the task of approximating the capacity of classical-quantum channels with a bounded continuous input alphabet and a finite-dimensional output. This, using the idea of a universal encoder, allows us to approximate the Holevo capacity for channels with a finite-dimensional quantum mechanical input and output. In particular, we show that the problem of approximating the Holevo capacity can be reduced to a multi-dimensional integration problem. For certain families of quantum channels we prove that the complexity to derive an additive epsilon-close solution to the Holevo capacity is subexponential or even polynomial in the problem size. We provide several examples to illustrate the performance of the approximation scheme in practice.

Further Information

Type of Publication:


File Download:

Request a copy of this publication.
(Uses JavaScript)
% Autogenerated BibTeX entry
@Article { SutEtal:2016:IFA_4822,
    author={D. Sutter and T. Sutter and P. Mohajerin Esfahani and R. Renner},
    title={{Efficient Approximation of Quantum Channel Capacities}},
    journal={IEEE Transactions on Information Theory},
Permanent link