Towards Optimal Separations between Quantum and Randomized Query Complexities

(Click “Event Website” above to access the zoom link.)

Abstract: The query model offers a concrete setting where quantum algorithms are provably superior to randomized algorithms. Beautiful results by Bernstein-Vazirani, Simon, Aaronson, and others presented partial Boolean functions that can be computed by quantum algorithms making much fewer queries compared to their randomized analogs. Till recently, separations of $O(1)$ vs. $\sqrt{N}$ between quantum and randomized query complexities remained the state-of-the-art (where N is the input length), leaving open the question of whether $O(1)$ vs. $N^{1/2+\Omega(1)}$ separations are possible?

We answer this question in the affirmative. Our separating problem is a variant of the Aaronson-Ambainis k-fold Forrelation problem. For any constant $\epsilon>0$, we give a $O(1)$ vs. $\Omega(N^{2/3-\epsilon})$ separation between the quantum and randomized query complexities of the k-fold Forrelation problem, for an appropriate value of k.

Our proof is Fourier analytical and uses new bounds on the Fourier spectrum of classical decision trees, which could be of independent interest. The proof exploits the differences between sparse polynomials and dense polynomials that arise when analyzing quantum query algorithms versus randomized query algorithms. We further conjectured that the Fourier bounds could be improved in a precise manner. In an exciting development, the conjecture was recently proved by Sherstov, Storozhenk, and Wu — yielding optimal $O(1)$ vs. $N^{1-\epsilon}$ separations between the quantum and randomized query complexities of the k-fold Forrelation problem.

Short Bio: Avishay Tal is an Assistant Professor in the Department of Electrical Engineering and Computer Sciences at the University of California, Berkeley. Avishay received his M.Sc. degree in 2012 under the supervision of Amir Shpilka and his Ph.D. in 2015 under the supervision of Ran Raz. He was a post-doc fellow at the Institute for Advanced Study (2015-2017), Stanford University (2017-2019), and the Simons Institute for the Theory of Computing (Fall 2018). His research interests lie within theoretical computer science and include complexity theory at large, analysis of Boolean functions, circuit complexity, pseudorandomness, computational learning theory, and quantum computing.