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:1902.10808 · Leibniz international proceedings in informatics

Approximate Unitary n^{2/3}-Designs Give Rise to Quantum Channels with Super Additive Classical Holevo Capacity

Aditya Nema, Sen, Pranab

Published Jan 1, 2019• 3 citations
arXivHTMLPDF

Abstract

In a breakthrough, Hastings' showed that there exist quantum channels whose classical capacity is superadditive i.e. more classical information can be transmitted by quantum encoding strategies entangled across multiple channel uses as compared to unentangled quantum encoding strategies. Hastings' proof used Haar random unitaries to exhibit superadditivity. In this paper we show that a unitary chosen uniformly at random from an approximate $n^{2/3}$-design gives rise to a quantum channel with superadditive classical Holevo capacity, where $n$ is the dimension of the unitary exhibiting the Stinespring dilation of the channel superoperator. We prove a sharp Dvoretzky-like theorem (similar to Aubrun, Szarek, Werner, 2010) stating that, with high probability under the choice of a unitary from an approximate $t$-design, random subspaces of large dimension make a Lipschitz function take almost constant value. Such theorems were known earlier only for Haar random unitaries. We obtain our result by appealing to Low's technique for proving concentration of measure for an approximate $t$-design, combined with a stratified analysis of the variational behaviour of Lipschitz functions on the unit sphere in high dimension. The stratified analysis is the main technical advance of this work. Finally we also show that for any $p>1$, approximate unitary $(n^{1.7} \log n)$-designs give rise to channels violating subadditivity of Rényi $p$-entropy. In addition to stratified analysis, the proof of this result uses a new technique of approximating a monotonic differentiable function defined on a closed bounded interval and its derivative by moderate degree polynomials which should be of independent interest. Hence, our work can be viewed as a partial derandomisation of Hastings' result and a step towards the quest of finding an explicit quantum channel with superadditive classical Holevo capacity.

DOI
10.4230/lipics.tqc.2019.9

Related papers

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

Approximate Unitary Designs Give Rise to Quantum Channels With Super Additive Classical Holevo Capacity

Aditya Nema, Pranab Sen

In a breakthrough, Hastings showed that there exist quantum channels whose classical Holevo capacity is superadditive i.e. more classical information can be transmitted by quantum encoding strategies entangled across multiple channel uses as compared to unentangled quantum encoding strategies. Hastings’ proof used Haar random unitaries to exhibit superadditivity. In this paper we show that a unitary chosen uniformly at random from an approximate$n^{2/3}$-design gives rise to a quantum channel with superadditive classical Holevo capacity, where$n$is the dimension of the unitary exhibiting the Stinespring dilation of the channel superoperator. We follow the geometric functional analytic approach of Aubrun, Szarek and Werner in order to prove our result. More precisely we prove a sharp Dvoretzky-like theorem stating that, with high probability under the choice of a unitary from an approximate$t$-design, random subspaces of large dimension make a Lipschitz function take almost constant value. Such theorems were known earlier only for Haar random unitaries. We obtain our result by appealing to Low’s technique for proving concentration of measure for an approximate$t$-design, combined with a stratified analysis of the variational behaviour of Lipschitz functions on the unit sphere in high dimension. The stratified analysis is the main technical advance of this work. Haar random unitaries require at least$\Omega (n^{2})$random bits in order to describe them with good precision. In contrast, there exist exact$n^{2/3}$-designs using only$O(n^{2/3} \log n)$random bits. Thus, our work can be viewed as a partial derandomisation of Hastings’ result, and a step towards the quest of finding an explicit quantum channel with superadditive classical Holevo capacity. Finally we also show that for any$p > 1$, approximate unitary$n^{1.7}$-designs give rise to channels violating subadditivity of Rényi$p$-entropy. In addition to stratified analysis, the proof of this result uses a new technique of approximating a monotonic differentiable function defined on a closed bounded interval and its derivative by moderate degree polynomials which should be of independent interest.

IEEE Transactions on Information Theory•Apr 21, 2022•1 citation

A quantum Johnson-Lindenstrauss lemma via unitary t-designs

Sen, Pranab

