Trade-offs between Entanglement and Communication

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/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/qic/Gavinsky08}.