  The relationship between BQP and PH has been an open problem since the
earliest days of quantum computing. We present evidence that quantum computers
can solve problems outside the entire polynomial hierarchy, by relating this
question to topics in circuit complexity, pseudorandomness, and Fourier
analysis.
  First, we show that there exists an oracle relation problem (i.e., a problem
with many valid outputs) that is solvable in BQP, but not in PH. This also
yields a non-oracle relation problem that is solvable in quantum logarithmic
time, but not in AC0.
  Second, we show that an oracle decision problem separating BQP from PH would
follow from the Generalized Linial-Nisan Conjecture, which we formulate here
and which is likely of independent interest. The original Linial-Nisan
Conjecture (about pseudorandomness against constant-depth circuits) was
recently proved by Braverman, after being open for twenty years.
