Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR23-148 | 3rd October 2023 22:36

One Clean Qubit Suffices for Quantum Communication Advantage


Authors: Srinivasan Arunachalam, Uma Girish, Noam Lifshitz
Publication: 3rd October 2023 23:10
Downloads: 188


We study the one-clean-qubit model of quantum communication where one qubit is in a pure state and all other qubits are maximally mixed. We demonstrate a partial function that has a quantum protocol of cost $O(\log N)$ in this model, however, every interactive randomized protocol has cost $\Omega(\sqrt{N})$, settling a conjecture of Klauck and Lim. In contrast, all prior quantum versus classical communication separations required at least $\Omega(\log N)$ clean qubits. The function demonstrating our separation also has an efficient protocol in the quantum-simultaneous-with-entanglement model of cost $O(\log N )$. We thus recover the state-of-the-art separations between quantum and classical communication complexity. Our proof is based on a recent hypercontractivity inequality introduced by Ellis, Kindler, Lifshitz, and Minzer, in conjunction with tools from the representation theory of compact Lie groups.

ISSN 1433-8092 | Imprint