Unbounded Holevo additivity gaps in finite dimensions

AI summary

Overview

Research area: Quantum information theory — specifically the classical capacity of quantum channels, the Holevo quantity, and additivity of channel capacities.

Technical level: Advanced. The paper assumes familiarity with quantum channels, von Neumann entropy, the Holevo–Schumacher–Westmoreland coding theorem, free probability (free group factors, Haagerup's inequality), and random matrix strong-convergence results.

Scope: The paper constructs explicit finite-dimensional quantum channels whose two-use Holevo information exceeds twice their single-use Holevo information by an amount that grows without bound, and it quantifies the input- and output-qubit cost of doing so.

What This Paper Is About

A quantum channel's classical capacity is governed by the Holevo quantity, and for a long time it was unclear whether using a channel jointly with entangled inputs across multiple uses can beat using it separately. Hastings showed in 2009 that it can, but every known gap stayed bounded as the channel dimensions grew. This paper asks whether the gap can grow without bound in finite dimensions, and how it scales with the number of input and output qubits — physically, whether entanglement across channel uses can give an arbitrarily large boost to the classical communication rate.

Key Contributions

1. Unbounded two-use Holevo gaps in finite dimensions. For every sufficiently large fixed integer K and all sufficiently large n, the paper constructs a channel T_n with output dimension K^n whose two-use gap Δχ(T_n) = χ(T_n^⊗2) − 2χ(T_n) grows linearly in n.

2. Explicit dimension accounting. The construction comes with an explicit quadratic input-qubit cost, Θ_K(n²), and n log₂K output qubits, plus an explicit threshold n₀(K) on how large n must be.

3. Capacity separations. The paper derives channels where C(T) − χ(T) is arbitrarily large and the ratio χ(T^⊗2)/(2χ(T)) is arbitrarily large, and separately a sequence of finite-dimensional channels whose single-use Holevo quantity tends to zero while their two-use Holevo information and classical capacity diverge.

4. A proof technique plus a formal certificate. The channels come from structured tensor products of the complementary mixed-unitary channels in Collins's free-probabilistic proof, with norm control from the Collins–Youn product-group Haagerup inequality and Bordenave–Collins quantitative strong convergence. The proofs are autoformalized in Lean and checked against Comparator.

Main Findings

• The main gap (Theorem 1.1): For fixed K ≥ 2 with δ_K = log₂K/K − 2log₂(1+9/K) > 0, and n ≥ n₀(K) = ⌈256(1+ln K)²⌉, there is a channel T_n: M_{2N^nK^{2n}}(ℂ) → M_{K^n}(ℂ) with N = ⌈e^{b_K n}⌉ and b_K = 40(7 ln K + 2), satisfying χ(T_n) ≤ n·a_K + 2log₂((n+1)/(n−1)) and χ(T_n^⊗2) ≥ n(log₂K)/K, where a_K = log₂(1+9/K). Hence Δχ(T_n) ≥ nδ_K − 4log₂((n+1)/(n−1)).

• Scaling of the gap: Δχ(T_n) = Θ_K(n) = Θ_K(√q_in,n), while q_out,n = n log₂K. The input-qubit count is q_in,n = (b_K/ln 2)n² + 2n log₂K + 1 + o(1), so the gap grows like the square root of the input-qubit count and linearly in the output qubits.

• Gap per output qubit: liminf Δχ(T_n)/q_out,n ≥ r_K := δ_K/log₂K = 1/K − 2ln(1+9/K)/ln K > 0, and r_K = (1 − 18/ln K)/K + O(1/(K² ln K)) as K → ∞.

• A concrete parameter choice: K = ⌈e^19⌉ = 178,482,301 gives δ_K ≈ 8.08 × 10⁻⁹, r_K ≈ 2.95 × 10⁻¹⁰, and n₀(K) = 102,401. The paper notes these describe the proved sufficient guarantee and that actual gaps may be larger.

• Sufficient condition for positivity: δ_K ≥ (ln K − 18)/(K ln 2), so ln K > 18 suffices for δ_K > 0.

• Why regrouping a fixed channel cannot work: For any fixed Φ, Δχ(Φ^⊗m)/m = 2[χ(Φ^⊗2m)/(2m) − χ(Φ^⊗m)/m] → 0 by the regularized capacity formula, so a gap linear in the number of uses requires a genuinely new channel for each n.

• Capacity separation (Corollary 1.2): C(T_{K,n}) − χ(T_{K,n}) ≥ (1/2)nδ_K − 2log₂((n+1)/(n−1)), and liminf χ(T_{K,n}^⊗2)/(2χ(T_{K,n})) ≥ 1 + δ_K/(2a_K) ≥ ln K/18. Consequently, for every A > 0 and R > 0 there is a finite-dimensional channel T with χ(T) > 0, C(T) − χ(T) ≥ A, and χ(T^⊗2)/(2χ(T)) ≥ R.

• Vanishing single-use Holevo information (Corollary 1.3): For every ε > 0 and R > 0 there is a finite-dimensional channel with χ(T) ≤ ε and (1/2)χ(T^⊗2) ≥ R. A sequence T^(K) exists with χ(T^(K)) → 0, (1/2)χ((T^(K))^⊗2) → ∞, and C(T^(K)) → ∞, obtained with n_K = ⌈K/√(ln K)⌉ and η_K = K⁻¹.

• Input cost of that separation (Remark 1.4): With the explicit construction, q_in = (280/ln 2 + o(1))K², so χ(T^(K)) = Θ(1/√(log q_in)) while (1/2)χ((T^(K))^⊗2) = Ω(√(log q_in)).

• Entropy bound behind the gap: For block inputs, Tr F_n(ρ)² ≤ 2^η K^{−n}(1+9/K)^n, giving S_min(F_n) ≥ n[log₂K − log₂(1+9/K)] − η; a product of n Bell inputs gives a joint entropy deficit of at least n(log₂K)/K, so 2S_min(F_n) − S_min(F_n ⊗ F̄_n) ≥ nδ_K − 4log₂κ.

• Not reported: The paper gives no experimental demonstration, no numerical simulation of the channels, and no optimized constants; it states that the constants in the dimension bounds are not optimized.

Methodology in Plain English

The starting point is Hastings's insight that entanglement across channel uses can help. The author builds a channel from K unitaries acting on ℂ^N: a state is tagged with a label recording which unitary was applied, and discarding the original system leaves a "complementary" channel whose K-dimensional output records the overlaps between the vectors U_i x.

The trick for the joint-entropy upper bound is to pair this channel with its complex conjugate. The maximally entangled Bell state is invariant under U_i ⊗ conjugate(U_i), so the K matching branch pairs collapse into a single pure state, and the resulting mixture has Shannon entropy at most 2log₂K − (log₂K)/K. This holds for any choice of unitaries.

The hard part is the opposite direction: ensuring that every output of the single channel is close to maximally mixed, even for inputs entangled across all n tensor factors. The author borrows a reference model from free probability — shift operators on a basis indexed by reduced words in free groups — where Haagerup's inequality bounds the norm of weighted sums of shifts by the size of their coefficients. Collins–Youn's product-group version handles one free group per tensor factor, which is exactly what is needed for entangled block inputs. Bordenave–Collins's tensor-product strong-convergence theorem then transfers the operator-norm bound to genuine finite random unitary matrices; operator-norm convergence, not just moment convergence, is essential because moment information alone can miss exceptional eigenvalues.

Finally, standard channel conversions — an input switch together with Shor's Weyl-covariant extension — turn the minimum-output-entropy gap into a two-use Holevo gap for a single channel. A separate section linearizes the relevant polynomials and reduces the number of independent Haar matrices to two per factor, producing the explicit N = ⌈e^{b_K n}⌉ and the quadratic input-qubit cost.

Why This Matters

Impact on research. Prior gap bounds were bounded as dimensions grew: Belinschi–Collins–Nechita reached gaps approaching one bit, and later work kept the gaps bounded. This paper shows the gap is unbounded in finite dimensions and pins down its scaling, settling the qualitative question and giving the first explicit dimension accounting. It also cleanly separates the Holevo story from the older Rényi-entropy story, where gaps proportional to log of the output dimension were already known for every fixed order p > 1.

Potential real-world applications (not discussed in the paper; these are plausible implications, not reported results):

• Designing encoders for quantum communication links that deliberately block and jointly encode several channel uses to exploit entanglement across uses.
• Benchmarking error-corrected quantum memories and repeaters, where knowing whether joint encoding helps bounds the value of complex entangled input states.
• Setting expectations for quantum key distribution and entanglement-assisted protocols that rely on Holevo-type capacity formulas.
• Guiding architecture decisions in quantum networking, where the quadratic input-qubit cost is a concrete resource constraint.

Industry relevance. The result is a foundational statement about the limits of classical communication over quantum channels. Because the constructed channels require enormous input dimensions and the guaranteed gap per output qubit is extremely small, the paper offers no immediate engineering recipe; its industrial value is in calibrating what joint encoding can and cannot buy, and in supplying proven bounds that protocol designers can cite.

Future Directions

• Reduce the input-qubit cost. The paper's construction needs Θ_K(n²) input qubits, while the scaling criterion it cites requires both input and output qubit counts to grow linearly with the gap. Closing this is explicitly left open.

• Optimize constants and thresholds. The guaranteed gap per output qubit is extremely small and the sufficient input dimensions and threshold n₀(K) are very large. The author states the constants are not optimized and that different linearization methods and sharper random-matrix estimates could improve them.

• Derandomize the construction. The construction is probabilistic; efficiently finding suitable unitaries and verifying the required norm bound remain open. The paper compares this with concurrent deterministic constructions by Shou–Gorshkov and by Cheng–Wu, noting those have input-qubit cost exponential in the gap.

• Improve the leading entropy-deficit coefficient. The scalar Haagerup constant 3 is asymptotically sharp, so beating the leading coefficient by this route requires additional structure that holds uniformly over tensor powers.

• Additivity between distinct channels. The paper notes that additivity of C between different channels remains a separate open problem and is not addressed here.

Target Audience

Quantum information theorists and mathematical physicists working on channel capacities, additivity problems, and entropy inequalities will get the most from this paper. It is also relevant to researchers in free probability and random matrix theory interested in quantitative strong-convergence applications, and to readers interested in machine-assisted formalization, given the Lean certificate. Graduate students with a background in quantum Shannon theory and some exposure to free probability could follow the main results, though the proofs require substantial technical maturity.

Authors’ abstract

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.