CS Paper Radar

Unbounded Holevo additivity gaps in finite dimensions

Jinzhao Wang

cs.IT quant-phmath-ph ·submitted 2026-09-16 06:52 UTC · v2
code/data

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.

Comment
22+8pp; v2:added a short discussion of concurrent works; corrected estimates in Appendix B; added a Lean certificate: https://github.com/JWang226/Holevo-Additivity-Gap

Closest papers

Nearest neighbours by meaning across the whole index.

Finite attainment and efficient computation of regularized quantum channel relative entropy

cs.IT quant-ph ·2026-11-02 ·Yiwei Xu, Kun Fang
similarity 0.70
Abstract · comments are welcome

Quantum channel relative entropy can be nonadditive, making its regularization essential for asymptotic analysis. We study when the regularized value is attained at finite blocklength and how efficiently it can be approximated. For the first question, we establish a sharp dichotomy: the regularized value is either attained already at the single-copy level, implying additivity at every blocklength, or is never attained at any finite blocklength. Notably, a simple two-copy additivity test distinguishes between these alternatives for qubit channels and for channel pairs in arbitrary dimensions admitting an interior optimizer. We further show that both the interiority condition and finite nonattainment are generic, holding for almost every channel pair. For the second question, we establish explicit convergence rates for approximating the regularized channel relative entropy. For fixed channel dimensions, $\widetilde O(\varepsilon^{-3/2})$ channel copies suffice to approximate the regularized value to additive accuracy $\varepsilon$. Alternatively, a semidefinite hierarchy achieves the same accuracy at level $\widetilde O(\varepsilon^{-2})$, yielding a certified polynomial-time approximation. Together, these results reveal the intriguing structure and generic behavior of regularized channel relative entropy, sharpening our understanding of both its analytical and computational aspects.

0.21

Multiplicative Semidefinite Programming Upper Bounds on Quantum No-Signalling-Assisted Zero-Error Capacity

cs.IT quant-ph ·2026-10-15 ·Xin Li, Yinan Li
theory similarity 0.69
Abstract · 23 pages

We study zero-error communication and exact simulation of quantum channels assisted by quantum no-signalling correlations. For a channel with Kraus operator space $K$, we introduce a semidefinite programming parameter $Γ(K)$ that is exactly multiplicative under tensor products and upper-bounds $Θ_{\rm NS}(K)$, where $\log_2Θ_{\rm NS}(K)=C_{0,\rm NS}(K)$ and $C_{0,\rm NS}(K)$ denotes the asymptotic quantum no-signalling-assisted zero-error capacity. Among known upper bounds on $Θ_{\rm NS}$ given by semidefinite programs, $Γ$ is the tightest. We also prove that the previously introduced simulation lower bound $Σ^{-}(K)$ is exactly multiplicative and satisfies $Θ_{\rm NS}(K)\leqΓ(K)\leqΣ^{-}(K)\leqΓ(K)^2$. Using this multiplicativity, we show that neither $S_{0,\rm NS}(K)=\log_2Σ^{-}(K)$ nor its regularized extension $S_{0,\rm NS}(K)=\lim\nolimits_{n\to\infty}n^{-1}\log_2Σ^{-}(K^{\otimes n})$ holds in general. This answers an open question about the asymptotic simulation cost $S_{0,\rm NS}(K)$. For classical-quantum channels, we obtain sharp bounds. If $r$ is the effective output dimension, then $Θ_{\rm NS}\leqΓ\leq(1+r^{1/2})Θ_{\rm NS}/2$ and $Γ\leqΣ^{-}\leq(1+r^{1/2})Γ/2$. If $k$ is the minimum rank of the output support projections, then $Σ^{-}/Θ_{\rm NS}\leq[(1+r^{1/2})/(1+k^{1/2})]^2$, and this bound is sharp for every $1\leq k\leq r$. Thus, we obtain the sharp bound $S_{0,\rm NS}-C_{0,\rm NS}\leq2\log_2[(1+r^{1/2})/(1+k^{1/2})]$.

0.14

Non-Multiplicativity of the Holevo Barycenter of Quantum Channels

