⚛️ quantum physics

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

This paper establishes that for any finite total function, the optimal asymptotic communication rate per instance in the quantum simultaneous-message-passing model converges to a specific threshold determined by the function's row and column ranks, demonstrating that joint computation and quantum resources offer no advantage over simple index transmission in the limit while proving an exponential strong converse for rates below this bound.

Original authors: Daiki Suruga

Published 2026-09-15

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Daiki Suruga

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the world of information, there is a persistent tension between the cost of sending a message and the value of the information it carries. Imagine two people, Alice and Bob, who are far apart and need to solve a problem together. They cannot talk to each other directly; instead, they must each send a single note to a third person, a referee, who then combines the information to give an answer. This setup, known as simultaneous message passing, is a fundamental test of how efficiently we can communicate when direct conversation is forbidden. For decades, scientists have known that using the strange laws of quantum mechanics—where particles can exist in multiple states at once—can sometimes shrink these notes dramatically. In fact, for certain simple tasks like checking if two long lists of numbers are identical, a quantum note can be exponentially smaller than a classical one, provided the senders do not share any pre-arranged secret code. This has led to a belief that quantum communication offers a massive, perhaps unlimited, advantage over classical methods.

However, a new study by Daiki Suruga at the University of Waterloo challenges the idea that this advantage holds up when we look at the long term. The research asks a deceptively simple question: what happens if Alice and Bob are not just solving one problem, but are tasked with solving thousands or millions of them at the same time? Does the quantum advantage persist, or does it vanish as the number of tasks grows? The answer turns out to be a profound limitation on the power of quantum mechanics in this specific setting. The study proves that when the number of tasks becomes very large, the exponential quantum advantage for these simultaneous messages disappears. Without shared entanglement, the amount of information required to solve the problem, whether using classical bits or quantum bits, converges to the same fundamental limit. However, if the senders share a specific type of quantum connection with the referee before they begin, a distinct quantum advantage remains: the required message size is cut exactly in half, but no further.

The researchers arrived at this conclusion by analyzing the structure of the problems themselves. They looked at a vast class of tasks where the answer depends on the combination of Alice's input and Bob's input. They discovered that the true bottleneck for communication is not the complexity of the calculation, but the sheer number of different ways the inputs can be arranged. Specifically, the optimal amount of information needed is determined by the number of unique rows and columns in the table of all possible answers. To solve the problem perfectly, Alice essentially needs to tell the referee which row of the table her input corresponds to, and Bob needs to specify which column his input matches. The study shows that no matter how cleverly one tries to compress this data using quantum tricks, shared randomness, or joint computation, the total amount of information that must be transmitted per task cannot drop below the sum of these row and column counts.

This finding has a striking consequence for the famous "equality" problem, where Alice and Bob want to know if their data is identical. In a single instance, quantum methods can solve this with a message size that grows only logarithmically with the data length, a massive improvement over classical methods. But the study proves that when solving many such equality problems together, this exponential savings evaporates. Without shared entanglement, the optimal rate for the quantum approach becomes identical to the classical approach: both require a message size that grows linearly with the data length. However, if the senders share entanglement with the referee, a quantum edge remains: the message size is halved compared to the classical case. Yet, this benefit is capped at a factor of two; the message size is reduced, but it cannot be reduced to the tiny logarithmic scales seen in single-instance scenarios.

The paper also establishes a sharp boundary for success. It demonstrates that if the senders try to communicate at any rate even slightly below this optimal limit, their chance of solving all the tasks correctly does not just drop a little; it collapses exponentially fast. If they try to save a small amount of communication per task, the probability of getting the entire set of answers right becomes vanishingly small as the number of tasks increases. This "strong converse" effect means there is no middle ground where one can trade a little communication for a little bit of success. One must either pay the full price of the optimal rate to have a reliable chance of success, or accept that failure is virtually guaranteed. This behavior holds true whether the senders use classical bits, quantum bits, shared randomness, or even complex three-way quantum entanglement.

