Exact Asymptotic Rates and an Exponential Strong Converse for quantum SMP and One-Way Communication
Abstract
Computing many instances jointly can reduce communication per instance. We ask whether such savings occur in the simultaneous-message-passing (SMP) model and how they depend on quantum messages and shared resources. For every finite total function f and fixed error 0≤ε<1, we prove that the optimal worst-case communication per instance for fn converges to D∥(f)=log|Row(f)|+log|Col(f)|, where Row(f) and Col(f) are the sets of distinct rows and columns of the table (f(x,y))x,y. This holds for classical and quantum SMP without shared entanglement, with or without shared randomness. Thus, transmitting row and column indices is asymptotically optimal, even with bounded error, joint computation, and quantum messages. In particular, the exponential advantage of quantum fingerprinting for a single instance of equality without shared randomness disappears in the asymptotic rate. We also prove that the same threshold governs an exponential strong converse: every fixed worst-case communication rate below it forces the probability of computing all n outputs correctly to decay as 2−Ω(n), even on average under a fixed product input distribution. With shared randomness, the optimal expected communication rate is (1−ε)D∥(f). Entanglement shared between each sender and the referee halves both rates; arbitrary tripartite entanglement gives no further reduction. The results extend to a class of total relations and yield one-way characterizations with D∥(f) replaced by log|Row(f)|. Our proof reduces SMP to one-way communication and relates successful computation to sampling based on quantum min-entropy; we also give a simpler proof of the key lemma using the pretty-good measurement.
Related
- An exponential strong converse for private communication over degradable quantum channels
- The exact strong converse exponent for private communication over quantum channels
- Quantum Channel Stein's Lemma with an Exponential Strong Converse
- Exponential strong converse for blind quantum data compression
- Strong converse for the quantum capacity of the pure-loss bosonic channel
BibTeX
@misc{suruga2026exact,
title = {{Exact Asymptotic Rates and an Exponential Strong Converse for quantum SMP and One-Way Communication}},
author = {Daiki Suruga},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.14658},
eprint = {2609.14658},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.14658},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Exact Asymptotic Rates and an Exponential Strong Converse for quantum SMP and One-Way Communication
AU - Daiki Suruga
PY - 2026
DA - 2026/09/13
PB - arXiv
DO - 10.48550/arxiv.2609.14658
UR - https://arxiv.org/abs/2609.14658
AB - Computing many instances jointly can reduce communication per instance. We ask whether such savings occur in the simultaneous-message-passing (SMP) model and how they depend on quantum messages and shared resources. For every finite total function f and fixed error 0≤ε<1, we prove that the optimal worst-case communication per instance for f^n converges to D^∥(f)=log|Row(f)|+log|Col(f)|, where Row(f) and Col(f) are the sets of distinct rows and columns of the table (f(x,y))_x,y. This holds for classical and quantum SMP without shared entanglement, with or without shared randomness. Thus, transmitting row and column indices is asymptotically optimal, even with bounded error, joint computation, and quantum messages. In particular, the exponential advantage of quantum fingerprinting for a single instance of equality without shared randomness disappears in the asymptotic rate. We also prove that the same threshold governs an exponential strong converse: every fixed worst-case communication rate below it forces the probability of computing all n outputs correctly to decay as 2^−Ω(n), even on average under a fixed product input distribution. With shared randomness, the optimal expected communication rate is (1−ε)D^∥(f). Entanglement shared between each sender and the referee halves both rates; arbitrary tripartite entanglement gives no further reduction. The results extend to a class of total relations and yield one-way characterizations with D^∥(f) replaced by log|Row(f)|. Our proof reduces SMP to one-way communication and relates successful computation to sampling based on quantum min-entropy; we also give a simpler proof of the key lemma using the pretty-good measurement.
ER -