cs.IT quant-ph ·2026-09-08 ·Sayantan Chakraborty, Stefano Mancini, Leonardo Rossetti, Andreas Winter
similarity 0.67
Abstract

The Holevo barycenter of a quantum channel is the unique output state obtained as the average output of any ensemble achieving the Holevo capacity. Given two quantum channels, the multiplicativity problem asks whether this barycenter tensorizes under parallel composition, namely whether the barycenter of the product channel coincides with the tensor product of the individual barycenters. This question is closely related to the additivity problem for the Holevo capacity: additivity implies tensorization of the Holevo barycenter, while tensorization alone is not sufficient for additivity. Although a construction is known that demonstrates the existence of channels with non-additive Holevo capacity, their corresponding Holevo barycenters still tensorize, leaving open whether multiplicativity might ultimately hold universally. Here, we answer this question in the negative by exhibiting channels for which the Holevo barycenter is not multiplicative under the tensor product of the channel with itself. Moreover, we show that the entropy of the Holevo barycenter is neither universally subadditive nor universally superadditive under tensor product.

0.26

Entanglement cost of quantum depolarization

cs.IT quant-ph ·2026-09-17 ·Kun Fang
theory similarity 0.66
Abstract · comments are welcome

Entanglement cost is the asymptotic rate of Bell pairs required to prepare a quantum state. Its regularized definition has made exact evaluation difficult, even for isotropic states (i.e., depolarized maximally entangled states). In this work, we determine the entanglement cost of every qubit isotropic state and, more generally, every two-qubit Bell-diagonal state. Our proof uses a family of suitably tuned qubit semigroups to transform a general log-Sobolev entropy bound into supporting lines of Wootters' function. A recent exact tensorization theorem of Dong et al. [arXiv:2606.17729] extends these bounds to arbitrarily many copies, yielding a general lower bound on entanglement cost. Matching this bound with the entanglement of formation also determines the exact cost for a broader class of two-qubit states. For qudit isotropic states, we derive another general lower bound from the full depolarizing $2\to 3$ norm. This bound substantially improves on the PPT-relative entropy of entanglement and nearly matches the entanglement of formation, leaving a gap of at most $2\%$ of $\log d$ that vanishes as $d$ grows. Finally, the exact qubit results and qudit bounds extend to the entanglement cost of preparing quantum depolarizing channels under both parallel and sequential strategies.

0.08

A Tight Second-Order Converse Bound for Variable-Length Feedback Codes

cs.IT ·2026-09-10 ·Recep Can Yavas
similarity 0.66
Abstract · 26 pages, submitted to Information Theory Transactions

We study variable-length feedback (VLF) codes over a discrete memoryless channel under average decoding-time and error-probability constraints. In the non-vanishing error probability regime, Polyanskiy, Poor, and Verdú (2011) derive achievability and converse bounds on the logarithm of the maximum achievable codebook size. These bounds establish the $ε$-capacity but leave an order-$\log N$ gap in the second-order expansion, where $N$ is the average decoding time. Yavas and Tan (2025) improve the coefficient of $\log N$ in the achievability bound from $-1$ to $-\frac{C}{C_1}$, where $C$ is the channel capacity and $C_1$ is the largest Kullback--Leibler divergence between two conditional output distributions. We derive a converse with the same coefficient, establishing the second-order fundamental limit for every positive-capacity discrete memoryless channel with finite $C_1$. The result also covers the moderate-deviations and error-exponent regimes, including polynomially decaying error probabilities. The converse uses Rényi entropy and the extrinsic Jensen--Shannon divergence. We also derive necessary properties of asymptotically optimal VLF codes. First-order-optimal codes must have an early-stopping branch, and second-order-optimal codes must additionally exhibit communication and confirmation behavior. Finally, for the binary erasure channel, we determine the exact minimum expected decoding time for every message-set size and admissible error probability.

0.11

Information-Spectrum General Formulas for the Capacity Region of Classical-Quantum Multiple Access Channels

cs.IT quant-ph ·2026-11-05 ·Takuya Kubo, Hiroshi Nagaoka
similarity 0.65
Abstract · 11 pages

