Title: Quantum advantage with shallow circuits
|Affiliation:||University of Waterloo|
A constant-depth quantum circuit is a parallel quantum computation that proceeds for a constant number of time steps. In this work we prove that constant-depth quantum circuits are more powerful than their classical counterparts. We describe a linear algebra problem which can be solved with certainty by a constant-depth quantum circuit composed of one- and two-qubit gates. In contrast, we prove that any classical probabilistic circuit composed of bounded fan-in gates that solves the problem with high probability must have depth logarithmic in the input size. The quantum advantage for this task is due to a strong form of quantum nonlocality which we establish is present in the measurement statistics of quantum states generated by constant-depth quantum circuits.
This is joint work with Sergey Bravyi and Robert Koenig .