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

arXiv:2608.25961 · quant-ph, math-ph, math.MP, math.PR · Submitted 2026-08-26 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: Quantum Radio. Generated commentary on the latest quantum physics and condensed matter papers.

Kai: Today's paper: "Superadditivity of classical communication over quantum channels via random and deterministic permutations".

Mira: Since Haar randomness can be replaced by random permutations without changing the limiting geometry responsible for nonadditivity,

Kai: First, who's behind it and why it matters.

Title and authors: Kai: So, this paper is showing that even when we replace those continuous Haar random variables with discrete random permutations, we can still get this nonadditivity in classical communication over quantum channels, Mira?

Mira: Exactly, Kai; it pins every claim to the fact that these specific permutation constructions mimic the limiting geometry responsible for that nonadditivity. The core idea is that this property isn't lost when we switch from continuous randomness to a discrete set of permutations.

Lev: From my side, if we're talking about real hardware, what does it mean for us? Does this give us a roadmap for building protocols that are robust against noise without needing infinitely large systems?

Kai: The authors show they can find these specific permutation tuples deterministically, which is a huge step because it moves us from just proving something exists randomly to actually finding the structure we need. It's like having a blueprint instead of just knowing a random shape might work.

Mira: That deterministic construction is key because it proves that these combinatorial structures are powerful enough to force the desired two-copy output exactly, which violates additivity in the limit. This moves the problem from asymptotic limits into verifiable finite settings, even if those settings are currently huge.

Lev: I'm still worried about the computational cost of finding these tuples; if we need a set of permutations with one hundred sixteen thousand two hundred seventeen decimal digits for a specific size NNA, how do we even begin to test this on any existing quantum hardware?

Kai: The paper gives us that explicit scale, which is really helpful because it tells us exactly what kind of system size we're dealing with when we look for these effects. It sets the bar for what's needed to observe this behavior.

Mira: And the mathematical machinery they use, linking spectral properties like those top spectral edges to discrepancy measures, provides the rigorous proof that if the entropy gap is big enough, this nonadditivity must occur in finite dimensions. That's why it works and not just by coincidence.

Lev: So what’s the big-picture impact here for error correction? Does this suggest we can use these permutation constraints to design more tailored fault-tolerant protocols that inherently prevent this kind of entropy reduction?

Kai: It suggests that the underlying structure of the permutations themselves dictates where the information loss happens, which is a necessary starting point before we even start designing codes. This work gives us a concrete mathematical object—the permutation tuple—that governs the behavior.

Mira: Precisely; it moves us away from just looking at noisy channels and towards understanding *why* certain discrete structures impose these specific non-additive constraints on quantum information flow. The implication is that we can use combinatorial tools to analyze quantum resource theories more deeply.

Lev: It's interesting how this ties back to the free probability models we saw in other papers; if we can map these permutation constraints onto those free limit channels, it might help us simplify the analysis of these complex noise regimes.

Kai: We’ve got a lot of ground here showing that derandomization is possible in this context, whether using Haar randomness or permutations, and now with an algorithm to find the right permutations.

Mira: It opens up a new avenue for exploring quantum non-additivity through structural methods rather than just statistical averages over continuous spaces.

Lev: So we’ve established the theoretical existence of these counterexamples and found an explicit scale for them, which is a solid foundation before we try to figure out how to engineer them in the lab.

The paper's summary: Kai: So, moving on to what the authors suggest for future work, they are looking at how we can push this further beyond just permutations and random channels, Mira?

Mira: Exactly; they’re exploring whether there are other algebraic structures or mechanisms that could serve as a foundation for quantum non-additivity counterexamples. They aren't satisfied with just permutation tuples.

Lev: If they find some new mechanism, how does that change the hardware requirements we talked about earlier? Does a different structure mean we need fewer permutations or a smaller system size NNA?

Kai: They’re essentially searching for new mathematical tools from areas like free probability or group theory that could provide a different way to construct these non-additive channels. It’s an attempt to find more fundamental reasons for this phenomenon.

Mira: That search is crucial because it would mean the mechanism is universal, not just tied to the specific algebraic properties of permutations they used in this paper. It pushes the theory toward a deeper understanding of when and where these non-additive effects appear in quantum systems.

Lev: From an error correction standpoint, if a new structure emerges that is easier to realize physically—perhaps something with more local constraints—it might give us a path to building protocols that are more efficient than what we can achieve with the permutation approach.

Kai: That’s the hope; finding a simpler underlying structure could translate directly into more practical, less resource-intensive quantum communication protocols. It would mean we don't have to rely on such enormous system sizes for every single demonstration.

Mira: The paper flags that they are currently focused on the tensor product of complex conjugate pair, but the suggestion is to broaden that search to see if other entanglement structures can force this non-additivity in a similar way. It’s an open question about the universality of this effect.

