Source-linked AI summary
Unbounded Holevo additivity gaps in finite dimensions
Jinzhao Wang
TL;DR
Finite-dimensional channels had not been shown to have unbounded two-use Holevo additivity gaps, motivating the question of how such gaps scale with channel dimensions. The paper combines entropy bounds with free-group estimates and finite-dimensional approximation to construct channels with linearly growing gaps. It also obtains channels with vanishing single-use Holevo information and diverging two-use information and classical capacity.
Problem
Whether two-use Holevo additivity gaps can grow without bound in finite dimensions, and how they scale with input and output qubits, remains the central question.
Source: §1 · pp. 1–2Method
The proof combines Bell-input entropy bounds, product-group Haagerup estimates, and finite-dimensional strong-convergence bounds, then applies channel extensions.
Source: §1 · p. 2, §2.2 · p. 11Results
The minimum-output-entropy gap grows linearly with n for fixed η and sufficiently large fixed K, and a sequence has vanishing single-use Holevo information with diverging two-use information and classical capacity.
Source: §1 · pp. 3, 5Takeaways & Limitations
An unbounded two-use gap gives an unbounded advantage from encoding jointly across channel uses.
Source: §1 · p. 2The construction is probabilistic; efficient unitary discovery and verification of the required norm bound remain open.
Source: §1 · p. 6
Abstract
from arXiv · showhide
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(\Theta_K(n^2))$, and \[ \chi(T_n^{\otimes2})-2\chi(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.
1 Introduction and main results
The paper asks whether finite-dimensional channels can have unbounded two-use Holevo additivity gaps and how those gaps scale with input and output size. It combines entropy bounds, free-group estimates, and finite-dimensional approximation to construct channels with linearly growing gaps and a quadratic input-qubit cost.
1 Introduction and main results
- Earlier established Holevo-additivity gaps remained bounded as channel dimensions grew, despite prior improvements approaching one bit [BCN16].The paper also notes that improving the quadratic input cost remains open and that the guaranteed gap per output qubit is extremely small.Source: §1 · pp. 1, 6
- The construction compares a lower bound on every individual output entropy with an upper bound on joint output entropy for a Bell input.The Bell-input estimate gives a joint entropy upper bound of 2 log2 K − (log2 K)/K, and the corresponding output of F ⊗ F has the same entropy.Source: §1 · p. 2
- To bound every output entropy, the authors control output purity through a uniform operator-norm bound on combinations of U_i*U_j.The purity estimate uses S(σ) ≥ −log2 Tr σ^2.Source: §1 · p. 2
- The norm bound uses Collins–Youn’s product-group extension of Haagerup’s inequality for tensor blocks of free-group shifts.Grouping terms by their nontrivial tensor factors lets the inequality control inputs entangled across all n factors.Source: §1 · p. 3
- Strong convergence transfers the reference-model bound to finite matrices, controlling operator norms as well as normalized trace moments.Norm convergence matters because moment convergence alone can miss exceptional eigenvalues.Source: §1 · p. 3
- The minimum-output-entropy gap grows linearly with n for fixed η and sufficiently large fixed K, yielding a linear two-use Holevo gap after channel extensions.A product of n Bell inputs gives a joint entropy deficit of at least n(log2 K)/K; the input switch and Weyl extension transfer the bound to the Holevo gap.Source: §1 · pp. 2–3
- For fixed K, the explicit construction uses Θ_K(n^2) input qubits and n log2 K output qubits.The dimension bound uses N = ⌈e^(b_K n)⌉ with b_K = O(ln K) and entropy error O(1/n).Source: §1 · p. 3
- A sequence of finite-dimensional channels has single-use Holevo information tending to zero while two-use Holevo information and classical capacity diverge.The paper relates the two-use gap to an advantage from encoding jointly across channel uses.Source: §1 · pp. 2, 5
2 Qualitative realization of unbounded Holevo gaps
The section constructs finite-dimensional block channels with growing minimum-output-entropy gaps, then converts those gaps into unbounded two-use Holevo gaps.
2.1 Finite-dimensional block channels and their entropy bound
- Product-group Haagerup bounds and finite-dimensional strong convergence yield block channels whose adjoint norm bound implies a minimum-output-entropy bound.The entropy estimate controls output purity and gives Smin(F) ≥ log L − log(1 + Lt^2).Source: §2.1 · pp. 8, 10
2.2 The minimum-output-entropy gap
- Pairing the complementary channel with its conjugate and using a Bell input gives a joint-output entropy bound from a mixture of pure states.For tensor blocks, the local Bell outputs form a tensor product, so their entropies add.Source: §2.2 · p. 11
2.3 Converting the entropy gap into a Holevo gap
- A switch combines the block channel and its conjugate, while the Weyl-covariant extension makes the single-use Holevo quantity equal to log L − Smin(Fn).The resulting channel has input dimension 2N^nK^{2n} and output dimension K^n.Source: §2.3 · pp. 11–12
- For fixed K with δK > 0, the constructed channels satisfy ∆χ(T) ≥ nδK − 2η, which diverges with n.The channel dimensions may depend on n.Source: §2.3 · p. 13
3 Quantitative finite-dimensional approximation
This section proves a uniform finite-matrix norm estimate for the block channel using a quantitative approximation strategy. The proof combines observable tests, represents the required generators using two base generators per factor, and reduces the resulting polynomial to degree one.
3 Quantitative finite-dimensional approximation
- The constructed unitary tuples yield the uniform bound ∥F_n*(A)∥ ≤ κc^n∥A∥_2 for every traceless Hermitian A in M_(K^n)(C).The proposition supplies tuples for each n ≥ n0(K).Source: §3 · p. 14
3.1 Step 1: combine the observable tests
- A symmetric 1/n-net of traceless Hermitian unit-Hilbert–Schmidt observables is combined into one polynomial whose norm is the largest norm among its tests.The prescribed test A* also controls the first error factor.Source: §3.1 · pp. 14–15
3.2 Step 2: use two base generators
- Representing the K generators in each factor as words in two base generators limits the construction to two independent Haar unitaries per factor.The derived K unitaries within a factor need not be independent; the words have length at most ℓ = 2⌊log2(K − 1)⌋ + 1.Source: §3.2 · p. 16
3.3 Step 3: reduce to a linear polynomial
- Repeated factorization splits tensor supports and shortens within-factor words, enlarging coefficients while controlling backward relative error before a norm-preserving Hermitian dilation.The final dilation produces a self-adjoint linear polynomial; the shortening steps are omitted when ℓ = 1.Source: §3.3 · pp. 16, 19, 20, 21
Appendix B.2 sums the logarithms of these products and proves, for every n ≥n0(K),
Theorem 1.1 follows by applying the input switch and Weyl extension to the tuples from Proposition 3.1. The random-matrix estimate and controlled error transfer provide the finite-dimensional norm bound used in that construction.
Appendix B.2 sums the logarithms of these products and proves, for every n ≥n0(K),
- The product of error-transfer factors satisfies T_nε_n ≤ 1/n, while Step 4 verifies that intermediate errors remain within the required bound.The reductions are undone in reverse order to recover the estimate for P.Source: Appendix B.2 · p. 21, §3.4 · p. 22
3.4 Step 4: apply the random-matrix estimate
- With positive probability, the random-matrix estimate gives H a relative norm error at most ε_n, which is transferred back through the reductions to P.The fixed realization is chosen from the event in (3.16), and the backward calculation checks the error-transfer conditions.Source: §3.4 · p. 22
Appendix B.2 sums the logarithms of these products and proves, for every n ≥n0(K),
- Applying the input switch and Weyl extension to Proposition 3.1's tuples yields T_n with input dimension 2N^nK^(2n) and output dimension K^n.The bound (3.1) supplies the hypothesis with κ = (n + 1)/(n − 1).Source: §3.4 · p. 23
A Algebraic tools for reducing the word length
The appendix's algebraic tools support the reductions used in the proof by providing short words, factorizations, and bounds on their costs.
A Algebraic tools for reducing the word length
- The algebraic tools provide short words for the second construction step.Source: A Algebraic tools for reducing the… · p. 23
- They provide factorizations used in the third construction step.Source: A Algebraic tools for reducing the… · p. 23
- The tools bound coefficient size and error during these reductions.Source: A Algebraic tools for reducing the… · p. 23
A.1 Short words in two base generators
This subsection embeds the free group on K generators into the free group on two generators using short generator words. The embedding preserves regular-representation polynomial norms, including with matrix coefficients and tensor products.
A.1 Short words in two base generators
- For every K ≥ 2, F_K embeds into F_2 with generator images of length at most 2⌊log2(K − 1)⌋ + 1.Source: §A.1 · p. 23
- A covering-graph construction yields the short words by using a binary-tree spanning structure and completing partial label maps to permutations.The remaining K edges give a free basis, with word length controlled by the tree depth.Source: §A.1 · p. 23
- The embedding preserves regular-representation norms for polynomials with matrix coefficients and for direct products of the groups.Restricting F_2's regular representation to the embedded subgroup decomposes it into copies of that subgroup's regular representation.Source: §A.1 · p. 23
A.2 Factorization and error transfer
This appendix constructs a positive-matrix factorization for finite-set group polynomials and transfers norm estimates, including a relative-error bound, between representations.
A.2 Factorization and error transfer
- For a finite set S, the factorization builds positive block matrices from inverse pairs to represent polynomial terms while controlling a constant term.The construction adds one positive matrix per inverse pair and handles self-inverse elements with half of the same matrix.Source: §A.2 · pp. 23–24
- The lemma also gives a relative-error implication when ∥Q(π)∥ is at most (1 + e) times ∥Q(λG)∥, for 0 ≤ e ≤ 1.The displayed transfer uses the factorization bounds and the inequality (1 + e)^2 − 1 ≤ 3e.Source: §A.2 · pp. 24–25
- The resulting positive operator has largest spectral value ∥P(π)∥ + θ, establishing the factorization bound.The proof bounds θ using Cauchy–Schwarz and |W| ≤ B^2.Source: §A.2 · p. 25
B The random-matrix estimate and parameter bounds
The appendix makes the two-generator Bordenave–Collins estimate explicit by repairing two intermediate path-counting bounds while retaining the same N^-1/2 error.
B The random-matrix estimate and parameter bounds
- The revised two-generator estimate retains the N^-1/2 error after correcting two intermediate counting bounds.The earlier bounds fail on explicit paths; the replacements use corrected counts and a weighted enumeration of path classes.Source: B The random-matrix estimate and… · p. 25
- One repaired count concerns important exploration times, and the other counts blocks between first and last edge visits.The corrected bounds support the weighted path-class enumeration used in the estimate.Source: B The random-matrix estimate and… · p. 25
- The remaining subsections verify the parameter bounds used in Section 3.Source: B The random-matrix estimate and… · p. 25
B.1 The two-generator Haar estimate
This subsection proves an explicit two-generator Haar estimate for self-adjoint linear polynomials, using corrected path counts and successive replacement of Haar pairs by regular generators.
B.1 The two-generator Haar estimate
- The one-pair estimate gives the explicit constant c = 1 in the two-generator, self-adjoint case.The estimate is applied to finite-support polynomial coefficients arising in the iteration, not arbitrary traced C*-algebras.Source: §B.1 · p. 26
- For active classes, δ = e1 + 2s, and the geometric series over e1 and s are each at most 2 in the summation bounding |Dt|.Source: §B.1 · pp. 27–28
- The path-weight argument repairs the prior block-count bound: r ≤ 3ê can fail, while marked blocks satisfy M ≤ 2ê and r − M ≤ M − 1.The passage gives an active closed path with ê = 2 and r = 7 as a counterexample to the earlier bound.Source: §B.1 · p. 27
- A second correction replaces the claimed δ + 1 bound on important steps, which can fail, with a bound that permits weighted enumeration.The passage supplies an active path with defect δ = 2 and four important steps.Source: §B.1 · p. 28
- Chronological encoding records important-step positions and bounds the total weight of functions by (1 + 64t^2z)^t.Taking z = p^-3 yields the stated bound for t ≤ p before refined classes are counted.Source: §B.1 · p. 28
- Replacing Haar pairs one at a time and converting operator norms to normalized p-norms yields the tensor-product estimate.At each stage, the conditioned polynomial permits the one-pair estimate; the final stage needs no further norm conversion.Source: §B.1 · p. 29
B.2 Coefficient size and error multiplication
This subsection bounds the coefficient-reduction and error costs using an explicit threshold in n and estimates in terms of u = 1 + ln K + ln n.
B.2 Coefficient size and error multiplication
- For K ≥ 2, the parameter choice requires n ≥ n0(K) = ⌈256(1 + ln K)^2⌉.Under this threshold the passage also derives n > 512 and u > 15/2.Source: §B.2 · pp. 29–30
- The reduction parameters satisfy q + s ≤ 5u/2 and ln(2n) ≤ u.These bounds follow after summing the reduction costs and applying the stated parameter inequalities.Source: §B.2 · p. 30
- The total error factor is bounded by T_n ≤ e^(γ_K n).The derivation combines the logarithmic error contributions under the threshold assumptions.Source: §B.2 · p. 31
B.3 Verification of the final norm error
The final norm error is verified by bounding its three contributions and checking that the resulting estimates decrease for n ≥ 64. For n ≥ n0(K) > 64, these bounds give En ≤ εn/16.
B.3 Verification of the final norm error
- The error is decomposed as En = An + Dn + Rn, with Rn = n ln(1 + N^-1/2).The estimates use N = ⌈e^(bK n)⌉ and bounds on p and the coefficient size.Source: §B.3 · p. 32
- The three resulting bounds decrease for n ≥ 64, and their values at n = 64 are bounded using e > 2 and 1494 < 2^11.The logarithmic derivatives are 3/n − 1/2, 4/n − 3/2, and 2/n − 1.Source: §B.3 · p. 32
- For n ≥ n0(K) > 64, the final bound is En ≤ εn/16.The proof then compares this bound with the required logarithm using ln(1 + x) ≥ x/(1 + x).Source: §B.3 · p. 32