Formalize Open Quantum Problem #10: Additivity of classical capacity and related problems

---
### What is the conjecture

This is problem [#10](https://oqp.iqoqi.oeaw.ac.at/additivity-of-classical-capacity-and-related-problems) in [Krüger–Werner’s snapshot of the Open Quantum Problems list](https://arxiv.org/abs/quant-ph/0504166) (see “Problem 10”), later maintained by a community of quantum researchers at the [Open Quantum Problems site](https://oqp.iqoqi.oeaw.ac.at/open-quantum-problems).

**Status:** this problem is listed as **solved** on the [Solved Quantum Problems](https://oqp.iqoqi.oeaw.ac.at/solved-quantum-problems) page (solved by M. Hastings). The original additivity conjecture is **false**: there exist finite-dimensional quantum channels `T1, T2` such that
`χ(T1 ⊗ T2) > χ(T1) + χ(T2)`
(i.e. entangled signal states across channel uses can strictly increase the achievable classical communication rate).

> **Problem (Open Quantum Problem #10: “Additivity of classical capacity and related problems”).**
> For each quantum channel `T` (Schrödinger picture), define the Holevo quantity
> `χ(T) = sup_{p, ρ} ( H(∑_i p_i T(ρ_i)) - ∑_i p_i H(T(ρ_i)) )`,
> where the supremum ranges over all finite ensembles of input states `ρ_i` with probabilities `p_i`, and `H` denotes the von Neumann entropy.
> Show that `χ(T1 ⊗ T2) = χ(T1) + χ(T2)`, or else give a counterexample.

Concretely / definitions:

* A (finite-dimensional) **quantum channel** is a completely positive trace-preserving (CPTP) linear map
`T : D(H_in) → D(H_out)`
on density operators.
* An **ensemble** is a finite collection `{(p_i, ρ_i)}` with `p_i ≥ 0`, `∑_i p_i = 1`, and each `ρ_i ∈ D(H_in)`.
* The **von Neumann entropy** is `H(σ) = -Tr(σ log σ)` (the log base only rescales capacities).

Why this matters (classical capacity):

* The (unassisted) **classical capacity** of a channel `T` is given by the regularized Holevo quantity (Holevo–Schumacher–Westmoreland theorem):
`C(T) = lim_{n→∞} (1/n) χ(T^{⊗ n})`.
* Since `χ` is always **superadditive** (`χ(T1 ⊗ T2) ≥ χ(T1) + χ(T2)`), additivity would imply the sought “single-letter” formula `C(T) = χ(T)` for all channels.
* Hastings’ counterexample shows that, in general, `C(T) > χ(T)` can occur, i.e. entanglement across multiple channel uses can strictly increase the optimal classical communication rate.

Related equivalent additivity problems (same “additivity conjecture family”):

* **Minimum output entropy**: `H_min(T) = min_ρ H(T(ρ))` and the conjecture `H_min(T1 ⊗ T2) = H_min(T1) + H_min(T2)`.
* **Entanglement of formation** additivity / strong superadditivity.
* Shor showed that the global versions of these conjectures are equivalent: they are either all true or all false.

Solved statement to formalize (negative answer):

* There exist finite-dimensional CPTP maps `T1, T2` such that
`χ(T1 ⊗ T2) > χ(T1) + χ(T2)`.
Hastings proved this via a randomized construction (channels built from Haar-random isometries / random unitary ensembles), giving a counterexample to additivity of minimum output entropy; by Shor’s equivalence this yields a counterexample to additivity of `χ`.

### Where to find the details / references

Primary sources:

* [Open Quantum Problems site (Problem #10)](https://oqp.iqoqi.oeaw.ac.at/additivity-of-classical-capacity-and-related-problems)
* [Solved Quantum Problems list (marks #10 as solved)](https://oqp.iqoqi.oeaw.ac.at/solved-quantum-problems)
* O. Krüger & R. F. Werner, “Some Open Problems in Quantum Information Theory” (Problem 10):
* https://arxiv.org/abs/quant-ph/0504166
* https://arxiv.org/pdf/quant-ph/0504166

Key background / equivalence references (mentioned on the OQP page or standard for the topic):

* A. S. Holevo, “The Capacity of the Quantum Channel with General Signal States” (1998), arXiv: quant-ph/9611023
* B. Schumacher & M. D. Westmoreland, “Sending classical information via noisy quantum channels” (Phys. Rev. A 56, 131 (1997))
* P. W. Shor, “Equivalence of additivity questions in quantum information theory” (2003), arXiv: quant-ph/0305035
* P. W. Shor, “Additivity of the classical capacity of entanglement-breaking quantum channels” (2002/2004), arXiv: quant-ph/0201149

Resolution / negative answer (counterexample):

* M. B. Hastings, “Superadditivity of communication capacity using entangled inputs” (Nature Physics 5, 255–257 (2009)), arXiv: 0809.3972
* (Optional exposition/simplification) F. G. S. L. Brandão & M. Horodecki, “On Hastings' counterexamples to the minimum output entropy additivity conjecture” (2009), arXiv: 0907.3210

### Prerequisites needed

* Finite-dimensional quantum mechanics: density matrices, tensor products, partial trace
* Quantum channels (CPTP maps) and Kraus/Stinespring representations
* Von Neumann entropy; basic properties (concavity, subadditivity, etc.)
* Holevo information / Holevo quantity; classical capacity definitions and regularization
* Basic convexity/optimization over ensembles
* (If formalizing the solution) concentration of measure / random matrix theory techniques used in Hastings-style randomized constructions

### [AMS categories](https://github.com/google-deepmind/formal-conjectures/labels?q=ams-)

* ams-81 (Quantum theory)
* ams-94 (Information and communication theory)
* ams-47 (Operator theory)

### Choose either option

* [ ] I plan on adding this conjecture to the repository
* [X] This issue is up for grabs: I would like to see this conjecture added by somebody else
---

Start with the stated negative additivity claim and the Hastings and Shor references; the payload names no repository file, test, or entry point. Done means adding a Lean formalization of the counterexample statement, with the required definitions and supporting results established or appropriately represented.

Written by the indexing model from the issue text.