Tight lower bound on the error exponent of classical-quantum channels

• URL: http://arxiv.org/abs/2407.11118v2
• Date: Fri, 19 Jul 2024 11:26:49 GMT
• Title: Tight lower bound on the error exponent of classical-quantum channels
• Authors: Joseph M. Renes,
• Abstract summary: A fundamental quantity of interest in Shannon theory, classical or quantum, is the error exponent of a given channel $W$ and rate $R. Nearly matching lower and upper bounds are well-known for classical channels. I show a lower bound on the error exponent of communication over arbitrary classical-quantum (CQ) channels.
• Score: 2.7195102129094995
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A fundamental quantity of interest in Shannon theory, classical or quantum, is the error exponent of a given channel $W$ and rate $R$: the constant $E(W,R)$ which governs the exponential decay of decoding error when using ever larger optimal codes of fixed rate $R$ to communicate over ever more (memoryless) instances of a given channel $W$. Nearly matching lower and upper bounds are well-known for classical channels. Here I show a lower bound on the error exponent of communication over arbitrary classical-quantum (CQ) channels which matches Dalai's sphere-packing upper bound [IEEE TIT 59, 8027 (2013)] for rates above a critical value, exactly analogous to the case of classical channels. This proves a conjecture made by Holevo in his investigation of the problem [IEEE TIT 46, 2256 (2000)]. Unlike the classical case, however, the argument does not proceed via a refined analysis of a suitable decoder, but instead by leveraging a bound by Hayashi on the error exponent of the cryptographic task of privacy amplification [CMP 333, 335 (2015)]. This bound is then related to the coding problem via tight entropic uncertainty relations and Gallager's method of constructing capacity-achieving parity-check codes for arbitrary channels. Along the way, I find a lower bound on the error exponent of the task of compression of classical information relative to quantum side information that matches the sphere-packing upper bound of Cheng et al. [IEEE TIT 67, 902 (2021)]. In turn, the polynomial prefactors to the sphere-packing bound found by Cheng et al. may be translated to the privacy amplification problem, sharpening a recent result by Li, Yao, and Hayashi [IEEE TIT 69, 1680 (2023)], at least for linear randomness extractors.

Related papers

• Convergence Rate Analysis of LION [54.28350823319057]
  LION converges iterations of $cal(sqrtdK-)$ measured by gradient Karush-Kuhn-T (sqrtdK-)$. We show that LION can achieve lower loss and higher performance compared to standard SGD.
  arXiv  Detail & Related papers  (2024-11-12T11:30:53Z)
• Reliability Function of Classical-Quantum Channels [6.959602244161659]
  We study the reliability function of general classical-quantum channels. We prove a lower bound, in terms of the quantum Renyi information in Petz's form, for the reliability function.
  arXiv  Detail & Related papers  (2024-07-17T08:30:27Z)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  We introduce a variational quantum solver for optimizations over $m=mathcalO(nk)$ binary variables using only $n$ qubits, with tunable $k>1$. We analytically prove that the specific qubit-efficient encoding brings in a super-polynomial mitigation of barren plateaus as a built-in feature.
  arXiv  Detail & Related papers  (2024-01-17T18:59:38Z)
• Lower Bounds on Error Exponents via a New Quantum Decoder [14.304623719903972]
  We show new lower bounds on the error exponent on the classical-quantum and the entanglement-assisted channel coding problem. Our bounds are expressed in terms of measured (for the one-shot bounds) and sandwiched (for the bounds) channel R'enyi mutual information of order between 1/2 and 1.
  arXiv  Detail & Related papers  (2023-10-13T11:22:49Z)
• Noisy decoding by shallow circuits with parities: classical and quantum [0.0]
  We show that any classical circuit can correctly recover only a vanishingly small fraction of messages, if the codewords are sent over a noisy channel with positive error rate. We give a simple quantum circuit that correctly decodes the Hadamard code with probability $Omega(varepsilon2)$ even if a $(1/2 - varepsilon)$-fraction of a codeword is adversarially corrupted.
  arXiv  Detail & Related papers  (2023-02-06T15:37:32Z)
• Quantum computation on a 19-qubit wide 2d nearest neighbour qubit array [59.24209911146749]
  This paper explores the relationship between the width of a qubit lattice constrained in one dimension and physical thresholds. We engineer an error bias at the lowest level of encoding using the surface code. We then address this bias at a higher level of encoding using a lattice-surgery surface code bus.
  arXiv  Detail & Related papers  (2022-12-03T06:16:07Z)
• Achievable error exponents of data compression with quantum side information and communication over symmetric classical-quantum channels [8.122270502556372]
  A fundamental quantity of interest in Shannon theory, classical or quantum, is the optimal error exponent of a given channel W and rate R. I show that a bound by Hayashi for an analogous quantity in privacy amplification implies a lower bound on the error exponent of communication over symmetric classical-quantum channels.
  arXiv  Detail & Related papers  (2022-07-18T19:20:47Z)
• A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
  The threshold theorem is a fundamental result in the theory of fault-tolerant quantum computation. We prove an exponential upper bound on the maximal length of fault-tolerant quantum computation with amplitude noise.
  arXiv  Detail & Related papers  (2022-01-31T22:19:49Z)
• Fault-tolerant Coding for Quantum Communication [71.206200318454]
  encode and decode circuits to reliably send messages over many uses of a noisy channel. For every quantum channel $T$ and every $eps>0$ there exists a threshold $p(epsilon,T)$ for the gate error probability below which rates larger than $C-epsilon$ are fault-tolerantly achievable. Our results are relevant in communication over large distances, and also on-chip, where distant parts of a quantum computer might need to communicate under higher levels of noise.
  arXiv  Detail & Related papers  (2020-09-15T15:10:50Z)
• Quantum Communication Complexity of Distribution Testing [114.31181206328276]
  Two players each receive $t$ samples from one distribution over $[n]$. The goal is to decide whether their two distributions are equal, or are $epsilon$-far apart. We show that the quantum communication complexity of this problem is $tildeO$(tepsilon2))$ qubits when distributions have low $l$-norm.
  arXiv  Detail & Related papers  (2020-06-26T09:05:58Z)
• From Information Theory Puzzles in Deletion Channels to Deniability in Quantum Cryptography [0.0]
  We first conjecture on the basis of experimental data that the entropy of the posterior is minimized by the constant strings. We then establish a connection between covert communication and deniability to propose DC-QKE. We present an efficient coercion-resistant and quantum-secure voting scheme, based on fully homomorphic encryption.
  arXiv  Detail & Related papers  (2020-03-25T22:20:47Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.