Lev: It sounds like they're looking for a structural shortcut; maybe there's an inherent geometric feature in some quantum state space that guarantees this output gap regardless of the specific permutation details.

Kai: That’s what we’re hoping to see; a feature that is robust enough to survive when you move from discrete permutations back toward continuous Haar randomness, which would be a massive step forward for experimentalists.

Mira: If they find that connection, it validates the entire approach by showing that this non-additivity is not an artifact of the discrete setting but a reflection of a deeper physical principle governing quantum information limits.

The paper's improvements: Kai: So, to wrap up on "Superadditivity of classical communication over quantum channels via random and deterministic permutations," the main point is that we can find concrete instances where classical communication over these quantum channels shows a non-additive behavior under permutation constructions.

Mira: Right; the authors successfully bridge the gap between continuous randomness and discrete structures, proving that this nonadditivity persists even when using random permutations instead of Haar unitaries.

Lev: I think this result is significant because it confirms that these combinatorial constraints are powerful enough to violate additivity in finite dimensions, which is a big step toward understanding resource limitations in quantum communication.

Kai: It’s exciting because it gives us a concrete mathematical object—the permutation tuple—that we can use as a benchmark for testing potential future hardware designs.

Mira: And the explicit quantitative estimate for the required system size really grounds these abstract limits in reality, telling us exactly how large a simulation or device needs to be to see this effect.

Lev: For error correction, it means we have a theoretical structure that dictates exactly where the output entropy gap will occur, which is vital for designing protocols that are more resilient against noise.

Kai: We’ve shown that derandomization works here, and finding these deterministic constructions gives us a way to systematically search for these counterexamples in finite settings.

Mira: It opens up new ways to study quantum non-additivity by looking at structural properties of channels rather than just relying on the statistical properties of continuous random variables.

Lev: So, while the construction itself is computationally intensive, the result validates that this pathway exists for exploring quantum resource theories in a more structured way.

Conclusion: Kai: So, we’re wrapping up on "Superadditivity of classical communication over quantum channels via random and deterministic permutations," which really shows that replacing continuous Haar randomness with discrete permutations doesn't lose that core nonadditivity we’re talking about.

Mira: Exactly, Kai; the authors successfully bridged the gap between those continuous random variables and discrete structures, proving that this nonadditivity persists even when using random permutations instead of Haar unitaries.

Kai: It’s exciting because it gives us a concrete mathematical object—the permutation tuple—that we can use as a benchmark for testing potential future hardware designs.

Mira: And the explicit quantitative estimate for the required system size really grounds those abstract limits in reality, telling us exactly how large a simulation or device needs to be to see this effect.

Kai: We’ve shown that derandomization works here, and finding those deterministic constructions gives us a way to systematically search for these counterexamples in finite settings.

Mira: It opens up new ways to study quantum non-additivity by looking at structural properties of channels rather than just relying on the statistical properties of continuous random variables.

Lev: So, while the construction itself is computationally intensive, the result validates that this pathway exists for exploring quantum resource theories in a more structured way.

Kai: That’s the picture we have today, moving toward derandomization in this area, and it definitely gives us a lot to chew on before we look at what's next on our schedule.

Mira: Indeed, the paper lays out a clear mathematical pathway showing that finite-dimensional channels generated by these permutation tuples can indeed exhibit nonadditivity.

Lev: I think this work provides a rigorous foundation for using combinatorial structures to study quantum information problems that are often intractable when approached through continuous methods.

Kai: That’s the picture we have today, moving toward derandomization in this area, and it definitely gives us a lot to chew on before we look at what's next on our schedule.

Mira: I think the real impact for me is that we can start looking for structural explanations of nonadditivity that don't rely on continuous Haar randomness, opening up new avenues in understanding how quantum correlations behave in noisy settings.

Lev: For error correction, it means we have a theoretical structure—the permutation tuples—that dictates where the information loss or reduction occurs at the finite level, which is a necessary first step before we can even think about building practical codes on it.

Kai: Ultimately, this paper gives us a concrete bound on how large a system needs to be to observe this effect, which helps researchers know what scale of simulation or hardware they need to aim for when chasing these non-additive phenomena.

Mira: It’s a strong piece of work because it moves the discussion from just proving existence in the limit to providing tools—like the deterministic search algorithm and quantitative estimates—to find those actual instances.

Lev: We should watch how this deterministic construction plays out in future error correction studies; if we can build systems around these permutation constraints, it could lead to more tailored fault-tolerant approaches.

Department of Computer Science and Software Engineering, Concordia University · Department of Mathematics, Institute for Quantum and Information Sciences, Syracuse University · Institute for Quantum Computing, University of Waterloo

quant-ph, math-ph, math.MP, math.PR

Submitted: 2026-08-26

Updated: 2026-10-05

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 76/100

