On the Complexity of Quantum ACCReport as inadecuate

On the Complexity of Quantum ACC

On the Complexity of Quantum ACC - Download this document for free, or read online. Document in PDF available to download.


Green, Frederic; Homer, Steven; Pollett, Christopher. -On the Complexity of Quantum ACC-, Technical Report BUCS-2000-003, Computer Science Department, Boston University, January 20, 2000. Available from: http:-hdl.handle.net-2144-1798


For any q > 1, let MOD q 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, MOD q is equivalent to MOD t up to constant depth. Based on the case q=2, Moore has shown that quantum analogs of AC^0, ACCq, and ACC, denoted QAC^0 wf, QACC2, QACC respectively, define the same class of operators, leaving q > 2 as an open question. Our result resolves this question, implying that QAC^0 wf = QACCq = QACC for all q. We also prove the first upper bounds for QACC in terms of related language classes. We define classes of languages EQACC, NQACC both for arbitrary complex amplitudes and BQACC for rational number amplitudes and show that they are all contained in TC^0. To do this, we show that a TC^0 circuit can keep track of the amplitudes of the state resulting from the application of a QACC operator using a constant width polynomial size tensor sum. In order to accomplish this, we also show that TC^0 can perform iterated addition and multiplication in certain field extensions.

CAS: Computer Science: Technical Reports -

Author: Green, Frederic - Homer, Steven - Pollett, Christopher - -

Source: https://open.bu.edu/


Related documents