Quantum advantage with shallow circuits

Sergey Bravyi, David Gosset, Robert Koenig

We prove that constant-depth quantum circuits are more powerful than their classical counterparts. To this end we introduce a non-oracular version of the Bernstein-Vazirani problem…