Error correction, authentication, and false acceptance, probabilities for communication over noisy quantum channels: converse upper bounds on the bit transmission rate

Technical Summary: Error Correction, Authentication, and False Acceptance Probabilities for Communication over Noisy Quantum Channels

Problem Statement
This paper investigates the fundamental limits of bit transmission rates for classical information communicated over noisy quantum channels in the presence of an eavesdropper, Eve. The central problem addresses a paradoxical scenario in quantum communication: Alice and Bob share a quantum channel with a higher noise level ($N_{A \to B}$) than the channel between Bob and Eve ($N_{B \to E}$). Previous work (specifically arXiv:1804.01797) established lower bounds for transmission rates under low-noise conditions, demonstrating that Alice and Bob could achieve error correction and authentication. However, the author seeks to determine if strict upper bounds (converse results) exist for the bit transmission rate $r$ in this high-noise regime, and whether Alice and Bob can still maintain quantum advantage—specifically, the ability to perform error correction and minimize false acceptance—despite the channel between them being noisier than the channel between Bob and Eve.

Methodology
The paper employs a combination of information-theoretic optimization, game-theoretic modeling, and asymptotic analysis of probability distributions.

1. Information-Theoretic Framework: The analysis centers on the Mutual Information $I(X, Y)$ and conditional Shannon entropies $H(Y|X)$ and $H_Q(Y|Z=z)$. The bit transmission rate $r$ is analyzed through the lens of constrained optimization over probability measures $P_X$. The author formulates a converse result where the goal is to upper bound $r$ using expressions involving these entropies.
2. Pruning and Alphabet Overlap: A critical methodological component is the introduction of a "pruning procedure" and an overlap function $O(X, Y, Z)$. This function determines the intersection of the alphabets used by Alice ($X$), Bob ($Y$), and Eve ($Z$). The paper analyzes the cardinality of these alphabets ($|X|, |Y|, |Z|$) and their pruned subsets ($X^*, Y^*, Z^*$) to determine conditions under which symbols can be removed to maintain quantum advantage.
3. Asymptotic and Calculus Analysis: The author derives strict upper bounds for $r$ by analyzing the asymptotic behavior of doubly logarithmic and logarithmic terms involving the alphabet sizes. This involves computing the first and second derivatives of the proposed converse rate function with respect to alphabet cardinalities. The paper identifies critical points where these derivatives vanish or diverge, establishing conditions for the well-definedness of the transmission rate.
4. Stochastic Domination: The paper utilizes stochastic domination arguments to compare the probabilities of error correction ($p_{EC}$) and false acceptance ($p_{FA}$) between the Alice-Bob channel and the Bob-Eve channel. It leverages game-theoretic objects, including simulators and resource metrics, to formalize the security of the communication.

Key Contributions and Results

• Converse Upper Bound on Bit Transmission Rate (Theorem 1): The paper establishes a strict upper bound for the bit transmission rate $r$ in the converse regime. Unlike the lower bound $r < \sup \min \{I(X,Y), \dots\}$, the converse result posits $r > \sup \min \{I(X,Y), \dots\}$. The derived upper bound is expressed as a piecewise function dependent on the natural logarithm of the alphabet sizes ($|X|, |Y|, |Z|$) and their pruned versions. Specifically, the bound takes the form of sums of double logarithms (e.g., $\log \log (\log |Y^*|/|X^*|) + \dots$) depending on the relative magnitudes of the alphabet cardinalities.
• Stochastic Domination of Probabilities (Theorem 2): The paper proves that even when $N_{A \to B} > N_{B \to E}$ (Alice and Bob's channel is noisier), there exists stochastic domination such that the probability of successful error correction for Alice and Bob ($p_{EC, A \to B}$) is strictly greater than that for Bob and Eve ($p_{EC, B \to E}$). Conversely, the probability of false acceptance is lower for Alice and Bob. This result relies on the overlap function $O(X, Y, Z)$, showing that Alice and Bob can utilize symbols from their alphabets that Eve does not use, thereby preserving their ability to authenticate and correct errors.
• Existence of Suitable Protocols (Theorem 3): The author demonstrates the existence of protocols $\pi_n = (E_n, D_n)$ such that for sufficiently large $n$, Alice and Bob can map bit codewords into the authenticated space $Arn_{A \to B}$ with high probability, even under the derived upper bound constraints.
• Corollaries on Error and False Acceptance:
  • Corollary 1: Establishes a correspondence where a high probability of error correction ($p_{EC} \approx 1$) implies a vanishing probability of false acceptance ($p_{FA} \approx 0$) in the limit of infinitely many bits.
  • Corollary 2: Discusses the stability of the inverse monotonicity of Hamming ball radii with respect to channel noise for transmitted codewords with infinitely many bits.

Significance and Claims
The paper claims to resolve a paradoxical aspect of quantum communication: that quantum advantage in error correction and authentication can persist even when the legitimate channel is significantly noisier than the eavesdropper's channel. The author argues that this advantage is not merely a result of proof artifacts but reflects intrinsic properties of quantum information, specifically related to nonlocality and the ability to prune alphabets to eliminate overlap with the eavesdropper's symbols.

The work suggests that by carefully characterizing the upper bounds on transmission rates through the lens of alphabet cardinality and overlap, one can construct error-correcting codes resilient to noise. The author posits that these findings offer a framework for classifying paradoxical aspects of communication protocols and constructing codes that maximize error correction while minimizing false acceptance, even in adversarial, high-noise environments. The paper explicitly states that these results generalize a counterexample from previous work, showing that Alice and Bob need not sacrifice their security probabilities despite the noise asymmetry.