Explicit channels with unbounded gains in classical communication using entangled inputs

Technical Summary: Explicit Channels with Unbounded Gains in Classical Communication Using Entangled Inputs

Problem Statement
The paper addresses the fundamental question in quantum information theory regarding the additivity of classical communication capacity over quantum channels. Specifically, it investigates whether entangling the inputs of independent uses of a quantum channel can increase the achievable classical communication rate beyond what is possible with product-state codewords.

For a memoryless channel $\Phi$, the optimal asymptotic rate using product states is given by the one-shot Holevo information $\chi_{\max}(\Phi)$. The classical capacity $C(\Phi)$ allows for entangled codewords across $n$ uses, defined as $C(\Phi) = \sup_{n \ge 1} \frac{1}{n}\chi_{\max}(\Phi^{\otimes n})$. The "additivity problem" asks if $C(\Phi) > \chi_{\max}(\Phi)$, or equivalently, if the minimum output entropy is non-additive. While Hastings (2009) proved the existence of such channels using probabilistic methods involving Haar-random unitaries, a longstanding open problem remained: can one construct an explicit family of finite-dimensional channels demonstrating this superadditivity, and can the gain be made unbounded?

Methodology
The authors construct an explicit family of finite-dimensional quantum channels $\Phi_N$ by combining deterministic qudit Clifford unitaries with a specific measurement and classical feedforward process. This approach serves as a derandomization of Hastings' probabilistic construction.

1. Channel Structure: The basic channel $\Psi^{(k)}_{n,H}$ is defined as a convex combination of a complementary mixed-unitary channel $\Psi_0$ and a completely depolarizing channel, controlled by a measurement operator $H$:
   $$\Psi^{(k)}_{n,H}(\rho) = \Psi_0(H\rho H) + \text{Tr}[(I_n - H^2)\rho] \frac{I_k}{k}$$
   Here, $\Psi_0$ is a uniform mixed-unitary channel where the unitaries $U_I$ are products of tensor products of quantum adder circuits.

2. Deterministic Unitaries: Instead of Haar-random unitaries, the authors use explicit unitary operators constructed from arithmetic quantum adder circuits modulo $Q = 2^q$. Specifically, they utilize the circuits $|a, b\rangle \mapsto |a+2b, b\rangle$ and $|a, b\rangle \mapsto |a, b+2a\rangle$. These are Clifford operators relative to generalized Pauli operators. The set of unitaries $\{U_I\}$ is formed by tensor products of these adder-based permutations.

3. Measurement and Feedforward (MFF): The operator $H$ is defined as $H^2 = \gamma(I_n + F)^{-1}$, where $F$ is a positive operator constructed from the unitaries to control the output entropy. The channel is implemented via a binary measurement $\{H^2, I_n - H^2\}$. If the outcome corresponds to $H^2$, the state passes through $\Psi_0$; otherwise, it is replaced by the maximally mixed state.

4. Entropy Bounds via Moment Estimates: The core technical innovation is deriving one-copy and two-copy output entropy bounds using moment estimates of the unitary family, rather than relying on strong convergence or concentration of measure for random matrices.

   • One-copy (Lower Bound): A lower bound on the minimum output entropy $H_{\min}(\Psi)$ is established by bounding the operator norm of $H A(W) H$, where $A(W)$ involves sums of $U_I^\dagger U_J$. This relies on the specific algebraic structure of the Clifford unitaries.
   • Two-copy (Upper Bound): An upper bound on $H_{\min}(\Psi \otimes \Psi)$ is derived by analyzing the trace of $F$. The authors show that for their specific choice of $F$ (a sum of high powers of $A(V)$), the trace $\text{Tr}(F)/n$ can be made arbitrarily small by choosing sufficiently large parameters $Q$ and $L$. This small trace ensures that the two-copy output entropy is significantly lower than twice the one-copy entropy.

Key Contributions and Results
The paper presents Theorem 1, which establishes the existence of an explicit quantum channel family $\Phi_N$ (parameterized by $N$) with the following properties:

• Dimensions: The output dimension $k$ is exponential in $N$, while the input dimension $n$ is doubly exponential in $N$.
• Unbounded Gain: The one-shot Holevo information $\chi_{\max}(\Phi_N)$ is strictly less than $1/N$, while the two-copy Holevo information $\chi_{\max}(\Phi_N^{\otimes 2})$ exceeds $N$.
• Superadditivity: Consequently, the classical capacity satisfies $C(\Phi_N) \ge \frac{1}{2}\chi_{\max}(\Phi_N^{\otimes 2}) \gg \chi_{\max}(\Phi_N)$.

The gap between the two-copy capacity and the one-shot capacity grows linearly with the parameter $r$ (where $N$ is related to $r$), while the input dimension grows doubly exponentially in $r$. This demonstrates an unbounded violation of additivity per channel use as the family parameter increases.

Significance and Claims
The authors claim to resolve three specific questions regarding the additivity problem:

1. Explicitness: They provide a channel defined by algebraic formulas (Clifford permutations and specific measurement operators) and prove analytically that its Holevo information is strictly superadditive, removing the need for probabilistic existence proofs.
2. Magnitude: They demonstrate that the gain per channel use, $\frac{1}{2}\chi_{\max}(\Phi^{\otimes 2}) - \chi_{\max}(\Phi)$, can grow without bound.
3. Dimension Bounds: They provide explicit bounds on the input and output dimensions required to achieve a prescribed gain.

The paper positions this work as a "proof of principle." The authors acknowledge that the current dimensions are not practically implementable and that the choice of unitaries is not unique. They suggest that finding simpler, smaller-size quantum circuits remains an open problem for future work. The mathematical proofs are verified using the Lean theorem prover. The work derandomizes Hastings' construction by replacing random unitaries with deterministic Clifford permutations and utilizing a carefully designed measurement and feedforward process to control entropy bounds via moment estimates.