Parity vs. AC0 with simple quantum preprocessing

Joseph Slote

A recent line of work has shown the unconditional advantage of constant-depth quantum computation, or $\mathsf{QN}{\mathsf{C}}^0$, over $\mathsf{N}{\mathsf{C}}^0$, $\mathsf{A}{\mathsf{C}}^0$, and related models of…