Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2608.31081

Deterministic Minimum-Output-Entropy Nonadditivity via Haagerup's Inequality and Near-Free Permutation Representations

Guocheng Zhen, Chengkai Zhu, Ranyiliu Chen, Xin Wang

quant-phSubmitted Aug 31, 2026• Announced Sep 1, 2026• 5 citations
arXivHTMLPDF

Abstract

We give a deterministic realization of the finite-dimensional quadratic certificate underlying Collins's mixed-unitary proof of minimum-output-entropy nonadditivity. For every fixed integer $K\ge 2$ and rational $η>0$ satisfying $\log K>2(3+η)^2$, a deterministic polynomial-time algorithm, for every sufficiently large target size $N$, outputs $K$ permutations on $N'=N+o_{K,η}(N)$ points. Restricting their permutation matrices to the nontrivial standard representation yields real orthogonal Stinespring blocks and a channel $Φ_{N'}:M_{N'-1}(\mathbb{C})\to M_K(\mathbb{C})$ such that \[ 2H_{\min}(Φ_{N'}) -H_{\min}(Φ_{N'}^{\otimes 2}) \ge \frac{\log K}{K} -2\log\left(1+\frac{(3+η)^2}{K}\right) >0. \] The construction combines Haagerup's length-two inequality with the simultaneous deterministic spectral approximation of O'Donnell and Wu. We further show that the constant $3$ is asymptotically sharp on the relevant Hermitian zero-diagonal coefficient class and that the finite spectral transfer is nearly saturated, thereby isolating the finer geometry of the full output body as the natural next level of refinement beyond the scalar-radius method. Finally, a standard covariant extension converts the same deterministic entropy gap exactly into self-tensor superadditivity of the one-shot Holevo quantity.

Comments
26 pages. Feedback and comments are welcome

Related papers

Unbounded Holevo additivity gaps in finite dimensions

Jinzhao Wang

We establish unbounded two-use Holevo additivity gaps in finite dimensions. For each sufficiently large fixed integer $K$ and all sufficiently large $n$, we construct channels $T_n$ with output dimension $K^n$, input dimension $\exp(Θ_K(n^2))$, and \[ χ(T_n^{\otimes2})-2χ(T_n) \ge n\left[\frac{\log_2K}{K}-2\log_2(1+9/K)\right]-O(1/n). \] The gap is linear in output qubits, with an explicit quadratic input-qubit cost and an explicit threshold on $n$. We also obtain channels whose single-use Holevo quantity tends to zero while their two-use Holevo information, and hence classical capacity, diverges. The channels arise from structured tensor products of the complementary mixed-unitary channels used in Collins's free-probabilistic proof. We establish minimum-output-entropy gaps by combining Collins--Youn's product-group Haagerup inequality with Bordenave--Collins's quantitative strong-convergence estimates. We also provide a Lean certificate for our proofs.

quant-pharXiv:2609.18222•Sep 17, 2026•2 citations

Almost One Bit Violation of Minimum-Output Rényi Entropy Additivity Simultaneously at All Orders

Guocheng Zhen, Chengkai Zhu, Ranyiliu Chen +1 more

We prove that minimum-output Rényi-entropy additivity can fail by almost one bit simultaneously at every nonnegative order. For every $\varepsilon\in(0,\log2)$, there exists a finite-dimensional quantum channel with a real Stinespring isometry such that the same maximally entangled input witnesses a tensor-square entropy gap of at least $\log2-\varepsilon$ for all $p\in[0,\infty]$. The output dimension can be chosen to be $O(\varepsilon^{-3})$ as $\varepsilon\downarrow0$. The construction uses direct products of free groups: tensorized Haagerup estimates control the one-copy outputs, while commutation between distinct factors forces exact Bell-branch collisions at two copies. Strong convergence gives both an existential realization through finite-dimensional representations of right-angled Artin groups followed by realification, and a Haar-orthogonal model whose success probability tends to one as the matrix dimension grows. We also determine the exact Bell quotient, prove asymptotically sharp regular-radius bounds, and show that the cubic output-dimension scale is optimal within the present purity--rank certificate.

quant-pharXiv:2609.18747•Sep 17, 2026•4 citations

Superadditivity of classical communication over quantum channels via random and deterministic permutations

Benjamin Lovitz, Peixue Wu