Surprisingly, the study finds that the location of the quantum resources matters immensely. While sharing entanglement between the two senders and the referee helps, sharing entanglement only between the two senders themselves does not provide the same benefit. The advantage comes specifically from the connection between the senders and the referee, which allows for a technique called superdense coding to be used effectively. Furthermore, the researchers show that adding more complex forms of entanglement, such as a shared state involving all three parties, offers no additional reduction in communication beyond what is already achieved by the simpler pairwise connections. The results extend beyond simple functions to more complex relationships where multiple answers might be valid, provided the relationship follows certain structural rules.

Ultimately, this work redefines our understanding of quantum communication limits. It suggests that the dramatic advantages seen in isolated, single-instance experiments are often artifacts of the specific constraints of that single test. When the pressure of scale is applied, the fundamental geometry of the information problem takes over, and the quantum and classical paths converge, except for a fixed factor of two when entanglement is shared. The study provides a precise mathematical map of this terrain, showing exactly where the limits lie and proving that the exponential gap between classical and quantum communication is not a permanent feature of the universe, but a temporary illusion that disappears under the weight of many tasks. For anyone interested in the future of secure communication or distributed computing, this offers a sobering but clear picture: quantum mechanics is powerful, but it is not a magic wand that can bypass the fundamental costs of information transfer when the scale is large.

Technical Summary: Exact Asymptotic Rates and an Exponential Strong Converse for Quantum SMP and One-Way Communication

1. Problem Statement

The paper investigates the communication complexity of computing $n$ independent instances of a finite total function $f: X \times Y \to Z$ (or a total relation $R$ ) simultaneously in the Simultaneous Message Passing (SMP) model. In this model, two senders (Alice and Bob) receive inputs $x$ and $y$ , respectively, and send messages to a referee who computes $f(x, y)$ . The senders cannot communicate with each other.

The central question is whether computing $n$ instances jointly allows for a reduction in the communication cost per instance compared to solving them individually, and how this asymptotic rate depends on:

Resources: Classical vs. quantum messages, shared randomness, and shared entanglement (bipartite between senders and referee, or arbitrary tripartite).
Error: Bounded error ( $\epsilon$ ) vs. zero error, and worst-case vs. expected communication costs.
Function Structure: Specifically, how the number of distinct rows and columns in the function's truth table dictates the rate.

The author aims to determine the exact asymptotic communication rate per instance as $n \to \infty$ and establish whether an "exponential strong converse" holds: i.e., if the communication rate falls below a specific threshold, does the probability of correctly computing all $n$ outputs decay exponentially?

2. Methodology

The proof strategy relies on reducing the SMP problem to a one-way communication problem and utilizing information-theoretic bounds based on quantum min-entropy.

2.1 Reduction to One-Way Communication

The author observes that if the total communication $q_A + q_B$ in an SMP protocol is below the optimal threshold, then at least one sender's message must be significantly shorter than the information required to describe their input's row or column structure.

If $q_A$ is small, Bob and the referee are grouped into a single receiver. Since the receiver knows Bob's input $y_n$ , they can simulate Bob's encoding and the referee's measurement. This transforms the SMP protocol into a one-way protocol from Alice to the receiver with the same success probability but only $q_A$ communication.
A symmetric argument applies if $q_B$ is small.

2.2 Min-Entropy and Sampling

The core of the lower bound proof involves showing that short messages leave high conditional min-entropy about the inputs.

Min-Entropy Bound: If Alice sends $q_A$ qubits, the conditional min-entropy $H_{\min}(X^n | Q)$ of her input given the message $Q$ is shown to be linear in $n$ if $q_A$ is below the threshold.
Sampling Theorem: Using a sampling theorem (adapted from [Wul11]), the author shows that if the min-entropy is high, a randomly selected substring of the input (encoded as a truth table) is hard to guess.
Decoding Contradiction: The author constructs a specific decoding strategy: by carefully choosing Bob's input $Y^n$ based on the sampled indices, the output of the one-way protocol can be used to recover the sampled bits. If the protocol succeeds with high probability, the receiver could guess the sampled bits with high probability, contradicting the min-entropy bound. This establishes that the success probability must decay exponentially if the rate is below the threshold.

