Quantum versus Randomized Communication Complexity, with Efficient Players
summary
Shows a concrete partial function (a XOR lift of Aaronson’s Fourrelation) that has an efficient small-cost quantum simultaneous protocol with a few EPR pairs and polylog-size quantum circuits with oracle access, but no classical randomized protocol of small cost: any deterministic protocol of cost C has distinguishing advantage ≤ C^2 / √n, so C must be ≳ n^{1/4} to succeed. Proof combines the Raz–Tal Fourrelation distribution, convolution/rectangle reductions, and a level‑2 Fourier bound via hypercontractivity and results of Chattopadhyay et al.
AI-written summary · about
chapters (5)
- 0:00Start
- 0:11Communication Complexity
- 4:45State-of-the-art result
- 12:06Randomized Lower Bound
- 19:54Open Questions
related talks
32mCan We Get Verifiable Quantum Advantage from Forrelation
01h 06mQuantum Advantage Without Structure
59mQuantum cryptography and quantum complexity
01h 10mQuantum Advantage with Shallow Clifford Circuits
45mClassical Verification of Quantum Computational Advantage
29mParallel Repetition for Entangled Games via Fast Quantum Search
16mAsynchronous Multi-Party Quantum Computation
23mMore privacy, better social welfare: using quantum resources for daily problems