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 ... more >>>

In this work we consider the interplay between multiprover interactive proofs, quantum
entanglement, and zero knowledge proofs — notions that are central pillars of complexity theory,
quantum information and cryptography. In particular, we study the relationship between the
complexity class MIP$^*$ , the set of languages decidable by multiprover interactive ... more >>>