  We propose an iterative method for approximating the capacity of
classical-quantum channels with a discrete input alphabet and a finite
dimensional output, possibly 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 $\varepsilon$-close estimate
to the capacity, the presented algorithm requires $O(\tfrac{(N \vee M) M^3
\log(N)^{1/2}}{\varepsilon})$, where $N$ denotes the input alphabet size and
$M$ the output dimension. We then generalize the method for the task of
approximating the capacity of classical-quantum channels with a bounded
continuous input alphabet and a finite dimensional output. For channels with a
finite dimensional quantum mechanical input and output, the idea of a universal
encoder allows us to approximate the Holevo capacity using the same method. In
particular, we show that the problem of approximating the Holevo capacity can
be reduced to a multidimensional integration problem. For families of quantum
channels fulfilling a certain assumption we show that the complexity to derive
an $\varepsilon$-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.
