This talk is today at 4pm. The main technical heavy lifting is classical but it solves a long-standing problem in quantum complexity theory. ---------- Forwarded message --------- From: <calendar(a)csail.mit.edu> Date: Tue, Nov 27, 2018 at 12:01 AM Subject: [Theory-seminars] TALK: Tuesday 11-27-2018 Avishay Tal: Oracle Separation of BQP and the Polynomial Hierarchy To: <seminars(a)csail.mit.edu>du>, <theory-seminars(a)csail.mit.edu> Avishay Tal: Oracle Separation of BQP and the Polynomial Hierarchy *Seminar Series:* Theory of Computation (TOC) 2018 *Speaker:* Avishay Tal, Simons Instititue & Stanford University *Host:* Virginia Vassilevska Williams *Date:* Tuesday, November 27, 2018 *Time:* 4:00 PM to 5:00 PM *Location:* Patil/Kiva G449 Abstract: In their seminal paper, Bennett, Bernstein, Brassard and Vazirani [SICOMP, 1997] showed that relative to an oracle, quantum algorithms are unable to solve NP-complete problems in sub-exponential time (i.e., that Grover's search is optimal in this setting). In this work, we show a strong converse to their result. Namely, we show that, relative to an oracle, there exist computational tasks that can be solved efficiently by a quantum algorithm, but require exponential time for any algorithm in the polynomial hierarchy. (The polynomial hierarchy is a hierarchy of complexity classes that captures P, NP, coNP, and their generalizations.) The tasks that exhibit this "quantum advantage" arise from a pseudo-randomness approach initiated by Aaronson [STOC, 2010]. Our core technical result is constructing a distribution over Boolean strings that "look random" to constant-depth circuits of quasi-polynomial size, but can be distinguished from the uniform distribution by very efficient quantum algorithms. Joint work with Ran Raz. For more information please contact: Deborah Goodwin, 617.324.7303, dlehto(a)csail.mit.edu _______________________________________________ Theory-seminars mailing list Theory-seminars(a)lists.csail.mit.edu https://lists.csail.mit.edu/mailman/listinfo/theory-seminars _______________________________________________ qip mailing list qip(a)mit.edu http://mailman.mit.edu/mailman/listinfo/qip