💻 computer science

Exact Zero-Error Communication Complexity of an Entanglement-Assisted Quantum Learning Task

This paper resolves the open question of the exact zero-error one-way classical communication cost for a specific entanglement-assisted quantum learning task by proving it equals the logarithm of the ternary-cube covering number (or the total domination number of the categorical power $K_3^{\times n}$ ), thereby quantifying the precise classical resources required to match the quantum protocol's perfect success.

Original author: David Vesterlund

Published 2026-11-06

📖 5 min read🧠 Deep dive

CC BY 4.0

Original author: David Vesterlund

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

In the world of distributed computing, where different machines must work together to solve a problem, communication is often the most expensive resource. Imagine two people trying to coordinate a complex task without being able to speak to each other; they must rely on pre-agreed strategies or shared information to succeed. In recent years, scientists have discovered that if these two people share a special kind of quantum connection known as entanglement, they can sometimes perform tasks with perfect accuracy without sending a single message. This phenomenon, where quantum partners seem to know what the other is doing without communication, has long been a subject of intense study. However, a fundamental question remained unanswered: if we strip away the quantum magic and force the partners to use only standard, classical communication, exactly how much information must they exchange to match the perfect success of their quantum counterparts?

A new study by David Vesterlund addresses this precise question for a specific learning task recently proposed by Zhao and Deng. In that original task, a quantum protocol using a large number of pre-shared entangled pairs could achieve perfect success with zero classical communication. The classical alternative, however, was known to require a significant amount of data exchange, but the exact minimum amount needed to guarantee a perfect win was unknown. Vesterlund's work provides a definitive answer, revealing that the amount of classical communication required is not simply a linear sum of the parts, but follows a more complex, compressed pattern. By translating the problem into a geometric puzzle involving covering a multi-dimensional space with smaller blocks, the author calculated the exact number of bits needed to ensure a flawless outcome.

The researchers focused on a scenario where two parties, Alice and Bob, receive inputs and must produce outputs that satisfy a specific winning condition. In the quantum version of this game, they share entangled particles, which allows them to coordinate their answers perfectly without talking. In the classical version, they must send messages. The study proves that to achieve the same perfect success rate as the quantum version, the classical parties do not need to send one bit of information for every single sub-task they perform. Instead, they can compress the information. The paper establishes that the minimum number of bits required is determined by a mathematical property related to how efficiently one can cover a three-dimensional grid with smaller, two-dimensional slices.

Through a rigorous reduction of the problem, the study demonstrates that the communication cost grows much slower than the number of tasks increases. For a single task, the classical parties need a certain amount of information, but when they perform many tasks simultaneously, they can encode the necessary data more efficiently. The research shows that for large numbers of tasks, the classical communication required is approximately 0.585 bits per task. This means that by working together on a batch of problems, the classical partners can reduce their communication needs to less than 60 percent of what a standard, task-by-task approach would require. This finding highlights a property of classical information known as non-additivity, where the whole is cheaper than the sum of its parts, a feature that exists independently of the quantum advantage.

The study also clarifies the relationship between the quantum and classical resources. While the quantum protocol achieves perfect success with zero communication by using a specific amount of pre-shared entanglement, the classical protocol achieves the same result by using a small but non-zero amount of communication. The paper explicitly rules out the idea that shared randomness—where both parties have access to the same random numbers—can reduce this communication cost further. It proves that even with shared randomness, the classical parties cannot do better than the deterministic protocol derived from the geometric covering solution. The work confirms that the quantum advantage in this specific setting is a trade-off between communication and entanglement, where the quantum side pays with shared particles and the classical side pays with a compressed stream of bits.

The results are presented with exact precision for small numbers of tasks and a clear asymptotic rate for large numbers. The author used computational methods to verify the exact values for up to eight simultaneous tasks, confirming that the communication cost is indeed lower than the number of tasks starting from the fourth task onward. For larger scales, the study relies on recent mathematical proofs regarding the covering of ternary cubes to establish the long-term behavior. The final conclusion is that the classical cost is not linear but follows a logarithmic growth pattern, settling at a rate of roughly 0.585 bits per task. This provides a complete picture of the communication landscape for this learning task, showing exactly where the classical limit lies and how it compares to the quantum capability.

This work does not claim that classical computers are superior to quantum ones, nor does it suggest that the quantum advantage disappears. Rather, it precisely maps the boundary of what is possible without quantum resources. It shows that while quantum entanglement allows for a zero-communication solution, the classical world is not as inefficient as one might assume; it possesses its own mechanisms for compression that allow it to approach the quantum performance with a surprisingly small amount of data. The study closes a gap in our understanding of distributed learning, moving from a general observation of separation to an exact calculation of the cost, offering a clear and quantified view of the resources required to bridge the gap between classical and quantum coordination.

Technical Summary: Exact Zero-Error Communication Complexity of an Entanglement-Assisted Quantum Learning Task

Problem Statement
This work addresses the exact zero-error one-way classical communication complexity required to simulate a specific entanglement-assisted quantum learning task introduced by Zhao and Deng. In the Zhao–Deng task, a quantum protocol utilizing $2n$ preshared Bell pairs achieves perfect success with zero input-dependent classical communication. While Zhao and Deng established a constant-versus-linear separation against common classical models (requiring linear scaling for nontrivial accuracy), the precise minimum number of classical bits ( $B^*(n, 1)$ ) required for a deterministic one-way classical protocol to achieve perfect (zero-error) success remained unknown. The paper investigates three specific questions: the exact cost, the additivity of communication under parallel repetition, and the asymptotic communication rate.

