TCS+ Talk

Please join us this TCS+ video seminar. Coffee and pastries will be served.

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.