The famous Johnson-Lindenstrauss lemma states that for any set of n vectors, there is a linear transformation into a space of dimension O(log n) that approximately preserves all their lengths. In fact, a Haar random unitary transformation followed by projection onto the first O(log n) coordinates followed by a scaling works as a valid transformation with high probability. In this work, we show that the Haar random unitary can be replaced by a uniformly random unitary chosen from a finite set called an approximate unitary t-design for t = O(log n). Choosing a unitary from such a design requires only polylogarithmic random bits as opposed to exponential in dimension random bits required to choose a Haar random unitary with reasonable precision. Moreover, since such unitaries can be efficiently implemented in the superpositional setting, our result can be viewed as an efficient quantum Johnson-Lindenstrauss transform akin to efficient quantum Fourier transforms widely used in earlier work on quantum algorithms. We prove our result by leveraging a method of Low for showing concentration for approximate unitary t-designs. We discuss algorithmic advantages and limitations of our result and conclude with a toy application to private information retrieval.

arXiv:1807.08779•Jul 23, 2018•5 citations

Approaches for approximate additivity of the Holevo information of quantum channels

Felix Leditzky, Eneet Kaur, Nilanjana Datta +1 more

We study quantum channels that are close to another channel with weakly additive Holevo information, and we derive upper bounds on their classical capacity. Examples of channels with weakly additive Holevo information are entanglement-breaking channels, unital qubit channels, and Hadamard channels. Related to the method of approximate degradability, we define approximation parameters for each class above, which measure how close an arbitrary channel is to satisfying the respective property. This gives us upper bounds on the classical capacity in terms of functions of the approximation parameters, as well as an outer bound on the dynamic capacity region of a quantum channel. Since these parameters are defined in terms of the diamond distance, the upper bounds can be computed efficiently using semidefinite programming (SDP). We exhibit the usefulness of our method with two example channels: a convex mixture of amplitude damping and depolarizing noise and a composition of amplitude damping and dephasing noise. For both channels, our bounds perform well in certain regimes of the noise parameters in comparison to a recently derived SDP upper bound on the classical capacity. Along the way, we define the notion of a generalized channel divergence (which includes the diamond distance as an example), and we prove that for jointly covariant channels these quantities are maximized by purifications of a state invariant under the covariance group. This latter result may be of independent interest.

arXiv:1709.01111•Physical Review A•Jan 25, 2018•121 citations

Superadditivity for Entanglement-Assisted Communication

Hao-Chung Cheng, Mario Berta

The entanglement-assisted capacity of a quantum channel admits an additive single-letter characterization, implying that joint encodings across channel uses cannot increase the ultimate communication rate. Here, we show that this additive picture does not extend to communication reliability. Specifically, we prove that the Petz-Rényi channel information can be strictly superadditive for every $α\in[1/2,1)$, yielding a genuine multi-copy enhancement of the entanglement-assisted random-coding error exponent, even though the entanglement-assisted capacity remains additive. We establish this phenomenon analytically already for measurement channels, which are entanglement-breaking and have additive unassisted capacity. Remarkably, this strict superadditivity is witnessed by a separable, classically correlated two-copy channel-input marginal, demonstrating that no entanglement between the transmitted systems is required. Our results show that, although correlations across channel uses cannot increase the ultimate rate of entanglement-assisted communication, they can enhance its reliability.

quant-pharXiv:2607.15151•Jul 17, 2026•2 citations

LOW ENTROPY OUTPUT STATES FOR PRODUCTS OF RANDOM UNITARY CHANNELS

Benoît Collins, Motohisa Fukuda, Ion Nechita

In this paper, we study the behavior of the output of pure entangled states after being transformed by a product of conjugate random unitary channels. This study is motivated by the counterexamples by Hastings [Superadditivity of communication capacity using entangled inputs, Nat. Phys.5 (2009) 255–257] and Hayden–Winter [Counterexamples to the maximal p-norm multiplicativity conjecture for all p > 1, Comm. Math. Phys.284(1) (2008) 263–280] to the additivity problems. In particular, we study in depth the difference of behavior between random unitary channels and generic random channels. In the case where the number of unitary operators is fixed, we compute the limiting eigenvalues of the output states. In the case where the number of unitary operators grows linearly with the dimension of the input space, we show that the eigenvalue distribution converges to a limiting shape that we characterize with free probability tools. In order to perform the required computations, we need a systematic way of dealing with moment problems for random matrices whose blocks are i.i.d. Haar distributed unitary operators. This is achieved by extending the graphical Weingarten calculus introduced in [B. Collins and I. Nechita, Random quantum channels I: Graphical calculus and the Bell state phenomenon, Comm. Math. Phys.297(2) (2010) 345–370].