For classical-quantum multiple access channels (cq-MACs) with two senders, we give several general expressions for the capacity region, valid for arbitrary sequences of channels. In the case of asymptotically vanishing error ($\varepsilon=0$), the capacity region is expressed in terms of spectral inf-mutual information rates. For every $0\le\varepsilon<1$, the $\varepsilon$-capacity region is expressed in terms of a quantity defined through a linear combination of three alternative hypotheses. In particular, the outer bound of Kubo and Nagaoka (2015) is tight. Our results include the quantum counterpart of the general formula of Han (1998) for the classical MAC. The most important ingredient is the one-shot inner bound of Sen (2021), which we apply to each member of an arbitrary channel sequence.

0.25

Improved Quantum Query Bounds for Boolean Matrix Product Verification

cs.DS quant-ph ·2026-09-30 ·Amin Shiraz Gilani, François Le Gall, Xingyu Zhou
theory similarity 0.64
Abstract · 38 pages

We prove the first non-trivial upper bound for the quantum query complexity of Boolean Matrix Product Verification ($\mathsf{BMPV}$), answering a longstanding open question in quantum query complexity. For $n\times n$ matrices, our upper bound is $\widetilde O(n^{17/12})$, improving on the standard $O(n^{3/2})$ bound obtained using Grover search by Buhrman and Špalek [SODA 2006]. We complement this result by showing an $Ω(n^{5/4})$ lower bound, which improves over the previous best known lower bound of $\widetildeΩ(n^{19/18})$ by Childs, Kimmel, and Kothari [ESA 2012]. Our approach centers on a connection with Orthogonal Vectors ($\mathsf{OV}$), which asks whether an indexed list of $n$ Boolean vectors of dimension $n$ contains two vectors with disjoint supports. In particular, we prove equivalences between $\mathsf{OV}$ and $\mathsf{BMPV}$ and establish the above bounds for $\mathsf{OV}$. We also prove a tight $\widetilde Θ(n^{3/2})$ bound for a variant of $\mathsf{BMPV}$ that asks whether the product contains a given row vector. Together, these results imply a polynomial separation between the quantum query complexities of deciding whether a graph has radius at most two and whether it has diameter at most two.

0.25

Information Complexity of Inner Product and Matrix Multiplication via Shannon-to-Min-Entropy Conversion

cs.IT cs.CC ·2026-11-02 ·Xiaohong Cai, Mingyang Zhu
theoryhot direction similarity 0.64
Abstract · 38 pages, including appendices

We determine the information complexity of matrix multiplication over finite fields under independent uniform inputs, up to a universal additive constant. The binary inner-product case resolves the open question of Braverman, Garg, Pankratov, and Weinstein on the optimal dependence of information complexity on the error probability. For inputs in $\mathbb F_2^m$ and error at most $\varepsilon\in[0,1/2]$, the information complexity with output at Bob lies between $(1-2\varepsilon)m-c_0$ and $(1-2\varepsilon)m$, where $c_0<4.772$ is a universal constant. For independent uniform matrices $X\in\mathbb F_q^{t\times m}$ and $Y\in\mathbb F_q^{s\times m}$, where $t\le s$, computing $XY^{\mathsf T}$ with output at Bob and error at most $\varepsilon\in[0,1]$ has information complexity $(1-q^{ts}\varepsilon/(q^{ts}-1))^+mt\log_2q$, up to an additive gap of less than $9.544$ bits. This gap is independent of the matrix dimensions, field size, and error. At zero error, the information complexity is exactly $mt\log_2q$. The information lower bounds for both inner product and matrix multiplication follow from a new Shannon-to-min-entropy theorem for convolution on discrete groups. Let $Q_1,\ldots,Q_k$ be the finitely supported distributions of independent random variables taking values in a discrete group, and let $s$ be the largest support size. We show that if $k\ge\lceil\lfloor\log_2s\rfloor\ln2\rceil$, then the min-entropy of their ordered product is at least the average Shannon entropy of the $Q_i$ minus $c_0$ bits. This holds for arbitrary discrete groups, including infinite and noncommutative groups, even when the input distributions differ. The leading coefficient of the logarithmic threshold is optimal.

0.38