Bounds on the QAC${}^0$ Complexity of Approximating Parity

Gregory Rosenthal

QAC circuits are quantum circuits with one-qubit gates and Toffoli gates of arbitrary arity. QAC${}^0$ circuits are QAC circuits of constant depth, and are quantum analogues of AC$^0…