17
$\begingroup$

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?

$\endgroup$
20
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Do you have a citation that shows that $TC^0 \subseteq QACC^0$? $\endgroup$ – Samuel Schlesinger Nov 6 '17 at 14:13
  • $\begingroup$ @SamuelSchlesinger: This paper shows that you can compute threshold, parity, majority, etc. with only fanout gates and 2-qubit gates: theoryofcomputing.org/articles/v001a005 $\endgroup$ – Robin Kothari Nov 7 '17 at 16:22
9
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.