CSAIL Event Calendar: Previous Series

Pseudorandom generators, the BQP vs. PH problem, and beating the hybrid argument

Speaker: Chris Umans , Caltech
Date: March 15 2011
Time: 4:15PM to 5:15PM
Location: 32-155
Host: Scott Aaronson, CSAIL, MIT

It is a longstanding open problem to devise an oracle relative to which BQP does not lie in the Polynomial-Time Hierarchy (PH). We advance a natural conjecture about the capacity of the Nisan-Wigderson pseudorandom generator [NW94] to fool AC^0, with MAJORITY as its hard function. Our conjecture is essentially that the loss due to the hybrid argument (which is a component of the standard proof from [NW94]) can be avoided in this setting. We then show that our conjecture implies the existence of an oracle relative to which BQP is not in the PH. This entails giving an explicit construction of unitary matrices, realizable by small quantum circuits, whose row-supports are “nearly-disjoint.” Our framework generalizes the setting of Aaronson [Aar09], and remains a viable approach to resolving the BQP vs. PH problem after the recent proof that the Generalized Linial-Nisan Conjecture of [Aar09] is false.



As a first step towards proving our conjecture, we show that the loss from the hybrid argument can indeed be avoided for "repeated sampling" generators based on PARITY, MAJORITY, and other functions. This leads to new pseudorandom generators for the low-level circuit classes AC^0[p], which have sublinear stretch, but nevertheless represent the best-known generators for these classes.



Based on joint work with Bill Fefferman, Ronen Shaltiel, and Emanuele Viola.

See other events that are part of Theory Colloquium 2010/2011

See other events happening in March 2011