# Nov 13th: Prof. Scott Aaronson (MIT)

“Forrelation: A Problem that Optimally Separates Quantum from Classical Computing”

Prof. Scott Aaronson, MIT

ROOM 26-214

THURSDAY, NOVEMBER 13, 2014

12:00 PM – 13:00 PM

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

“The students in MIT’s new NSF training program will be encouraged to cross disciplines, and develop a common fellowship with their peers. We will also address training for post-academic jobs directly by connecting students to government and industrial members of the iQuISE Consortium.”

—Seth Lloyd, Co-Director, iQuISE, and Professor of Mechanical Engineering and Professor of Engineering Systems