The gist: Since Haar randomness can be replaced by random permutations without changing the limiting geometry responsible for nonadditivity, this work shows that classical communication over quantum channels

Key concepts

Superadditivity: This phenomenon means that when you combine two independent quantum communication channels, the minimum output entropy of the combined system is strictly less than twice the minimum output entropy of each individual channel. This violation of additivity is a key feature distinguishing quantum communication from classical communication.
Haar Randomness vs. Permutations: The study replaces continuous Haar random unitaries with discrete random permutations to investigate if the nonadditivity observed in continuous settings remains true for simpler, discrete constructions. This tests whether the geometric properties causing nonadditivity are robust against this type of randomness.
Free Limit Channels: The paper connects finite-dimensional quantum channels to their infinite-dimensional 'free limit' versions using strong convergence theorems. This allows researchers to analyze the behavior of complex, finite systems by studying simpler, exactly solvable models in the limit, which helps establish the nonadditivity gap.
Deterministic Construction: The authors developed an algorithm that provides a way to find specific permutation tuples that guarantee superadditivity. While computationally hard for large systems, this deterministic method shows that the desired nonadditive behavior can be achieved through a structured search, offering a path toward derandomization.

Terminology

Trace — 34× in this paper · explained in 2 episodes
Additivity — 33× in this paper · explained in 1 episode
Superadditivity — 12× in this paper · explained in 2 episodes
Admissibility — 10× in this paper · explained in 2 episodes
Hilbert Space — 8× in this paper · explained in 2 episodes
Entanglement — 5× in this paper · explained in 4 episodes
Accuracy — 4× in this paper · explained in 1 episode
Core — 3× in this paper · explained in 2 episodes
Admissible Tuple — 2× in this paper · explained in 1 episode
Benchmark — 2× in this paper · explained in 2 episodes
Embeddings — 2× in this paper · explained in 2 episodes
Fidelity — 2× in this paper · explained in 2 episodes
Verification — 2× in this paper · explained in 2 episodes
Axioms — 1× in this paper · explained in 2 episodes
Homogeneity — 1× in this paper · explained in 2 episodes
Quantum Circuits — 1× in this paper · explained in 2 episodes
Regularization — 1× in this paper · explained in 3 episodes

Summary

Since Haar randomness can be replaced by random permutations without changing the limiting geometry responsible for nonadditivity, this work shows that classical communication over quantum channels exhibits superadditivity under random and deterministic permutation constructions.

The core problem addressed is the superadditivity of classical communication over quantum channels, a phenomenon fundamentally linked to the additivity problem of minimum output entropy in quantum information theory.

A fundamental difference between classical and quantum noise is that quantum channels allow the joint system to exhibit less entropy than the sum of its parts.

The paper investigates how this nonadditivity persists when replacing continuous Haar random unitaries with discrete random permutations, which opens a path toward derandomization. The main finding demonstrates that for sufficiently large systems, these permutation-based constructions yield finite-dimensional channels exhibiting nonadditivity.

The proof strategy relies on linking the finite-dimensional channel to its infinite-dimensional free limit via strong convergence.

The authors begin by studying standard random channel models: complementary channels associated with Haar-random mixed-unitary channels and channels induced by Haar-random subspaces.
Strong asymptotic freeness for Haar randomness identifies their large-environment limits as a free mixed-unitary complementary channel and a free-compression channel, both of which are exactly solvable.
The strong convergence theorem of Bordenave and Collins is applied to show that the finite-dimensional channels generated by permutation tuples strongly converge in probability to the infinite-dimensional free limit channels. This ensures that the one-copy output body converges, meaning the minimum output entropy converges: Hmin(ΦN) → Hmin(Φ∞).

The two-copy nonadditivity is established by showing that a specific auxiliary phase system forces the desired two-copy output exactly.

The construction separates the ingredients needed for nonadditivity: The one-copy output body is controlled by the spectral behavior of a tuple of permutations, whereas an auxiliary finite phase system forces the desired two-copy output exactly.
For any permutation tuple, a key identity shows that: ((ΦσN ⊗ ΦσN)(ψ+rN) = tψ+k + (1 − t)Ik2k2) for sufficiently large N.
This leads to the conclusion that: "Hmin(ΦσN ⊗ ΦσN) ≤ H(ρ∞) < 2Hmin(Φ∞)," establishing the violation of additivity for the two-copy case in the limit.

The paper provides a deterministic algorithmic construction to find such permutation tuples, although it remains computationally challenging.

The algorithm of O’Donnell and Wu provides a deterministic asymptotic construction, running in polynomial time in the size when the channel parameters and accuracy are fixed.
This allows for a deterministic search of a suitable permutation tuple by finding an admissible lift inside a very large search space, although the required dimensions for current quantitative estimates are not numerically practical.

