Computer Science

On the complexity of quantum ACC

Document Type

Article

Abstract

For any q>1, let MODq be a quantum gate that determines if the number of 1's in the input is divisible by q. We show that for any q, t>1, MODq is equivalent to MODt (up to constant depth). Based on the case q = 2, Moore has shown that quantum analogs of AC(0), ACC[q], and ACC, denoted QACw f(0), QACC[2], QACC respectively, define the same class of operators, leaving q>2 as an open question. Our result resolves this question, proving that QACw f(0) = QACC[q] = QACC for all q. We also develop techniques for proving upper bounds for QACC in terms of related language classes. We define classes of languages EQACC, NQACC and BQACCQ. We define a notion of log-planar QACC operators and show the appropriately restricted versions of EQACC and NQACC are contained in P/poly. We also define a notion of log-gate restricted QACC operators and show the appropriately restricted versions of EQACC and NQACC are contained in TC(0). To do this last proof, we show that TC(0) can perform iterated addition and multiplication in certain field extensions. We also introduce the notion of a polynomial-size tensor graph and we show that families of such graphs can encode the amplitudes resulting from applying an arbitrary QACC operator to an initial state.

Publication Title

Proceedings of the Annual IEEE Conference on Computational Complexity

Publication Date

2000

First Page

250

Last Page

262

ISSN

1093-0159

DOI

10.1109/CCC.2000.856756

Keywords

Quantum computing, circuits, computer science, polynomials, mathematics. tensile stress, Quantum mechanics, upper bound, Turing machines, parallel processing

APA Citation

Green, F., Homer, S., & Pollett, C. (2000, July). On the complexity of quantum ACC. In Proceedings 15th Annual IEEE Conference on Computational Complexity (pp. 250-262). IEEE.

Link to Full Text

Share

COinS