Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

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

David Vesterlund

Published Nov 6, 2026• 0 citations
PDF (CC BY)Publisher

Abstract

Abstract Zhao and Deng introduced an entanglement-assisted learning task exhibiting a constant-versus-linear separation against communication-bounded classical models: a quantum protocol with \(\:2n\) preshared Bell pairs achieves perfect success with zero input-dependent classical communication, while commonly used classical models must scale linearly to achieve nontrivial accuracy. The exact zero-error one-way classical communication cost was unknown. We prove an exact reduction: the minimum one-way classical communication for perfect success equals the logarithm of the ternary-cube covering number, equivalently the total domination number of the categorical power \(\:{K}_{3}^{\times\:n}\):

DOI
10.21203/rs.3.rs-11229222/v1

Related papers

Exponential Separation of Quantum and Classical One-Way Communication Complexity

Ziv Bar-Yossef, T. S. Jayram, Iordanis Kerenidis

We give the first exponential separation between quantum and bounded-error randomized one-way communication complexity. Specifically, we define the Hidden Matching Problem HM$_n$: Alice gets as input a string ${\bf x}\in\{0, 1\}^n$, and Bob gets a perfect matching M on the n coordinates. Bob's goal is to output a tuple $\langle i,j,b \rangle$ such that the edge $(i,j)$ belongs to the matching M and $b=x_i\oplus x_j$. We prove that the quantum one-way communication complexity of HM$_n$ is $O(\log n)$, yet any randomized one-way protocol with bounded error must use $\Omega({\sqrt{n}})$ bits of communication. No asymptotic gap for one-way communication was previously known. Our bounds also hold in the model of Simultaneous Messages (SM), and hence we provide the first exponential separation between quantum SM and randomized SM with public coins. For a Boolean decision version of HM$_n$, we show that the quantum one-way communication complexity remains $O(\log n)$ and that the 0-error randomized one-way communication complexity is $\Omega(n)$. We prove that any randomized linear one-way protocol with bounded error for this problem requires $\Omega(\sqrt[3]{n \log n})$ bits of communication.

SIAM Journal on Computing•Jan 1, 2008•57 citations

Multiparty Zero-Error Classical Channel Coding With Entanglement

Teresa Piovesan, Giannicola Scarpa, Christian Schaffner

We study the effects of quantum entanglement on the performance of two classical zero-error communication tasks among multiple parties. Both tasks are generalizations of the two-party zero-error channel-coding problem, where a sender and a receiver want to perfectly communicate messages through a one-way classical noisy channel. If the two parties are allowed to share entanglement, there are several positive results that show the existence of channels for which they can communicate strictly more than what they could do with classical resources. In the first task, one sender wants to communicate a common message to multiple receivers. We show that if the number of receivers is greater than a certain threshold then entanglement does not allow for an improvement in the communication for any finite number of uses of the channel. On the other hand, when the number of receivers is fixed, we exhibit a class of channels for which entanglement gives an advantage. The second problem we consider features multiple collaborating senders and one receiver. Classically, cooperation among the senders might allow them to communicate on average more messages than the sum of their individual possibilities. We show that whenever a channel allows single-sender entanglement-assisted advantage, then the gain extends also to the multisender case. Furthermore, we show that entanglement allows for a peculiar amplification of information which cannot happen classically, for a fixed number of uses of the channels.

arXiv:1403.5003•IEEE Transactions on Information Theory•Dec 10, 2014•4 citations

Exponential separation of quantum and classical one-way communication complexity

Ziv Bar-Yossef, T. S. Jayram, Iordanis Kerenidis

We give the first exponential separation between quantum and bounded-error randomized one-way communication complexity. Specifically, we define the Hidden Matching Problem HMn: Alice gets as input a string x ∈ (0, 1)n and Bob gets a perfect matching M on the n coordinates. Bob's goal is to output a tuple [i,j,b] such that the edge (i,j) belongs to the matching M and b = xi ⊕ xj. We prove that the quantum one-way communication complexity of HMn is O(log n), yet any randomized one-way protocol with bounded error must use Ω(√n) bits of communication. No asymptotic gap for one-way communication was previously known. Our bounds also hold in the model of Simultaneous Messages (SM) and hence we provide the first exponential separation between quantum SM and randomized SM with public coins.For a Boolean decision version of HMn, we show that the quantum one-way communication complexity remains O(log n) and that the 0-error randomized one-way communication complexity is Ω(n). We prove that any randomized linear one-way protocol with bounded error for this problem requires Ω(√[3] n log n) bits of communication.

ACM Symposium on Theory of Computing (STOC)•Jun 13, 2004•111 citations

A lower bound on entanglement-assisted quantum communication complexity

Ashley Montanaro, Andreas Winter

