Abstract
Understanding how quantum algorithms are more powerful than their classical counterparts is one of the central challenges of quantum computing. While current theoretical computer science lacks tools to definitively differentiate quantum and classical complexity classes, valuable insights into algorithmic differences can be gleaned by establishing unconditional separations within various concrete models such as query and communication complexity. Such concrete models also serve as a foundation for proving separations between quantum and classical complexity classes relative to oracles.
In this talk, I will look at quantum-classical separations through the lens of the k-fold Forrelation problem introduced by Aaronson and Ambainis. This problem has led to several interesting quantum-classical separations in recent years, such as an oracle separation of BQP and PH, optimal separations between quantum and classical query algorithms and communication protocols, and oracle separation of one-way functions from quantum cryptographic primitives, among others.
Two valuable insights have proven instrumental in these separations: the l1-Fourier growth, an analytic proxy for the sparsity of the polynomials computed by a given computational model, and the tool of pathwise analysis or semigroup interpolation, which enables an analysis of complex correlated distributions on the hypercube. These insights are also of broader significance beyond quantum-classical separations as they have connections to pseudorandomness, statistical physics, and several other areas.
In this talk, I intend to provide a gentle overview of these ideas. This talk will partly be based on a joint work with Nikhil Bansal but I will also touch upon relevant contributions from other researchers.