Methodology
The author employs a reductionist approach, mapping the communication problem to a combinatorial covering problem on a ternary hypercube.

Task Definition: The task involves $n$ parallel copies of a single-copy game derived from the Mermin–Peres magic-square construction. Alice and Bob receive inputs from $\{00, 01, 10, 11\}^n$ . A "hard" input is defined as one where the index $I(x) \in \{1, 2, 3\}$ (excluding $00$). The winning condition requires specific alignment of "virtual outputs" based on the inputs.
Compatibility Analysis: The core of the proof involves defining "compatibility" for sets of hard inputs. A set of inputs is compatible if there exist deterministic functions for Alice and Bob that win the game for all inputs in the set against any possible opponent input.
- Single-Copy Lemma: A subset of hard inputs $\{01, 10, 11\}$ is compatible if and only if its size is at most 2. The full set of three is incompatible due to a contradiction in the required virtual output matrix (specifically, the asymmetry in the third component leads to $0=1$ ).
- Factorization Lemma: For the $n$ -fold parallel task, a set of inputs is compatible if and only if its projection onto every coordinate $i$ is single-copy compatible.
Reduction to Covering: The author proves that a maximal compatible set of inputs corresponds to a "binary subcube" of the ternary space $\mathbb{Z}_3^n$ $Z_{3}^{n}$ (where each coordinate takes values from a subset of size 2). Consequently, a perfect classical protocol with $B$ $B$ bits corresponds to a partition of the hard input space into at most $2^B$ $2^{B}$ compatible sets.
- This reduces the problem to finding the minimum number of binary subcubes required to cover $\mathbb{Z}_3^n$ .
- This covering number, denoted $f(n, 3)$ , is shown to be equivalent to the total domination number $\gamma_t(K_3^{\times n})$ of the categorical power of the complete graph $K_3$ .
Extension to Full Task: The author demonstrates that solving the problem for the restricted "all-hard" input space is equivalent to solving it for the full input space (including easy inputs like $00$), as easy inputs auto-win and can be mapped to hard inputs without increasing communication cost.

Key Contributions and Results

Exact Reduction (Theorem 1): The paper establishes the exact formula for the minimum one-way classical communication cost:
$B^*(n, 1) = \lceil \log_2 f(n, 3) \rceil = \lceil \log_2 \gamma_t(K_3^{\times n}) \rceil$
where $f(n, 3)$ is the minimum number of binary subcubes covering $\mathbb{Z}_3^n$ .
Finite-Size Values: Using Integer Linear Programming (ILP) and literature values (Adriaensen et al., Kuang and Wang), the author provides exact values for $B^*(n, 1)$ for $n=1$ to $8$.
- For $n=1$ , $B^*=1$ .
- For $n=2$ , $B^*=2$ (equal to $n$ ).
- For $n=3$ , $B^*=3$ (equal to $n$ ).
- For $n=4$ , $B^*=3$ (strictly less than $n$ ).
- The values falsify the conjecture that $B^*(n, 1) = n$ starting from $n=4$ , where the cost drops below the linear scaling.
Non-Additivity (Corollary 1): The communication cost is strictly non-additive for $n \ge 4$ . Specifically, $B^*(n, 1) < n$ . This indicates that joint encoding of parallel subtasks allows for classical communication compression.
Asymptotic Rate (Corollary 2): By combining the exact reduction with the 2026 asymptotic covering result of Kuang and Wang ( $f(n) \sim (C_3 + o(1))(3/2)^n$ ), the paper derives the exact first-order asymptotic communication rate:
$B^*(n, 1) = n \log_2(3/2) + O(1)$
$\lim_{n \to \infty} \frac{B^*(n, 1)}{n} = \log_2(3/2) \approx 0.585$
This implies that asymptotically, parallel encoding requires only ~58.5% of one bit per subtask.
Shared Randomness (Corollary 3): The paper proves that shared randomness does not reduce the zero-error communication cost; $B^*_{shared}(n, 1) = B^*_{deterministic}(n, 1)$ .

Significance and Claims
The paper claims to resolve the specific open question of the exact zero-error communication cost for the Zhao–Deng learning task, a quantity not determined in the original work.

Resource Separation: The work highlights a communication–entanglement resource separation. The quantum protocol achieves perfect success with zero input-dependent communication using $2n$ Bell pairs. The classical protocol requires $\Theta(n)$ bits, specifically growing as $n \log_2(3/2)$ .
Classical Nature of Compression: The author emphasizes that the observed communication compression (the factor of $\log_2(3/2)$ ) is a classical property of the parallel task structure (governed by the covering number of the ternary cube) and not a quantum effect. It arises from the ability to jointly encode subtasks.
Scope Limitations: The author explicitly states they do not claim a universal computational advantage or a sharpening of Zhao and Deng's main machine learning theorems. The result is restricted to deterministic (and shared-randomness) one-way communication with perfect success ( $q=1$ ). Extensions to imperfect success or interactive communication are left for future work.

In summary, the paper translates a quantum learning communication problem into a graph-theoretic total domination problem, providing an exact formula and asymptotic rate that quantify the classical communication overhead required to match a specific entanglement-assisted quantum protocol.

Technical Summary: Exact Zero-Error Communication Complexity of an Entanglement-Assisted Quantum Learning Task

More like this