<p>The question makes sense, and the short answer is that it's an open problem.</p>

<p>Here's the long answer: Depending on how you define constant-depth unbounded-fanin quantum circuits, you might get different classes. QAC<sup>0</sup> is usually defined to have unbounded fanin Toffoli gates and single-qubit gates. QAC<sup>0</sup><sub>wf</sub> 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 AC<sup>0</sup>, also ACC<sup>0</sup> and TC<sup>0</sup>. </p>

<p>So the obvious question to ask is whether PARITY is contained in QAC<sup>0</sup>, and this is an open problem. It is equivalent to asking whether QAC<sup>0</sup> = QAC<sup>0</sup><sub>wf</sub>. I guess that the belief is that PARITY is not in QAC<sup>0</sup>. Further information can be found in the survey <a href="http://dx.doi.org/10.1145/1272729.1272739" rel="noreferrer">Small depth quantum circuits</a> by Bera, Green and Homer.</p>

CC BY-SA 3.0
2017-11-06T14:13:06.560Z
Do you have a citation that shows that $TC^0 \subseteq QACC^0$?
Samuel Schlesinger
CC BY-SA 3.0
2017-11-07T16:22:01.830Z
@SamuelSchlesinger: This paper shows that you can compute threshold, parity, majority, etc. with only fanout gates and 2-qubit gates: http://www.theoryofcomputing.org/articles/v001a005/
Robin Kothari
CC BY-SA 2.5
2011-02-24T21:20:25.150Z
2011-02-24T21:20:25.150Z
Robin Kothari
<p>Surprisingly, the number of extra work qubits (ancilla) matters. Right now it is known that PARITY is not in QAC_0 with bounded ancillae. <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.9.9565">Quantum lower bounds for fanout</a> gives one proof for circuits using at most linearly many ancilla and 
<a href="http://dl.acm.org/citation.cfm?id=1994580">doi:10.1016/j.ipl.2011.05.002</a> gives another proof for circuits using no ancillae.</p>

CC BY-SA 3.0
2011-08-30T02:50:39.983Z
2011-08-30T02:50:39.983Z
dBera
<p>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.</p>

<p>What about QUANTUM circuits?</p>

<p>a) Can PARITY be done with a quantum circuit that has constant depth and poly number of gates?</p>

<p>b) Does my question even make sense?</p>

CC BY-SA 2.5
2011-02-24T21:10:52.420Z
This seems relevant: http://eccc.uni-trier.de/eccc-reports/1999/TR99-032/
Ross Snider
<cc.complexity-theory><quantum-computing><circuit-complexity>
Is PARITY in QAC_0 (if that even makes sense)
Bill GASARCH
# Is PARITY in QAC_0 (if that even makes sense)

(Asked by: username_0 on 2011-02-24)

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?

**Tags:** cc.complexity-theory, quantum-computing, circuit-complexity
> **Comments:**
> **username_1**: This seems relevant: http://eccc.uni-trier.de/eccc-reports/1999/TR99-032/  

---

## 2 answers

### Answer by username_2 on 2011-02-24. Score: 20

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](http://dx.doi.org/10.1145/1272729.1272739) by Bera, Green and Homer.

> **Comments:**
> **username_3**: Do you have a citation that shows that $TC^0 \subseteq QACC^0$?  
> **username_2**: @SamuelSchlesinger: This paper shows that you can compute threshold, parity, majority, etc. with only fanout gates and 2-qubit gates: http://www.theoryofcomputing.org/articles/v001a005/  

---

### Answer by username_4 on 2011-08-30. Score: 10

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](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.9.9565) gives one proof for circuits using at most linearly many ancilla and
[doi:10.1016/j.ipl.2011.05.002](http://dl.acm.org/citation.cfm?id=1994580) gives another proof for circuits using no ancillae.


---

