Interactive shallow Clifford circuits: quantum advantage against NC${}^1$ and beyond

Daniel Grier, Luke Schaeffer

Recent work of Bravyi et al. and follow-up work by Bene Watts et al. demonstrates a quantum advantage for shallow circuits: constant-depth quantum circuits can perform a task which…