  Information theory establishes the fundamental limits on data transmission,
storage, and processing. Quantum information theory unites information
theoretic ideas with an accurate quantum-mechanical description of reality to
give a more accurate and complete theory with new and more powerful
possibilities for information processing. The goal of both classical and
quantum information theory is to quantify the optimal rates of interconversion
of different resources. These rates are usually characterized in terms of
entropies. However, nonadditivity of many entropic formulas often makes finding
answers to information theoretic questions intractable. In a few auspicious
cases, such as the classical capacity of a classical channel, the capacity
region of a multiple access channel and the entanglement assisted capacity of a
quantum channel, additivity allows a full characterization of optimal rates.
Here we present a new mathematical property of entropic formulas, uniform
additivity, that is both easily evaluated and rich enough to capture all known
quantum additive formulas. We give a complete characterization of uniformly
additive functions using the linear programming approach to entropy
inequalities. In addition to all known quantum formulas, we find a new and
intriguing additive quantity: the completely coherent information. We also
uncover a remarkable coincidence---the classical and quantum uniformly additive
functions are identical; the tractable answers in classical and quantum
information theory are formally equivalent. Our techniques pave the way for a
deeper understanding of the tractability of information theory, from classical
multi-user problems like broadcast channels to the evaluation of quantum
channel capacities.
