Nov 13th: Prof. Scott Aaronson (MIT)

“Forrelation: A Problem that Optimally Separates Quantum from Classical Computing”
Prof. Scott Aaronson, MIT

ROOM 26-214
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 IGERT program has been developed to meet the challenges of educating U.S. Ph.D. scientists, engineers, and educators with the interdisciplinary backgrounds, deep knowledge in chosen disciplines, and technical, professional, and personal skills to become in their own careers the leaders and creative agents for change.”

—The National Science Foundation