Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
As is well known PARITY cannot be done in poly-sized constant-depth circuits, and in fact const-dept circuits require EXP number of gates.
What about QUANTUM circuits?
a) Can PARITY be done with a quantum circuit that has constant depth and poly number of gates?
b) Does my question even make sense?
The question makes sense, and the short answer is that it's an open problem.
Here's the long answer: Depending on how you define constant-depth unbounded-fanin quantum circuits, you might get different classes. QAC0 is usually defined to have unbounded fanin Toffoli gates and single-qubit gates. QAC0wf is the class where we also allow a "fanout" gate, which copies an input bit to many outputs. (It implements |a>|0>...|0> --> |a>|a>...|a>) This class is really powerful since it contains, besides PARITY and AC0, also ACC0 and TC0.
So the obvious question to ask is whether PARITY is contained in QAC0, and this is an open problem. It is equivalent to asking whether QAC0 = QAC0wf. I guess that the belief is that PARITY is not in QAC0. Further information can be found in the survey Small depth quantum circuits by Bera, Green and Homer.
Surprisingly, the number of extra work qubits (ancilla) matters. Right now it is known that PARITY is not in QAC_0 with bounded ancillae. Quantum lower bounds for fanout gives one proof for circuits using at most linearly many ancilla and doi:10.1016/j.ipl.2011.05.002 gives another proof for circuits using no ancillae.
