Demonstrating an unconditional separation between quantum and classical information resources
October 22, 2025 (GHC 8102)
Abstract: I’ll describe a recent demonstration of unconditional quantum advantage based on quantum–classical separations in one-way communication. We construct a task for which the most space-efficient classical algorithm provably requires between 62 and 382 bits of memory, yet we solve it using only 12 qubits on a trapped-ion quantum processor.
Based on arXiv:2509.07255. Joint work with William Kretschmer, Matthew DeCross, Justin A. Gerber, Kevin Gilmore, Dan Gresh, Nicholas Hunter-Jones, Karl Mayer, Brian Neyenhuis, David Hayes, and Scott Aaronson.