## 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

## Repository Citation

Green, Frederic; Homer, Steven; and Pollett, Christopher, "On the complexity of quantum ACC" (2000). *Computer Science*. 65.

https://commons.clarku.edu/faculty_computer_sciences/65

## 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.