pipette
ESEspañol

The Robustness of QAC0

Daniel Grier, Jackson Morris, Kewen Wu

Preprint

In the authors' words

In this work we study the robustness of with respect to error tolerance and modifications to its gate-set. First, we investigate whether the non-zero error typically allowed for circuits computing Boolean functions is truly necessary. We show that the error inherent in the parallel -test of \cite{grier_morris_wu} can be eliminated entirely via a novel application of exact amplitude amplification in the many-copies context. Consequently, we find that can exactly simulate with polynomially many copies of the classical input and that for every fixed prime exact , , can compute total Boolean functions outside of . Second, we ask to what extent the computational power of follows from the fact that arbitrary single-qubit gates may be used at any point in the circuit. We find that is in fact robust to restrictions on which single-qubit gates are permitted: every circuit can be approximately implemented by a circuit consisting of just generalized Toffoli, , and Hadamard gates. Moreover, this approximating circuit can be constructed efficiently from a classical description of the original circuit.

Main resultThe abstract does not state a limitation.

Appeared: Friday, October 2. arXiv. Preprint, not yet peer-reviewed.