| Abstract: | I'll describe recent progress on understanding the largest possible quantum vs. classical speedups in the setting of query complexity.
First, I'll discuss "Forrelation," a problem that Andris Ambainis and I proved yields essentially the largest quantum speedup of any promise problem, as well as Fourier Sampling, which yields essentially the largest speedup of any sampling problem. I'll then explain how Fourier Sampling relates to BosonSampling, the Bremner-Jozsa-Shepherd commuting Hamiltonians model, and other experimental systems that fall short of universal quantum computing, but that might be used in the near future to try to demonstrate quantum supremacy on some task.
Finally, I'll explain how my student Shalev Ben-David "broke the Grover barrier" this summer, achieving a 2.5th-power separation between randomized and quantum query complexities for a total Boolean function---and how the proof of a key conjecture about the Forrelation problem would improve the separation to cubic.
|
