Tight bounds on depth-2 QAC-circuits computing parity

Stephen Fenner, Daniel Grier, Daniel Padé +1

We show that the parity of more than three non-target input bits cannot be computed by QAC-circuits of depth-2, not even uncleanly, regardless of the number of ancilla qubits. This…