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.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/0610085Oct 11, 20060 citations

Multi-Party Quantum Communication Complexity with Prior Entanglements

Takashi Mihara

IEICE Transactions on Information and SystemsNov 1, 20010 citations

Quantum Entanglement and the Communication Complexity of the Inner Product Function

Richard Cleve, Wim van Dam, Michael A. Nielsen +1 more

Lecture notes in computer scienceJan 1, 1999133 citations

Maximum Separation of Quantum Communication Complexity With and Without Shared Entanglement

Atsuya Hasegawa, François Le Gall, Augusto Modanese

We present relation problems whose input size is $n$ such that they can be solved with no communication for entanglement-assisted quantum communication models, but require $Ω(n)$ qubit communication for $2$ -way quantum communication models without prior shared entanglement. This is the maximum separation of quantum communication complexity with and without shared entanglement. To our knowledge, our result even shows the first lower bound on quantum communication complexity without shared entanglement when the upper bound of entanglement-assisted quantum communication models is zero. Our result refutes a quantum analog of Newman's theorem. The problem we consider is parallel repetition of any non-local game which has a perfect quantum strategy and no perfect classical strategy, and for which a parallel repetition theorem holds with exponential decay.We present relation problems whose input size is $n$ such that they can be solved with no communication for entanglement-assisted quantum communication models, but require $Ω(n)$ qubit communication for $2$-way quantum communication models without prior shared entanglement. This is the maximum separation of quantum communication complexity with and without shared entanglement. To our knowledge, our result even shows the first lower bound on quantum communication complexity without shared entanglement when the upper bound of entanglement-assisted quantum communication models is zero. Our result refutes a quantum analog of Newman's theorem. The problem we consider is parallel repetition of any non-local game which has a perfect quantum strategy and no perfect classical strategy, and for which a parallel repetition theorem holds with exponential decay.

arXiv:2505.16457May 22, 20250 citations

Bounds on Oblivious Multiparty Quantum Communication Complexity

François Le Gall, Daiki Suruga

arXiv:2210.15402Lecture notes in computer scienceJan 1, 20224 citations

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.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.07699Leibniz international proceedings in informaticsJan 1, 20191 citation

We present relation problems whose input size is

n

such that they can be solved with no communication for entanglement-assisted quantum communication models, but require

Ω(n)

qubit communication for

2

-way quantum communication models without prior shared entanglement. This is the maximum separation of quantum communication complexity with and without shared entanglement. To our knowledge, our result even shows the first lower bound on quantum communication complexity without shared entanglement when the upper bound of entanglement-assisted quantum communication models is zero. Our result refutes a quantum analog of Newman's theorem. The problem we consider is parallel repetition of any non-local game which has a perfect quantum strategy and no perfect classical strategy, and for which a parallel repetition theorem holds with exponential decay.

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.