Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > DQC1:
Reports tagged with DQC1:
TR23-148 | 3rd October 2023
Srinivasan Arunachalam, Uma Girish, Noam Lifshitz

One Clean Qubit Suffices for Quantum Communication Advantage

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 ... more >>>




ISSN 1433-8092 | Imprint