Colloquium featuring Avishay Tal, University of California, Berkeley
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. To date, separations of $O(1)$ vs. $\sqrt{N}$ between quantum and randomized query complexities remain 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. Looking forward, we conjecture that the Fourier bounds could be further improved in a precise manner, and show how such conjectured bounds imply optimal $O(1)$ vs. $N^{1-\epsilon}$ separations between the quantum and randomized query complexities of the k-fold Forrelation problem.
Webex Online - Event address for attendees:
https://uwaterloo.webex.com/uwaterloo/onstage/g.php?MTID=e62f0e6733d10a83d79e0c2afa51c9559
Event number (access code): 160 849 2082
Event password: fPFkjpMB238