Exponential Quantum Speed-ups are Generic

Understand

A central problem in quantum computation is to understand which quantum circuits are useful for exponential speed-ups over classical computation.

• We address this question in the setting of query complexity and show that for almost any sufficiently long quantum circuit one can construct a black-box problem which is solved by the circuit with a constant number of quantum queries, but which requires exponentially many classical queries, even if the classical machine has the ability to postselect.
• We prove the result in two steps.
• In the first, we show that almost any element of an approximate unitary 3-design is useful to solve a certain black-box problem efficiently.