Closed-form nonadditivity of the Holevo capacity and entanglement of formation

Problem

Construct a simple closed-form or practically computable counterexample to additivity of the Holevo capacity or the entanglement of formation, together with a rigorous certificate of a strict violation.

For a density operator \(\rho\), write \(S(\rho)=-\operatorname{Tr}\rho\log_2\rho\). For a bipartite state \(\rho_{AB}\), the entanglement of formation is

\begin{equation} E_F(\rho_{AB})=\inf_{\{p_x,\psi_x\}}\ \sum_x p_x\, S\big(\operatorname{Tr}_B\lvert\psi_x\rangle\!\langle\psi_x\rvert\big), \tag{1} \end{equation}

where the infimum runs over pure-state ensembles with \(\sum_x p_x\lvert\psi_x\rangle\!\langle\psi_x\rvert=\rho_{AB}\); and for a channel \(\mathcal N\), the Holevo capacity is

\begin{equation} \chi(\mathcal N)=\sup_{\{p_x,\rho_x\}}\ \Big[ S\Big(\sum_x p_x\,\mathcal N(\rho_x)\Big)-\sum_x p_x\,S\big(\mathcal N(\rho_x)\big)\Big], \tag{2} \end{equation}

where the supremum runs over finite input ensembles. The target is at least one of the inequalities

\begin{equation} E_F(\rho\otimes\sigma)<E_F(\rho)+E_F(\sigma) \qquad\text{and}\qquad \chi(\mathcal N_1\otimes\mathcal N_2)>\chi(\mathcal N_1)+\chi(\mathcal N_2), \tag{3} \end{equation}

A solution must specify the finite states or channel operators completely, give their dimensions, and certify the corresponding inequality in (3) for the quantities defined in (1) and (2). For example, a certificate may combine rigorous one-copy bounds with an explicit two-copy input or ensemble. A simple closed-form construction must include a proof; a computational construction must include the actual instance and reproducible error bounds. An asymptotic algorithm or an existence proof alone does not supply such an instance. No universal upper bound on the witness dimensions is imposed.

The two formulations share the universal additivity equivalences discussed in Progress. Any use of a reduction to produce a witness must also specify the resulting data and certificate; the equivalence alone does not guarantee practical size. Counterexamples for minimum output Rényi entropy at orders \(p\ne1\) do not answer this question.

Source

Lovitz and Wu explicitly identify the search for a simple closed-form or practically computable counterexample as open [LovWu26], Abstract and Section 1.1. The entanglement-of-formation formulation is motivated by Shor’s equivalence of the universal additivity conjectures [Sho04]; this connection does not assert that their smallest or most practical witnesses have the same dimensions.

Progress

Hastings constructed random unitary channels whose minimum output entropy is nonadditive in sufficiently large dimension, yielding existentially the violations of (3), with superadditivity of the Holevo capacity under entangled inputs [Has09].
Shor proved equivalence of the universal additivity conjectures for \(\chi\), minimum output von Neumann entropy, \(E_F\), and strong superadditivity of \(E_F\) [Sho04]. Pomeransky proved that additivity of \(E_F\) implies its strong superadditivity [Pom03]. Together with Hastings’ result, these establish nonadditivity existentially; obtaining explicit, manageable witnesses requires control of the reductions and their dimensions.
Belinschi, Collins, and Nechita obtained random-channel violations at output dimension \(183\), and entropy gaps approaching one bit in a suitable asymptotic regime [BCN16]. These are separate parameter statements, not a one-bit gap at dimension \(183\).
For Rényi entropy away from order one, Cubitt, Harrow, Leung, Montanaro, and Winter supplied an explicit pair of channels from dimension \(4\) to \(3\) with nonadditive minimum output rank [CHL+08]. Derksen and Lovitz gave constructive counterexamples for every \(p>1\) [DL26]. Krohn-Grimberghe certified a positive-order violation for the normalized explicit pair over \(0<p\le1/22\) [KG26]. The last two works are preprints.
Leung, Lovitz, and Wu’s July 2026 preprint gives random-channel counterexamples for \(p>3/4\) and \(0\le p<1/4\). Section 5.1 reports a numerically optimized von Neumann Bell-input threshold of output dimension \(182\) for their ensemble, improving the earlier ensemble’s threshold of \(183\); this is not a universal minimum dimension [LLW26].
Two August 2026 preprints give deterministic asymptotic constructions. Lovitz and Wu derandomize through permutations but report an impractically large quantitative size bound [LovWu26]. Zhen, Zhu, Chen, and Wang give a deterministic algorithm polynomial in the target size, for fixed channel parameters and sufficiently large sizes [ZZCW26], Theorem 2.1. Neither work supplies a practically computed instance.

Comment

Finite-dimensional violations are known to exist, and deterministic asymptotic constructions are now available. The remaining task is a fully specified, rigorously verifiable instance with a simple construction or a computation that can actually be carried out. Merely bounding the dimensions, or excluding violations in a small dimension, does not complete this construction task. The universal equivalences connect the Holevo-capacity and entanglement-of-formation questions but do not preserve a prescribed dimension bound. The separate minimum-output-entropy dimension question concerns where a violation can exist, regardless of whether an explicit instance is known. The delayed-onset additivity record concerns when self-power additivity first fails for Rényi orders; the polarized Werner–Holevo record asks for multiplicativity in a particular family.

References

[Has09]: M. B. Hastings, “Superadditivity of communication capacity using entangled inputs,” Nature Physics 5, 255–257 (2009).DOI arXiv
[Sho04]: P. W. Shor, “Equivalence of additivity questions in quantum information theory,” Communications in Mathematical Physics 246, 453–472 (2004).arXiv
[Pom03]: A. A. Pomeransky, “Strong superadditivity of the entanglement of formation follows from its additivity,” Physical Review A 68, 032317 (2003).DOI arXiv
[BCN16]: S. T. Belinschi, B. Collins, and I. Nechita, “Almost one bit violation for the additivity of the minimum output entropy,” Communications in Mathematical Physics 341(3), 885–909 (2016).arXiv
[CHL+08]: T. Cubitt, A. W. Harrow, D. Leung, A. Montanaro, and A. Winter, “Counterexamples to additivity of minimum output \(p\)-Rényi entropy for \(p\) close to \(0\),” Communications in Mathematical Physics 284, 281–290 (2008).DOI arXiv
[DL26]: H. Derksen and B. Lovitz, “Constructive counterexamples to the additivity of minimum output Rényi entropy of quantum channels for all \(p>1\),” preprint (2025; v2 January 2026).arXiv
[KG26]: A. Krohn-Grimberghe, “Exact certification of a positive-order Rényi additivity violation for an explicit channel pair,” preprint (2026; v2 August 2026).arXiv
[LLW26]: D. Leung, B. Lovitz, and P. Wu, “Counterexamples to additivity of minimum output \(p\)-Rényi entropy of quantum channels for \(p>3/4\) and \(0\le p<1/4\),” preprint (July 2026).arXiv
[LovWu26]: B. Lovitz and P. Wu, “Superadditivity of classical communication over quantum channels via random and deterministic permutations,” preprint (August 2026).arXiv
[ZZCW26]: G. Zhen, C. Zhu, R. Chen, and X. Wang, “Deterministic minimum-output-entropy nonadditivity via Haagerup’s inequality and near-free permutation representations,” preprint (August 2026).arXiv

Closed-form nonadditivity of the Holevo capacity and entanglement of formation

Problem

Source

Progress

Comment

References

Cite this problem

BibTeX

Plain text

Problem

Source

Progress

Comment

References

Related problems