Pseudorandom generators, the BQP vs. PH problem, and beating the hybrid argument
Speaker: Chris Umans , Caltech
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.