Since Hastings' proof of superadditivity of classical communication over quantum channels, considerable effort has been devoted to finding a structural explanation of this phenomenon that was originally established by concentration of measure for Haar random unitaries. The main observation of this work is that Haar randomness can be replaced by random permutations without changing the limiting geometry responsible for nonadditivity. This replacement turns a continuous problem over unitary matrices into a discrete combinatorial problem over zero--one permutation matrices, and thereby opens a path toward derandomization. The theorem of Bordenave and Collins shows that random permutations have the required limiting behavior and the algorithm of O'Donnell and Wu then provides a deterministic asymptotic construction, running in polynomial time in the size when the channel parameters and accuracy are fixed. Thus the random construction can be derandomized in an asymptotic algorithmic sense. Finally, a quantitative random permutation estimate by Chen, Garza-Vargas, Tropp and van Handel gives a fully numerical estimate: there exists a tuple of 57,836,025 permutations acting on a set of size \[ N \le 5.422\times 10^{116216}\] such that the associated finite dimensional channel exhibits nonadditivity. This enormous value remains an obstacle to a practical construction.

quant-pharXiv:2608.25961•Aug 27, 2026•6 citations

Counterexamples to additivity of minimum output $p$-Rényi entropy of quantum channels for all $p\ge 0$

Debbie Leung, Benjamin Lovitz, Ion Nechita +1 more

The additivity of minimum output entropies is a central problem in quantum information theory. Nonadditivity is known for every Rényi order $p>1$, at the von Neumann point $p=1$, and for sufficiently small positive $p$, while much of the interval $0<p<1$ has remained open. In this work, we prove that for every $p>0$ there exist finite-dimensional quantum channels whose minimum output $p$-Rényi entropies violate additivity. Our proof combines two constructions: random projection-induced channels yield nonadditivity for $p>3/4$, and antisymmetric postprocessing extends the violation to all positive Rényi orders. Our estimates also improve the output-dimension bound obtained by Belinschi, Collins, and Nechita for additivity violation of minimum output von Neumann entropy.

quant-pharXiv:2607.15210•Jul 17, 2026•8 citations

Exact certification of a positive-order Rényi additivity violation for an explicit channel pair

Artus Krohn-Grimberghe

Cubitt, Harrow, Leung, Montanaro, and Winter (CHLMW) exhibited an explicit pair of quantum channels whose minimum output Rényi entropy is nonadditive at order zero, and reported numerical violations at positive orders close to zero. Their paper states that a semidefinite-programming argument yields a rigorous positive-order interval for the same example, without printing the endpoint or a verifiable certificate; a recent paper by Leung, Lovitz, and Wu records that for this pair "no rigorous endpoint was obtained". We close that gap for the trace-preserving normalization of the printed pair fixed in Section 2. Small rational witness matrices prove that every output of either channel has all eigenvalues between $301/100000$ and $2/3$; a single explicit entangled input has an exact rational joint output spectrum of rank eight; and two independent elementary interval arguments turn these three facts into a proof of strict additivity violation, $S_p^{\min}(\mathrm{N}_R\otimes\mathrm{N}_{\bar S}) < S_p^{\min}(\mathrm{N}_R)+S_p^{\min}(\mathrm{N}_{\bar S}),$ for every real order $0<p\le 1/22$. Every step of the verification reduces to comparisons of integers, and the complete certificate is a few small rational matrices that a reader can check with a short program -- or, for any single order, by hand. To our knowledge, consistent with the assessment of Leung, Lovitz, and Wu, this is the first printed, computer-verifiable certified positive-order endpoint for this explicit pair. We claim no novelty for the phenomenon or for the eigenvalue-floor mechanism, both due to CHLMW, and no optimality of the endpoint.

quant-pharXiv:2608.17376•Aug 19, 2026•0 citations

Additivity violation of the regularized minimum output entropy

Sang-Gyun Youn, Benoît Collins

The problem of additivity of the Minimum Output Entropy is of fundamental importance in Quantum Information Theory (QIT). It was solved by Matthew B. Hastings [“Superadditivity of communication capacity using entangled inputs”, Nature Physics 5, 255–257 (2009; doi:)] in the one-shot case by exhibiting a pair of random quantum channels. However, the initial motivation was arguably to understand regularized quantities, and there was so far no way to solve additivity questions in the regularized case. The purpose of this paper is to give a solution to this problem. Specifically, we exhibit a pair of quantum channels that unearths additivity violation of the regularized minimum output entropy. Unlike previously known results in the one-shot case, our construction is non-random, infinite-dimensional, and in the commuting-operator setup. The commuting-operator setup is equivalent to the tensor-product setup in the finite-dimensional case for this problem, but their difference in the infinite-dimensional setting has attracted substantial attention and legitimacy recently in QIT with the celebrated resolutions of Tsirelson's and Connes embedding problem [ Z. Ji et al., “ \mathsf{MIP}^*= \mathsf{RE} ”, Preprint, ], Likewise, it is not clear that our approach works in the finite-dimensional setup. Our strategy of proof relies on developing a variant of the Haagerup inequality optimized for a product of free groups.

