Quantum circuits solve 2-fold Forrelation faster than classical AC0 circuits
2-Fold Forrelation is in QAC$^0$
Computational Complexity
Summary
Some problems are very hard for simple classical computers to solve quickly. The authors show that a certain quantum problem called 2-fold Forrelation can be solved efficiently by very basic quantum circuits, even when the problem's input is given directly rather than as a mysterious oracle. This shows a clear difference in what quantum and classical circuits can efficiently do on this problem. Their result points to a natural way to separate simple quantum and classical computation models.
What this means in practice
- •For quantum hardware designers: Use the efficient quantum circuit constructions for 2-fold Forrelation to benchmark low-depth quantum devices against classical circuits.
- •For complexity theorists: Employ the established separation between QAC0 and AC0 to inform theoretical limits on classical versus quantum circuit classes.
A theory result. No direct application yet.
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$.