  We work out a theory of approximate quantum error correction that allows us
to derive a general lower bound for the entanglement fidelity of a quantum
code. The lower bound is given in terms of Kraus operators of the quantum
noise. This result is then used to analyze the average error correcting
performance of codes that are randomly drawn from unitarily invariant code
ensembles. Our results confirm that random codes of sufficiently large block
size are highly suitable for quantum error correction. Moreover, employing a
lemma of Bennett, Shor, Smolin, and Thapliyal, we prove that random coding
attains information rates of the regularized coherent information.