A quantitative numerical estimate provides an explicit scale for the system size required to observe this nonadditivity.

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 × 10 116216 such that the associated finite dimensional channel exhibits nonadditivity.
The final construction yields an explicit integer bound, NNA (which has 116,217 decimal digits), satisfying the required condition for superadditivity: "There exists a tuple σNNA ∈ S57836025NNA (202) for which HminΦσNNA ⊗ ΦσNNA < 2Hmin(ΦσNNA)."

The paper details the mathematical machinery connecting spectral properties to the output entropy gap, using support polynomials and discrepancy measures.

The support function is a top spectral edge, and it is encoded by degree-two polynomials, leading to the key relationship: hOΓ(A) = max σ(Γ(A)) = 1A + Γ(A) - 1.
The discrepancy between the finite-dimensional output body and its free limit is measured by: errN (σN):= sup A=A∗∈Mk,∥A∥≤1 λmax(ΓσN (A)) − hKk,t (A).
By combining this discrepancy with the Audenaert–Fannes inequality, the paper proves that if the gap in entropy is sufficiently large, "HminΦσN ⊗ ΦσN < 2Hmin(ΦσN)," leading to a quantitative existence bound for N.

The final result confirms that both random and deterministic permutation constructions can be derandomized asymptotically.

Improvements for AI systems

As a diligent researcher, I have analyzed this paper, which establishes a framework for derandomizing constructions of quantum channels exhibiting superadditivity (non-additivity) of minimum output entropy by replacing Haar randomness with random permutations.

Here are the specific improvements that can be made to AI systems, categorized by the capability they unlock:

) 1. Enhanced Derandomization and Algorithmic Construction

The paper provides a deterministic, polynomial-time algorithm (O’Donnell and Wu) to find permutation tuples that satisfy spectral criteria necessary for non-additivity.

The improved AI system can perform an efficient, deterministic search for counterexamples to the additivity of minimum output entropy in finite-dimensional quantum channels.

Specifically: The system can take fixed channel parameters (accuracy, etc.) and deterministically find a set of random permutations that guarantees a violation of the additivity inequality:

If two independent channels act on the same input, the resulting joint output entropy will be strictly less than the sum of their individual minimum output entropies:

If Hmin(Φ1) and Hmin(Φ2) are known, this system can deterministically construct a channel Φ N such that Hmin(Φ N ⊗ Φ N) < 2Hmin(Φ N), where N is determined by the O’Donnell-Wu algorithm.

) 2. Robust Analysis of Quantum Channel Limits and Free Probability

The paper links finite-dimensional non-additivity to infinite-dimensional free compression channels via strong convergence theorems (Bordenave–Collins).

The improved AI system can analyze the asymptotic behavior of quantum information processing by mapping finite-dimensional channel constructions onto their free probability limits.

Specifically: The system can determine if a specific family of random quantum circuits (represented by permutation tuples) will exhibit non-additivity in the limit of large Hilbert spaces. It can identify which free compression limit the circuit converges to and predict whether this limiting channel violates additivity, even when a simple closed-form solution is unknown.

) 3. Verification and Characterization of Quantum Entanglement

The paper provides an exact identity (Theorem 3.4) showing that the finite-dimensional realization exactly reproduces a specific entangled output state (a Bell-state analogue).

The improved AI system can precisely characterize the entanglement properties of quantum states produced by permutation channels.

Specifically: When a channel is composed of two copies acting on an initial state, the system can verify that the resulting joint output state is exactly as entangled as predicted by its free limit. This allows for rigorous testing of whether a given quantum algorithm or communication protocol preserves or violates entanglement under noisy conditions.

) 4. Quantitative Resource Estimation and System Sizing

The paper provides a quantitative bound (Theorem 4.13) on the size of the required permutation set, leading to an explicit, albeit enormous, numerical scale for practical construction.

The improved AI system can provide precise resource estimates for constructing quantum communication protocols that violate additivity.

Specifically: Given desired accuracy levels and channel dimensions (k and m), the system can output a concrete upper bound on the required number of permutations (NNA). This allows researchers to know exactly how large a system must be to guarantee that a non-additive behavior is present, guiding the design of hardware or simulation requirements.

) 5. Automated Hypothesis Generation for Novel Mechanisms

The paper notes that current constructions rely on the tensor product of complex conjugate pair mechanism and suggests other mechanisms are open questions.

The improved AI system can perform automated literature review and hypothesis generation regarding new structural mechanisms for quantum non-additivity.

Specifically: The system can search existing mathematical literature (e.g., in free probability or group theory) for novel algebraic structures that might serve as the foundation for a quantum channel non-additivity counterexample, moving beyond the current permutation-based approach.

Abstract

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 times 10 116216 such that the associated finite dimensional channel exhibits nonadditivity. This enormous value remains an obstacle to a practical construction.