QAC0 circuits achieve exact computation and gate set robustness
The Robustness of QAC0
Computational Complexity
Summary
This paper looks at a special kind of quantum circuit called QAC0 and sees how reliable it is when we make small changes. The authors show that the usual chance of errors in these circuits can be completely removed by using multiple copies of the input and a special technique called exact amplitude amplification. They also find that even if the quantum circuit is limited to only certain basic gates, it can still perform the same tasks approximately as before. Thus, these quantum circuits are stronger and more stable than previously thought.
What this means in practice
- •For quantum hardware designers: Build quantum circuits that use only certain simple gates yet realize complex computations reliably and approximately.
- •For quantum algorithm developers: Design exact quantum algorithms that use polynomially many input copies for precise Boolean function evaluation beyond classical limits.
A theory result. No direct application yet.
Authors
Daniel Grier, Jackson Morris, Kewen Wu
Abstract
In this work we study the robustness of $\mathsf{QAC}^0$ with respect to error tolerance and modifications to its gate-set. First, we investigate whether the non-zero error typically allowed for $\mathsf{QAC}^0$ circuits computing Boolean functions is truly necessary. We show that the error inherent in the parallel $W$-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 $\mathsf{QAC}^0$ can \textit{exactly} simulate $\mathsf{TC}^0$ with polynomially many copies of the classical input and that for every fixed prime $p$ exact $\mathsf{QAC}^0$, $\mathsf{EQAC}^0$, can compute total Boolean functions outside of $\mathsf{AC}^0[p]$. Second, we ask to what extent the computational power of $\mathsf{QAC}^0$ follows from the fact that arbitrary single-qubit gates may be used at any point in the circuit. We find that $\mathsf{QAC}^0$ is in fact robust to restrictions on which single-qubit gates are permitted: every $\mathsf{QAC}^0$ circuit can be approximately implemented by a $\mathsf{QAC}^0$ circuit consisting of just generalized Toffoli, $S$, and Hadamard gates. Moreover, this approximating circuit can be constructed efficiently from a classical description of the original circuit.