Trade-offs between Entanglement and Communication

Abstract

The problem of how much entanglement quantum protocols need is a notoriously hard open problem in communication complexity. We study a variant of this problem, namely: for a quantum protocol, can we reduce the entanglement from $$\Theta(k \log n)$$ to $$O(k)$$ using a \emph{classical} communication protocol with polynomially larger cost? We provide a strong negative answer. We give explicit partial functions on $$n$$ bits for which reducing the entanglement increases the classical communication complexity exponentially. Our separations are as follows. For every~$$k\geq~1$$: \paragraph*{$$\Qent$$ versus $$\Rtwoent$$:} We show that quantum simultaneous protocols with $$\tilde{\Theta}(k^5\log^{3} n)$$ EPR pairs can exponentially outperform two-way randomized protocols with $$O(k)$$ qubits of entanglement. This resolves an open problem from~\cite{DBLP:journals/qic/Gavinsky08} and improves the state-of-the-art separations between quantum simultaneous protocols with entanglement and two-way randomized protocols without entanglement~\cite{gavinsky2019quantum,girish2022quantum}. \paragraph*{$$\Rent$$ versus $$\Qent$$:} We also show that classical simultaneous protocols with $$\tilde{\Theta}(k\log n)$$ EPR pairs can exponentially outperform quantum simultaneous protocols with $$O(k)$$ qubits of entanglement, resolving an open question from~\cite{gavinsky2006bounded,gavinsky2019quantum}. The best result prior to our work was a relational separation against protocols without entanglement~\cite{gavinsky2006bounded}. \paragraph*{$$\Rent$$ versus $$\Roneent$$:} We show that classical simultaneous protocols with $$\tilde{\Theta}(k\log n)$$ EPR pairs can exponentially outperform randomized one-way protocols with $$O(k)$$ qubits of entanglement. Prior to our work, only a relational separation was known~\cite{DBLP:journals/qic/Gavinsky08}.