Rosenthal, Gregory
Bounds on the QAC^0 Complexity of Approximating Parity
Abstract
QAC circuits are quantum circuits with onequbit gates and Toffoli gates of arbitrary arity. QAC^0 circuits are QAC circuits of constant depth, and are quantum analogues of AC^0 circuits. We prove the following:
 For all d ≥ 7 and ε > 0 there is a depthd QAC circuit of size exp(poly(n^{1/d}) log(n/ε)) that approximates the nqubit parity function to within error ε on worstcase quantum inputs. Previously it was unknown whether QAC circuits of sublogarithmic depth could approximate parity regardless of size.
 We introduce a class of "mostly classical" QAC circuits, including a major component of our circuit from the above upper bound, and prove a tight lower bound on the size of lowdepth, mostly classical QAC circuits that approximate this component.
 Arbitrary depthd QAC circuits require at least Ω(n/d) multiqubit gates to achieve a 1/2 + exp(o(n/d)) approximation of parity. When d = Θ(log n) this nearly matches an easy O(n) size upper bound for computing parity exactly.
 QAC circuits with at most two layers of multiqubit gates cannot achieve a 1/2 + exp(o(n)) approximation of parity, even noncleanly. Previously it was known only that such circuits could not cleanly compute parity exactly for sufficiently large n.
The proofs use a new normal form for quantum circuits which may be of independent interest, and are based on reductions to the problem of constructing certain generalizations of the cat state which we name "nekomata" after an analogous cat yōkai.
BibTeX  Entry
@InProceedings{rosenthal:LIPIcs.ITCS.2021.32,
author = {Gregory Rosenthal},
title = {{Bounds on the QAC^0 Complexity of Approximating Parity}},
booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)},
pages = {32:132:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771771},
ISSN = {18688969},
year = {2021},
volume = {185},
editor = {James R. Lee},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/13571},
URN = {urn:nbn:de:0030drops135713},
doi = {10.4230/LIPIcs.ITCS.2021.32},
annote = {Keywords: quantum circuit complexity, QAC^0, fanout, parity, nekomata}
}
04.02.2021
Keywords: 

quantum circuit complexity, QAC^0, fanout, parity, nekomata 
Seminar: 

12th Innovations in Theoretical Computer Science Conference (ITCS 2021)

Issue date: 

2021 
Date of publication: 

04.02.2021 