One Clean Qubit Suffices for Quantum Communication Advantage

Explore groundbreaking research presented at the 19th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2024) that demonstrates how a single clean qubit can achieve quantum communication advantage. Delve into a mathematical proof showing that a quantum protocol with one clean qubit and maximally mixed qubits can solve a partial function with O(log N) cost, while classical interactive randomized protocols require Ω(sqrt{N}) cost. Learn how this breakthrough settles a longstanding conjecture by Klauck and Lim, surpassing previous quantum-classical separations that needed Ω(log N) clean qubits. Understand the innovative proof methodology combining hypercontractivity inequality with representation theory of compact Lie groups, and discover how this function achieves similar efficiency in the quantum-simultaneous-with-entanglement model, matching current quantum communication complexity benchmarks.