2.3 Handling Resources

Entanglement: The analysis accounts for shared entanglement (BE: sender-referee; TE: tripartite). The presence of entanglement effectively doubles the capacity of the quantum channel (via superdense coding), halving the required communication rate. The proof shows that arbitrary tripartite entanglement (TE) offers no further advantage over independent sender-referee entanglement (BE).
Shared Randomness: The bounds are derived by fixing the shared randomness and averaging, showing the constants are uniform.
Variable Lengths: A technical lemma converts variable-length quantum protocols into fixed-length ones with only a negligible additive overhead, preserving the asymptotic rate.

3. Key Contributions and Results

3.1 The Asymptotic Rate Characterization

For any finite total function $f$ , the optimal worst-case communication rate per instance converges to:
$D_{\parallel}(f) = \log | \text{Row}(f) | + \log | \text{Col}(f) |$
where $\text{Row}(f)$ and $\text{Col}(f)$ are the sets of distinct rows and columns of the function table.

Classical and Quantum (No Entanglement): The rate is $D_{\parallel}(f)$ for both classical and quantum SMP, regardless of shared randomness or bounded error.
With Entanglement: If senders share entanglement with the referee (BE or TE), the rate is halved: $D_{\parallel}(f)/2$ .
Expected Communication: For expected communication with error $\epsilon$ , the rate is $(1-\epsilon)D_{\parallel}(f)$ (or $(1-\epsilon)D_{\parallel}(f)/2$ with entanglement). This is achieved by running a zero-error protocol with probability $1-\epsilon$ and sending nothing otherwise.

3.2 Exponential Strong Converse

The paper proves an exponential strong converse: for any fixed rate $R < R^*$ (where $R^*$ is the threshold defined above), the probability of computing all $n$ outputs correctly decays as $2^{-\Omega(n)}$ .

This holds for worst-case inputs and, more strongly, for average success probability under a fixed product input distribution.
This result implies that "savings" below the optimal rate are impossible; the transition from high success to exponential failure is sharp.

3.3 One-Way Communication

The results extend to one-way communication (Alice to Bob). The threshold becomes $D_{\rightarrow}(f) = \log | \text{Row}(f) |$ . The column term vanishes because Bob already possesses his input.

3.4 Specific Implications

Equality Function ( $EQ_m$ ): For a single instance, quantum fingerprinting achieves $O(\log m)$ qubits without shared randomness, while classical public-coin SMP achieves $O(1)$ bits. However, for $n$ instances, the asymptotic rate for quantum SMP without entanglement is $2m$ bits/qubits, and with entanglement is $m$ bits/qubits. The exponential quantum advantage for a single instance disappears in the asymptotic rate.
Relations: The results extend to a class of total relations satisfying specific conditions (C.I and C.II) that allow mapping relation outputs to an underlying function $g$ .

4. Significance and Claims

The paper claims to provide the first exact characterizations of both worst-case and expected asymptotic communication rates for all total functions in the SMP model, covering classical, quantum, and entanglement-assisted scenarios.

Resolution of Direct Sum Questions: Unlike previous direct sum theorems that only established linear growth ( $\Omega(n C_0)$ ) without identifying the exact coefficient, this work identifies the exact coefficient $D_{\parallel}(f)$ .
Strong Converse: It establishes an exponential strong converse at the exact optimal rate, a stronger result than typical strong direct product theorems which often apply only below a rate $c \cdot C_0$ where $c < 1$ .
Quantum Advantage: The work demonstrates that while quantum resources (fingerprinting) offer significant advantages for single instances, they do not improve the asymptotic communication rate per instance for total functions beyond a factor of 2 (achieved via superdense coding with entanglement).
Generality: The characterization applies to a broad class of relations, including those arising in linear games, provided they satisfy the structural conditions allowing reduction to an underlying function.

The author notes that the results do not apply to relations like the magic-square relation, which fall outside the defined conditions, and they leave open the question of extending these exact rates to interactive (two-way) communication models.