Exact Asymptotic Rates and an Exponential Strong Converse for quantum SMP and One-Way Communication

• URL: http://arxiv.org/abs/2609.14658v1
• Date: Sun, 13 Sep 2026 16:55:55 GMT
• Title: Exact Asymptotic Rates and an Exponential Strong Converse for quantum SMP and One-Way Communication
• Abstract summary: We prove that the optimal worst-case communication per instance for $fn$ converges to [ Dparallel(f)=log|mathrmRow(f)|+log|mathrmCol(f)|.<n>We also prove that the same threshold governs an exponential strong converse.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• 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\le\varepsilon<1$, we prove that the optimal worst-case communication per instance for $f^n$ converges to \[ D^\parallel(f)=\log|\mathrm{Row}(f)|+\log|\mathrm{Col}(f)|, \] where $\mathrm{Row}(f)$ and $\mathrm{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-\varepsilon)D^\parallel(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^\parallel(f)$ replaced by $\log|\mathrm{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 papers

• On the Limits of Quantum Multiparty Simultaneous Communication [1.7205106391379026]
  We establish a multiparty exponential separation through $nameIC_k,n$, a natural $k$-party generalization of textscIndex Coordination.<n>We show that quantum superposition cannot efficiently simulate the coordination afforded by public randomness, extending this separation to arbitrary $k$.
  arXiv  Detail & Related papers  (2026-09-09T15:07:22Z)
• Distributed Monogamy of Entanglement limits Quantum Channel Simulation [2.277447144331876]
  We introduce fractional extendibility, which gives a finer characterization of the quantum correlation that is leaked to the environment.<n>We also establish the distributed monogamy of entanglement: for any state on $AB_Bdots B_n$, the maximum average probability of extracting an EPR pair from a random subset of $k leq n/2$ systems among the $B_i$'s is the fraction $k/n$.
  arXiv  Detail & Related papers  (2026-07-09T15:26:41Z)
• Quantum Multi-Level Estimation of Functionals of Discrete Distributions [23.53427184324404]
  We propose a quantum multi-level estimation framework for a functional $sum_i=1n f(p_i)$ of a discrete distribution.<n>We present efficient quantum estimators for the $q$-Tsallis entropy of discrete distributions.
  arXiv  Detail & Related papers  (2026-05-05T12:25:17Z)
• Hardness of High-Dimensional Linear Classification [58.29089693778071]
  We establish new exponential in dimension lower bounds for the Maximum Halfspace Discrepancy problem.<n>Both are fundamental problems in computational geometry and machine learning in their exact and approximate forms.
  arXiv  Detail & Related papers  (2026-03-19T15:53:41Z)
• Proving the Limited Scalability of Centralized Distributed Optimization via a New Lower Bound Construction [57.93371273485736]
  We consider a centralized distributed learning setup where all workers jointly find an unbiased bound LDeltaepsilon2,$ better poly-logarithmically in $n$, even in the homogeneous (i.i.d.) case, where all workers access the same distribution.
  arXiv  Detail & Related papers  (2025-06-30T13:27:39Z)
• Quantum advantage in zero-error function computation with side information [10.0060346233449]
  We consider the problem of zero-error function computation with side information.<n>Alice and Bob have correlated sources $X,Y$ with joint p.m.f. $p_XY(cdot, cdot)$. Bob wants to calculate $f(X,Y)$ with zero error.
  arXiv  Detail & Related papers  (2024-02-02T16:41:36Z)
• A Unified Framework for Uniform Signal Recovery in Nonlinear Generative Compressed Sensing [68.80803866919123]
  Under nonlinear measurements, most prior results are non-uniform, i.e., they hold with high probability for a fixed $mathbfx*$ rather than for all $mathbfx*$ simultaneously. Our framework accommodates GCS with 1-bit/uniformly quantized observations and single index models as canonical examples. We also develop a concentration inequality that produces tighter bounds for product processes whose index sets have low metric entropy.
  arXiv  Detail & Related papers  (2023-09-25T17:54:19Z)
• Near Sample-Optimal Reduction-based Policy Learning for Average Reward MDP [58.13930707612128]
  This work considers the sample complexity of obtaining an $varepsilon$-optimal policy in an average reward Markov Decision Process (AMDP) We prove an upper bound of $widetilde O(H varepsilon-3 ln frac1delta)$ samples per state-action pair, where $H := sp(h*)$ is the span of bias of any optimal policy, $varepsilon$ is the accuracy and $delta$ is the failure probability.
  arXiv  Detail & Related papers  (2022-12-01T15:57:58Z)
• A Law of Robustness beyond Isoperimetry [84.33752026418045]
  We prove a Lipschitzness lower bound $Omega(sqrtn/p)$ of robustness of interpolating neural network parameters on arbitrary distributions. We then show the potential benefit of overparametrization for smooth data when $n=mathrmpoly(d)$. We disprove the potential existence of an $O(1)$-Lipschitz robust interpolating function when $n=exp(omega(d))$.
  arXiv  Detail & Related papers  (2022-02-23T16:10:23Z)
• Random quantum circuits transform local noise into global white noise [118.18170052022323]
  We study the distribution over measurement outcomes of noisy random quantum circuits in the low-fidelity regime. For local noise that is sufficiently weak and unital, correlations (measured by the linear cross-entropy benchmark) between the output distribution $p_textnoisy$ of a generic noisy circuit instance shrink exponentially. If the noise is incoherent, the output distribution approaches the uniform distribution $p_textunif$ at precisely the same rate.
  arXiv  Detail & Related papers  (2021-11-29T19:26:28Z)
• 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)
• Capacity Approaching Coding for Low Noise Interactive Quantum Communication, Part I: Large Alphabets [15.078027648304115]
  We consider the problem of implementing two-party interactive quantum communication over noisy channels. For a noiseless qudit channel over a $mathrmpoly(n)$ size alphabet, our main result is a simulation method that fails with probability less than $2-Theta(nepsilon)$ We conjecture that it is optimal up to a constant factor in the $sqrtepsilon$ term.
  arXiv  Detail & Related papers  (2020-01-09T02:48:43Z)

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.