pipette
ENEnglish

The Robustness of QAC0

Daniel Grier, Jackson Morris, Kewen Wu

Preprint

En palabras de los autores

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.

Resultado principalEl resumen no menciona limitaciones.

Apareció: viernes, 2 de octubre. arXiv. Preprint, todavía sin revisión por pares.