arXiv:1907.07856•Documenta Mathematica•Jan 1, 2022•6 citations
We give a deterministic realization of the finite-dimensional quadratic certificate underlying Collins's mixed-unitary proof of minimum-output-entropy nonadditivity. For every fixed integer K≥2K\ge 2K≥2 and rational η>0η>0η>0 satisfying log⁡K>2(3+η)2\log K>2(3+η)^2logK>2(3+η)2, a deterministic polynomial-time algorithm, for every sufficiently large target size NNN, outputs KKK permutations on N′=N+oK,η(N)N'=N+o_{K,η}(N)N′=N+oK,η​(N) points. Restricting their permutation matrices to the nontrivial standard representation yields real orthogonal Stinespring blocks and a channel ΦN′:MN′−1(C)→MK(C)Φ_{N'}:M_{N'-1}(\mathbb{C})\to M_K(\mathbb{C})ΦN′​:MN′−1​(C)→MK​(C) such that [ 2H_{\min}(Φ_{N'}) -H_{\min}(Φ_{N'}^{\otimes 2}) \ge \frac{\log K}{K} -2\log\left(1+\frac{(3+η)^2}{K}\right) >0. ] The construction combines Haagerup's length-two inequality with the simultaneous deterministic spectral approximation of O'Donnell and Wu. We further show that the constant 333 is asymptotically sharp on the relevant Hermitian zero-diagonal coefficient class and that the finite spectral transfer is nearly saturated, thereby isolating the finer geometry of the full output body as the natural next level of refinement beyond the scalar-radius method. Finally, a standard covariant extension converts the same deterministic entropy gap exactly into self-tensor superadditivity of the one-shot Holevo quantity.
We establish unbounded two-use Holevo additivity gaps in finite dimensions. For each sufficiently large fixed integer KKK and all sufficiently large nnn, we construct channels TnT_nTn​ with output dimension KnK^nKn, input dimension exp⁡(ΘK(n2))\exp(Θ_K(n^2))exp(ΘK​(n2)), and χ(Tn⊗2)−2χ(Tn)≥n[log⁡2KK−2log⁡2(1+9/K)]−O(1/n). χ(T_n^{\otimes2})-2χ(T_n) \ge n\left[\frac{\log_2K}{K}-2\log_2(1+9/K)\right]-O(1/n). χ(Tn⊗2​)−2χ(Tn​)≥n[Klog2​K​−2log2​(1+9/K)]−O(1/n). The gap is linear in output qubits, with an explicit quadratic input-qubit cost and an explicit threshold on nnn. We also obtain channels whose single-use Holevo quantity tends to zero while their two-use Holevo information, and hence classical capacity, diverges. The channels arise from structured tensor products of the complementary mixed-unitary channels used in Collins's free-probabilistic proof. We establish minimum-output-entropy gaps by combining Collins--Youn's product-group Haagerup inequality with Bordenave--Collins's quantitative strong-convergence estimates. We also provide a Lean certificate for our proofs.
We prove that minimum-output Rényi-entropy additivity can fail by almost one bit simultaneously at every nonnegative order. For every ε∈(0,log⁡2)\varepsilon\in(0,\log2)ε∈(0,log2), there exists a finite-dimensional quantum channel with a real Stinespring isometry such that the same maximally entangled input witnesses a tensor-square entropy gap of at least log⁡2−ε\log2-\varepsilonlog2−ε for all p∈[0,∞]p\in[0,\infty]p∈[0,∞]. The output dimension can be chosen to be O(ε−3)O(\varepsilon^{-3})O(ε−3) as ε↓0\varepsilon\downarrow0ε↓0. The construction uses direct products of free groups: tensorized Haagerup estimates control the one-copy outputs, while commutation between distinct factors forces exact Bell-branch collisions at two copies. Strong convergence gives both an existential realization through finite-dimensional representations of right-angled Artin groups followed by realification, and a Haar-orthogonal model whose success probability tends to one as the matrix dimension grows. We also determine the exact Bell quotient, prove asymptotically sharp regular-radius bounds, and show that the cubic output-dimension scale is optimal within the present purity--rank certificate.
Since Hastings' proof of superadditivity of classical communication over quantum channels, considerable effort has been devoted to finding a structural explanation of this phenomenon that was originally established by concentration of measure for Haar random unitaries. The main observation of this work is that Haar randomness can be replaced by random permutations without changing the limiting geometry responsible for nonadditivity. This replacement turns a continuous problem over unitary matrices into a discrete combinatorial problem over zero--one permutation matrices, and thereby opens a path toward derandomization. The theorem of Bordenave and Collins shows that random permutations have the required limiting behavior and the algorithm of O'Donnell and Wu then provides a deterministic asymptotic construction, running in polynomial time in the size when the channel parameters and accuracy are fixed. Thus the random construction can be derandomized in an asymptotic algorithmic sense. Finally, a quantitative random permutation estimate by Chen, Garza-Vargas, Tropp and van Handel gives a fully numerical estimate: there exists a tuple of 57,836,025 permutations acting on a set of size N≤5.422×10116216 N \le 5.422\times 10^{116216}N≤5.422×10116216 such that the associated finite dimensional channel exhibits nonadditivity. This enormous value remains an obstacle to a practical construction.
Counterexamples to additivity of minimum output ppp-Rényi entropy of quantum channels for all p≥0p\ge 0p≥0
The additivity of minimum output entropies is a central problem in quantum information theory. Nonadditivity is known for every Rényi order p>1p>1p>1, at the von Neumann point p=1p=1p=1, and for sufficiently small positive ppp, while much of the interval 0<p<10<p<10<p<1 has remained open. In this work, we prove that for every p>0p>0p>0 there exist finite-dimensional quantum channels whose minimum output ppp-Rényi entropies violate additivity. Our proof combines two constructions: random projection-induced channels yield nonadditivity for p>3/4p>3/4p>3/4, and antisymmetric postprocessing extends the violation to all positive Rényi orders. Our estimates also improve the output-dimension bound obtained by Belinschi, Collins, and Nechita for additivity violation of minimum output von Neumann entropy.
Cubitt, Harrow, Leung, Montanaro, and Winter (CHLMW) exhibited an explicit pair of quantum channels whose minimum output Rényi entropy is nonadditive at order zero, and reported numerical violations at positive orders close to zero. Their paper states that a semidefinite-programming argument yields a rigorous positive-order interval for the same example, without printing the endpoint or a verifiable certificate; a recent paper by Leung, Lovitz, and Wu records that for this pair "no rigorous endpoint was obtained". We close that gap for the trace-preserving normalization of the printed pair fixed in Section 2. Small rational witness matrices prove that every output of either channel has all eigenvalues between 301/100000301/100000301/100000 and 2/32/32/3; a single explicit entangled input has an exact rational joint output spectrum of rank eight; and two independent elementary interval arguments turn these three facts into a proof of strict additivity violation, Spmin⁡(NR⊗NSˉ)<Spmin⁡(NR)+Spmin⁡(NSˉ),S_p^{\min}(\mathrm{N}_R\otimes\mathrm{N}_{\bar S}) < S_p^{\min}(\mathrm{N}_R)+S_p^{\min}(\mathrm{N}_{\bar S}),Spmin​(NR​⊗NSˉ​)<Spmin​(NR​)+Spmin​(NSˉ​), for every real order 0<p≤1/220<p\le 1/220<p≤1/22. Every step of the verification reduces to comparisons of integers, and the complete certificate is a few small rational matrices that a reader can check with a short program -- or, for any single order, by hand. To our knowledge, consistent with the assessment of Leung, Lovitz, and Wu, this is the first printed, computer-verifiable certified positive-order endpoint for this explicit pair. We claim no novelty for the phenomenon or for the eigenvalue-floor mechanism, both due to CHLMW, and no optimality of the endpoint.
The problem of additivity of the Minimum Output Entropy is of fundamental importance in Quantum Information Theory (QIT). It was solved by Matthew B. Hastings [“Superadditivity of communication capacity using entangled inputs”, Nature Physics 5, 255–257 (2009; doi:)] in the one-shot case by exhibiting a pair of random quantum channels. However, the initial motivation was arguably to understand regularized quantities, and there was so far no way to solve additivity questions in the regularized case. The purpose of this paper is to give a solution to this problem. Specifically, we exhibit a pair of quantum channels that unearths additivity violation of the regularized minimum output entropy. Unlike previously known results in the one-shot case, our construction is non-random, infinite-dimensional, and in the commuting-operator setup. The commuting-operator setup is equivalent to the tensor-product setup in the finite-dimensional case for this problem, but their difference in the infinite-dimensional setting has attracted substantial attention and legitimacy recently in QIT with the celebrated resolutions of Tsirelson's and Connes embedding problem [ Z. Ji et al., “ \mathsf{MIP}^*= \mathsf{RE} ”, Preprint, ], Likewise, it is not clear that our approach works in the finite-dimensional setup. Our strategy of proof relies on developing a variant of the Haagerup inequality optimized for a product of free groups.