arXiv:1208.1449•Random Matrices Theory and Application•Jan 1, 2013•8 citations
In a breakthrough, Hastings' showed that there exist quantum channels whose classical capacity is superadditive i.e. more classical information can be transmitted by quantum encoding strategies entangled across multiple channel uses as compared to unentangled quantum encoding strategies. Hastings' proof used Haar random unitaries to exhibit superadditivity. In this paper we show that a unitary chosen uniformly at random from an approximate n2/3n^{2/3}n2/3-design gives rise to a quantum channel with superadditive classical Holevo capacity, where nnn is the dimension of the unitary exhibiting the Stinespring dilation of the channel superoperator. We prove a sharp Dvoretzky-like theorem (similar to Aubrun, Szarek, Werner, 2010) stating that, with high probability under the choice of a unitary from an approximate ttt-design, random subspaces of large dimension make a Lipschitz function take almost constant value. Such theorems were known earlier only for Haar random unitaries. We obtain our result by appealing to Low's technique for proving concentration of measure for an approximate ttt-design, combined with a stratified analysis of the variational behaviour of Lipschitz functions on the unit sphere in high dimension. The stratified analysis is the main technical advance of this work. Finally we also show that for any p>1p>1p>1, approximate unitary (n1.7log⁡n)(n^{1.7} \log n)(n1.7logn)-designs give rise to channels violating subadditivity of Rényi ppp-entropy. In addition to stratified analysis, the proof of this result uses a new technique of approximating a monotonic differentiable function defined on a closed bounded interval and its derivative by moderate degree polynomials which should be of independent interest. Hence, our work can be viewed as a partial derandomisation of Hastings' result and a step towards the quest of finding an explicit quantum channel with superadditive classical Holevo capacity.
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.
In a breakthrough, Hastings showed that there exist quantum channels whose classical Holevo capacity is superadditive i.e. more classical information can be transmitted by quantum encoding strategies entangled across multiple channel uses as compared to unentangled quantum encoding strategies. Hastings’ proof used Haar random unitaries to exhibit superadditivity. In this paper we show that a unitary chosen uniformly at random from an approximaten2/3n^{2/3}n2/3-design gives rise to a quantum channel with superadditive classical Holevo capacity, wherennnis the dimension of the unitary exhibiting the Stinespring dilation of the channel superoperator. We follow the geometric functional analytic approach of Aubrun, Szarek and Werner in order to prove our result. More precisely we prove a sharp Dvoretzky-like theorem stating that, with high probability under the choice of a unitary from an approximatettt-design, random subspaces of large dimension make a Lipschitz function take almost constant value. Such theorems were known earlier only for Haar random unitaries. We obtain our result by appealing to Low’s technique for proving concentration of measure for an approximatettt-design, combined with a stratified analysis of the variational behaviour of Lipschitz functions on the unit sphere in high dimension. The stratified analysis is the main technical advance of this work. Haar random unitaries require at leastΩ(n2)\Omega (n^{2})Ω(n2)random bits in order to describe them with good precision. In contrast, there exist exactn2/3n^{2/3}n2/3-designs using onlyO(n2/3log⁡n)O(n^{2/3} \log n)O(n2/3logn)random bits. Thus, our work can be viewed as a partial derandomisation of Hastings’ result, and a step towards the quest of finding an explicit quantum channel with superadditive classical Holevo capacity. Finally we also show that for anyp>1p > 1p>1, approximate unitaryn1.7n^{1.7}n1.7-designs give rise to channels violating subadditivity of Rényippp-entropy. In addition to stratified analysis, the proof of this result uses a new technique of approximating a monotonic differentiable function defined on a closed bounded interval and its derivative by moderate degree polynomials which should be of independent interest.
The famous Johnson-Lindenstrauss lemma states that for any set of n vectors, there is a linear transformation into a space of dimension O(log n) that approximately preserves all their lengths. In fact, a Haar random unitary transformation followed by projection onto the first O(log n) coordinates followed by a scaling works as a valid transformation with high probability. In this work, we show that the Haar random unitary can be replaced by a uniformly random unitary chosen from a finite set called an approximate unitary t-design for t = O(log n). Choosing a unitary from such a design requires only polylogarithmic random bits as opposed to exponential in dimension random bits required to choose a Haar random unitary with reasonable precision. Moreover, since such unitaries can be efficiently implemented in the superpositional setting, our result can be viewed as an efficient quantum Johnson-Lindenstrauss transform akin to efficient quantum Fourier transforms widely used in earlier work on quantum algorithms. We prove our result by leveraging a method of Low for showing concentration for approximate unitary t-designs. We discuss algorithmic advantages and limitations of our result and conclude with a toy application to private information retrieval.
We study quantum channels that are close to another channel with weakly additive Holevo information, and we derive upper bounds on their classical capacity. Examples of channels with weakly additive Holevo information are entanglement-breaking channels, unital qubit channels, and Hadamard channels. Related to the method of approximate degradability, we define approximation parameters for each class above, which measure how close an arbitrary channel is to satisfying the respective property. This gives us upper bounds on the classical capacity in terms of functions of the approximation parameters, as well as an outer bound on the dynamic capacity region of a quantum channel. Since these parameters are defined in terms of the diamond distance, the upper bounds can be computed efficiently using semidefinite programming (SDP). We exhibit the usefulness of our method with two example channels: a convex mixture of amplitude damping and depolarizing noise and a composition of amplitude damping and dephasing noise. For both channels, our bounds perform well in certain regimes of the noise parameters in comparison to a recently derived SDP upper bound on the classical capacity. Along the way, we define the notion of a generalized channel divergence (which includes the diamond distance as an example), and we prove that for jointly covariant channels these quantities are maximized by purifications of a state invariant under the covariance group. This latter result may be of independent interest.
The entanglement-assisted capacity of a quantum channel admits an additive single-letter characterization, implying that joint encodings across channel uses cannot increase the ultimate communication rate. Here, we show that this additive picture does not extend to communication reliability. Specifically, we prove that the Petz-Rényi channel information can be strictly superadditive for every α∈[1/2,1)α\in[1/2,1)α∈[1/2,1), yielding a genuine multi-copy enhancement of the entanglement-assisted random-coding error exponent, even though the entanglement-assisted capacity remains additive. We establish this phenomenon analytically already for measurement channels, which are entanglement-breaking and have additive unassisted capacity. Remarkably, this strict superadditivity is witnessed by a separable, classically correlated two-copy channel-input marginal, demonstrating that no entanglement between the transmitted systems is required. Our results show that, although correlations across channel uses cannot increase the ultimate rate of entanglement-assisted communication, they can enhance its reliability.
In this paper, we study the behavior of the output of pure entangled states after being transformed by a product of conjugate random unitary channels. This study is motivated by the counterexamples by Hastings [Superadditivity of communication capacity using entangled inputs, Nat. Phys.5 (2009) 255–257] and Hayden–Winter [Counterexamples to the maximal p-norm multiplicativity conjecture for all p > 1, Comm. Math. Phys.284(1) (2008) 263–280] to the additivity problems. In particular, we study in depth the difference of behavior between random unitary channels and generic random channels. In the case where the number of unitary operators is fixed, we compute the limiting eigenvalues of the output states. In the case where the number of unitary operators grows linearly with the dimension of the input space, we show that the eigenvalue distribution converges to a limiting shape that we characterize with free probability tools. In order to perform the required computations, we need a systematic way of dealing with moment problems for random matrices whose blocks are i.i.d. Haar distributed unitary operators. This is achieved by extending the graphical Weingarten calculus introduced in [B. Collins and I. Nechita, Random quantum channels I: Graphical calculus and the Bell state phenomenon, Comm. Math. Phys.297(2) (2010) 345–370].