Cliffords in constant depth
Daniel Grier and Luke Schaeffer released a wonderful paper on arXiv recently. In it, they highlight some surprisingly stronger separations between QNC0, constant depth quantum circuits, and constant depth classical circuits. For background, Bravyi, et al.’s major result two years ago was a strict separation between (noiseless) QNC0 and NC0 circuits by a problem called the “Hidden Linear Function problem.” But Grier and Schaeffer prove a stronger separation between (noiseless) QNC0 and AC0[p] circuits in their new paper. And it was my first time seeing the use of Barrington’s Theorem, and it’s amazing just how general but powerful it is!
In their paper, they point to a fairly old theorem in measurement-based quantum computation which I was even more surprised by. In short, it’s that any Clifford circuit can be implemented in constant depth by preparation of a constant degree grid state and constant depth MBQC if you’re willing to incur detectable Pauli errors.