24 January 2014, CWI Algorithms & Complexity seminar, Bill Fefferman (Caltech)

How powerful are quantum computers? Despite the prevailing belief that quantum computers are more powerful than their classical counterparts, this remains a conjecture backed by little formal evidence. Shor's famous factoring algorithm gives an example of a problem that can be solved efficiently on a quantum computer with no known efficient classical algorithm. Factoring, however, is unlikely to be NP-Hard, and few unexpected formal consequences would arise, should such a classical algorithm be discovered. Nonetheless, is there evidence we can give that quantum computers can solve problems whose solutions can't be verified efficiently? In this talk, I'll address this question from two different perspectives.

First, I'll discuss a longstanding open problem to devise an oracle relative to which BQP does not lie in the Polynomial Hierarchy (PH). I'll describe progress on this separation, connecting the problem to a question studied previously in the classical pseudorandomness literature. In particular, we advance a natural conjecture about the capacity of the Nisan-Wigderson pseudorandom generator 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 of Nisan and Wigderson) can be avoided in this setting. We 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.”

In the second part of the talk, I'll discuss the BQP vs PH problem from the perspective of sampling problems. Namely, is there some distribution that can be sampled efficiently by a quantum computer, that can't be approximately sampled (to within inverse-polynomial total variation distance) in the Polynomial Hierarchy? I'll show recent progress on this problem, complementing and generalizing the evidence given in Aaronson's work on the Computational Complexity of Linear Optics, where a different distribution with the same computational properties was given. Our result is far more general than his, but requires a more powerful quantum sampler.

Based on joint work with Chris Umans

For more information, please contact rdewolf at cwi.nl.