BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Memento EPFL//
BEGIN:VEVENT
SUMMARY:Forrelation: A Problem that Optimally Separates Quantum from Class
 ical Computing
DTSTART:20150116T150000
DTEND:20150116T160000
DTSTAMP:20260407T181100Z
UID:7ba3994da3b999c7ec66d28f5bf96a80d049854ac79db8a46740b8f8
CATEGORIES:Conferences - Seminars
DESCRIPTION:Scott Aaronson\, MIT\nWe achieve essentially the largest possi
 ble separation between quantum and classical query complexities.  We do s
 o 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 quan
 tum 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 opt
 imal: indeed\, any t-query quantum algorithm whatsoever can be simulated b
 y an O(N^{1-1/2t})-query randomized algorithm. Thus\, resolving an open qu
 estion of Buhrman et al. from 2002\, there is no partial Boolean function 
 whose quantum query complexity is constant and whose randomized query comp
 lexity is linear. We conjecture that a natural generalization of Forrelati
 on 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."\nJoint work with Andris Ambainis.  No quantum computing bac
 kground is needed for this talk.\nBio: 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 quan
 tum computers\, and computational complexity theory more generally.
LOCATION:BC 420 https://plan.epfl.ch/?room==BC%20420
STATUS:CONFIRMED
END:VEVENT
END:VCALENDAR