We prove a general lower bound on the bounded-error entanglement-assisted quantum communication complexity of Boolean functions. The bound is based on the concept that any classical or quantum protocol to evaluate a function on distributed inputs can be turned into a quantum communication protocol. As an application of this bound, we give a very simple proof of the statement that almost all Boolean functions on n+n bits have linear communication complexity, even in the presence of unlimited entanglement.

arXiv:quant-ph/0610085•Oct 11, 2006•1 citation

Universality of EPR Pairs in Entanglement-Assisted Communication Complexity, and the Communication Cost of State Conversion

Matthew Coudron, Aram W. Harrow

Entanglement assistance is known to reduce the quantum communication complexity of evaluating functions with distributed inputs. But does the type of entanglement matter, or are EPR pairs always sufficient? This is a natural question because in several other settings maximally entangled states are known to be less useful as a resource than some partially entangled state. These include non-local games, tasks with quantum communication between players and referee, and simulating bipartite unitaries or communication channels. By contrast, we prove that the bounded-error entanglement-assisted quantum communication complexity of a function cannot be improved by more than a constant factor by replacing maximally entangled states with arbitrary entangled states. In particular, we show that every quantum communication protocol using $Q$ qubits of communication and arbitrary shared entanglement can be $ε$-approximated by a protocol using $O(Q/ε+\log(1/ε)/ε)$ qubits of communication and only EPR pairs as shared entanglement. Our second result concerns an old question in quantum information theory: How much quantum communication is required to approximately convert one pure bipartite entangled state into another? We show that the communication cost of converting between two bipartite quantum states is upper bounded, up to a constant multiplicative factor, by a natural and efficiently computable quantity which we call the $\ell_{\infty}$-Earth Mover's Distance (EMD) between those two states. Furthermore, we prove a complementary lower bound on the cost of state conversion by the $ε$-smoothed $\ell_{\infty}$-EMD, which is a natural smoothing of the $\ell_{\infty}$-EMD that we will define via a connection with optimal transport theory.

arXiv:1902.07699•Leibniz international proceedings in informatics•Jan 1, 2019•2 citations

On communication over an entanglement-assisted quantum channel

Ashwin Nayak, Julia Salzman

Shared entanglement is a resource available to parties communicating over a quantum channel, much akin to public coins in classical communication protocols. Whereas shared randomness does not help in the transmission of information, or significantly reduce the classical complexity of computing functions (as compared to private-coin protocols), shared entanglement leads to startling phenomena such as "quantum teleportation" and "superdense coding."The problem of characterising the power of prior entanglement has puzzled many researchers. In this paper, we revisit the problem of transmitting classical bits over an entanglement-assisted quantum channel. We derive a new, optimal bound on the number of quantum bits required for this task, for any given probability of error. All known lower bounds in the setting of bounded error entanglement-assisted communication are based on sophisticated information theoretic arguments. In contrast, our result is derived from first principles, using a simple linear algebraic technique.

