Computer Science

Counting, fanout, and the complexity of quantum ACC

Document Type

Article

Abstract

We propose definitions of QAC0, the quantum analog of the classical class AC0 of constant-depth circuits with AND and OR gates of arbitrary fan-in, and QACC[q], the analog of the class ACC[q] where Modq gates are also allowed. We prove that parity or fanout allows us to construct quantum MODq gates in constant depth for any q, so QACC[2] = QACC. More generally, we show that for any q,p > 1, MODq is equivalent to MODp (up to constant depth and polynomial size). This implies that QAC0 with unbounded fanout gates, denoted QAC0wf, is the same as QACC[q] and QACC for all q. Since ACC[p] ≠ ACC[q] whenever p and q are distinct primes, QACC[q] is strictly more powerful than its classical counterpart, as is QAC0 when fanout is allowed. This adds to the growing list of quantum complexity classes which are provably more powerful than their classical counterparts. We also develop techniques for proving upper bounds for QACC in terms of related language classes. We define classes of languages closely related to QACC[2] and show that restricted versions of them can be simulated by polynomial-size circuits. With further restrictions, language classes related to QACC[2] operators can be simulated by classical threshold circuits of polynomial size and constant depth.

Publication Title

Quantum Information and Computation

Publication Date

2002

Volume

2

Issue

1

First Page

35

Last Page

65

ISSN

1533-7146

Keywords

quantum & circuit complexity, quantum computation, threshold circuit

APA Citation

Green, F., Homer, S., Moore, C., & Pollett, C. (2001). Counting, fanout, and the complexity of quantum ACC. arXiv preprint quant-ph/0106017.

Link to Full Text

Share

COinS