Forrelation: A Problem that Optimally Separates Quantum from Classical Computing

Thumbnail

Event details

Date 16.01.2015
Hour 15:0016:00
Speaker Scott Aaronson, MIT
Location
Category Conferences - Seminars
We achieve essentially the largest possible separation between quantum and classical query complexities.  We do so using a property-testing problem called Forrelation, where one needs to decide whether one Boolean function is highly correlated with the Fourier transform of a second function.  This problem can be solved using 1 quantum query, yet we show that any randomized algorithm needs Omega(sqrt(N) / log(N)) queries (improving an Omega(N^{1/4}) lower bound of Aaronson).  Conversely, we show that this 1 versus ~Omega(sqrt(N)) separation is optimal: indeed, any t-query quantum algorithm whatsoever can be simulated by an O(N^{1-1/2t})-query randomized algorithm. Thus, resolving an open question of Buhrman et al. from 2002, there is no partial Boolean function whose quantum query complexity is constant and whose randomized query complexity is linear. We conjecture that a natural generalization of Forrelation achieves the optimal t versus ~Omega(N^{1-1/2t}) separation for all t. As a bonus, we show that this generalization is BQP-complete. This yields what's arguably the simplest BQP-complete problem yet known, and gives a second sense in which Forrelation "captures the maximum power of quantum computation."

Joint work with Andris Ambainis.  No quantum computing background is needed for this talk.

Bio: Scott is an Associate Professor of Electrical Engineering and Computer Science at MIT, affiliated with CSAIL. His research interests center around the capabilities and limits of quantum computers, and computational complexity theory more generally.

Practical information

  • Informed public
  • Free

Organizer

  • Nisheeth Vishnoi

Event broadcasted in

Share