Quantum circuits solve key problem beyond classical circuits power
2-Fold Forrelation is in QAC$^0$
Computational Complexity
Summary
This paper explores a problem called 2-fold Forrelation, which is related to how certain types of quantum circuits process information. The authors show that small, shallow quantum circuits called QAC^0 can solve this problem efficiently even when the input is given explicitly. This contrasts with classical circuits known as AC^0, which struggle with the same problem. The result reveals a clear difference in capability between these two types of circuits under certain conditions.
quantum circuitsQAC^0AC^0 circuitsForrelationpromise problembounded errorcircuit complexitypolylogarithmic gap
Authors
Francisca Vasconcelos
Abstract
We show that 2-fold Forrelation with inverse-polylogarithmic promise gap can be solved, with bounded error, by polynomial-size QAC$^0$ circuits. Unlike the standard oracle-based Forrelation algorithm, our circuits receive the input explicitly, in the same form as the AC$^0$ circuits against which Forrelation is known to be hard. At constant gap, this yields a natural promise-problem separation between QAC$^0$ and AC$^0$.