ACM Symposium on Theory of Computing (STOC)•Jan 1, 2002•28 citations
Abstract Zhao and Deng introduced an entanglement-assisted learning task exhibiting a constant-versus-linear separation against communication-bounded classical models: a quantum protocol with (:2n) preshared Bell pairs achieves perfect success with zero input-dependent classical communication, while commonly used classical models must scale linearly to achieve nontrivial accuracy. The exact zero-error one-way classical communication cost was unknown. We prove an exact reduction: the minimum one-way classical communication for perfect success equals the logarithm of the ternary-cube covering number, equivalently the total domination number of the categorical power (:{K}_{3}^{\times:n}):
We give the first exponential separation between quantum and bounded-error randomized one-way communication complexity. Specifically, we define the Hidden Matching Problem HMn_nn​: Alice gets as input a string x∈{0,1}n{\bf x}\in\{0, 1\}^nx∈{0,1}n, and Bob gets a perfect matching M on the n coordinates. Bob's goal is to output a tuple ⟨i,j,b⟩\langle i,j,b \rangle⟨i,j,b⟩ such that the edge (i,j)(i,j)(i,j) belongs to the matching M and b=xi⊕xjb=x_i\oplus x_jb=xi​⊕xj​. We prove that the quantum one-way communication complexity of HMn_nn​ is O(log⁡n)O(\log n)O(logn), yet any randomized one-way protocol with bounded error must use Ω(n)\Omega({\sqrt{n}})Ω(n​) bits of communication. No asymptotic gap for one-way communication was previously known. Our bounds also hold in the model of Simultaneous Messages (SM), and hence we provide the first exponential separation between quantum SM and randomized SM with public coins. For a Boolean decision version of HMn_nn​, we show that the quantum one-way communication complexity remains O(log⁡n)O(\log n)O(logn) and that the 0-error randomized one-way communication complexity is Ω(n)\Omega(n)Ω(n). We prove that any randomized linear one-way protocol with bounded error for this problem requires Ω(nlog⁡n3)\Omega(\sqrt[3]{n \log n})Ω(3nlogn​) bits of communication.
We study the effects of quantum entanglement on the performance of two classical zero-error communication tasks among multiple parties. Both tasks are generalizations of the two-party zero-error channel-coding problem, where a sender and a receiver want to perfectly communicate messages through a one-way classical noisy channel. If the two parties are allowed to share entanglement, there are several positive results that show the existence of channels for which they can communicate strictly more than what they could do with classical resources. In the first task, one sender wants to communicate a common message to multiple receivers. We show that if the number of receivers is greater than a certain threshold then entanglement does not allow for an improvement in the communication for any finite number of uses of the channel. On the other hand, when the number of receivers is fixed, we exhibit a class of channels for which entanglement gives an advantage. The second problem we consider features multiple collaborating senders and one receiver. Classically, cooperation among the senders might allow them to communicate on average more messages than the sum of their individual possibilities. We show that whenever a channel allows single-sender entanglement-assisted advantage, then the gain extends also to the multisender case. Furthermore, we show that entanglement allows for a peculiar amplification of information which cannot happen classically, for a fixed number of uses of the channels.
We give the first exponential separation between quantum and bounded-error randomized one-way communication complexity. Specifically, we define the Hidden Matching Problem HMn: Alice gets as input a string x ∈ (0, 1)n and Bob gets a perfect matching M on the n coordinates. Bob's goal is to output a tuple [i,j,b] such that the edge (i,j) belongs to the matching M and b = xi ⊕ xj. We prove that the quantum one-way communication complexity of HMn is O(log n), yet any randomized one-way protocol with bounded error must use Ω(√n) bits of communication. No asymptotic gap for one-way communication was previously known. Our bounds also hold in the model of Simultaneous Messages (SM) and hence we provide the first exponential separation between quantum SM and randomized SM with public coins.For a Boolean decision version of HMn, we show that the quantum one-way communication complexity remains O(log n) and that the 0-error randomized one-way communication complexity is Ω(n). We prove that any randomized linear one-way protocol with bounded error for this problem requires Ω(√[3] n log n) bits of communication.
We prove a general lower bound on the bounded-error entanglement-assisted quantum communication complexity of Boolean functions. The bound is based on the concept that any classical or quantum protocol to evaluate a function on distributed inputs can be turned into a quantum communication protocol. As an application of this bound, we give a very simple proof of the statement that almost all Boolean functions on n+n bits have linear communication complexity, even in the presence of unlimited entanglement.
Entanglement assistance is known to reduce the quantum communication complexity of evaluating functions with distributed inputs. But does the type of entanglement matter, or are EPR pairs always sufficient? This is a natural question because in several other settings maximally entangled states are known to be less useful as a resource than some partially entangled state. These include non-local games, tasks with quantum communication between players and referee, and simulating bipartite unitaries or communication channels. By contrast, we prove that the bounded-error entanglement-assisted quantum communication complexity of a function cannot be improved by more than a constant factor by replacing maximally entangled states with arbitrary entangled states. In particular, we show that every quantum communication protocol using QQQ qubits of communication and arbitrary shared entanglement can be εεε-approximated by a protocol using O(Q/ε+log⁡(1/ε)/ε)O(Q/ε+\log(1/ε)/ε)O(Q/ε+log(1/ε)/ε) qubits of communication and only EPR pairs as shared entanglement. Our second result concerns an old question in quantum information theory: How much quantum communication is required to approximately convert one pure bipartite entangled state into another? We show that the communication cost of converting between two bipartite quantum states is upper bounded, up to a constant multiplicative factor, by a natural and efficiently computable quantity which we call the ℓ∞\ell_{\infty}ℓ∞​-Earth Mover's Distance (EMD) between those two states. Furthermore, we prove a complementary lower bound on the cost of state conversion by the εεε-smoothed ℓ∞\ell_{\infty}ℓ∞​-EMD, which is a natural smoothing of the ℓ∞\ell_{\infty}ℓ∞​-EMD that we will define via a connection with optimal transport theory.
Shared entanglement is a resource available to parties communicating over a quantum channel, much akin to public coins in classical communication protocols. Whereas shared randomness does not help in the transmission of information, or significantly reduce the classical complexity of computing functions (as compared to private-coin protocols), shared entanglement leads to startling phenomena such as "quantum teleportation" and "superdense coding."The problem of characterising the power of prior entanglement has puzzled many researchers. In this paper, we revisit the problem of transmitting classical bits over an entanglement-assisted quantum channel. We derive a new, optimal bound on the number of quantum bits required for this task, for any given probability of error. All known lower bounds in the setting of bounded error entanglement-assisted communication are based on sophisticated information theoretic arguments. In contrast, our result is derived from first principles, using a simple linear algebraic technique.