William Kretschmer (University of Texas at Austin), QISE Seminar: Demonstrating an unconditional separation between quantum and classical information resources

Abstract:

A longstanding question in the foundations of quantum mechanics is whether the exponential state space of a quantum system is a physically accessible resource, or whether the observed behavior of quantum devices admits a succinct classical explanation. In this talk I will discuss an experimental work in which, leveraging quantum-classical separations in communication complexity, we performed a task using 12 trapped-ion qubits that would provably require at least 62 bits of storage to replicate using classical information resources. Consequently, no classical ontological model of fewer than 62 bits can explain the observed behavior of the 12-qubit system. Our separation does not rely on any unproven conjectures, and demonstrates how today’s quantum processors can generate and manipulate entangled states of sufficient complexity to access the exponentiality of Hilbert space. Based on arXiv:2509.07255.

Speaker Bio:

William Kretschmer is an Assistant Professor in the Department of Computer Science at UT Austin. Previously, was a Quantum Postdoctoral Fellow at the Simons Institute for the Theory of Computing. His research lies broadly in quantum information and computation, with connections to complexity theory, cryptography, and learning. Kretschmer is especially interested in understanding computational problems that involve operation on quantum inputs.