Source-linked AI summary
2-Fold Forrelation is in QAC$^0$
Francisca Vasconcelos
TL;DR
2-fold Forrelation is a natural candidate for separating shallow quantum and classical circuits, but its standard quantum algorithm uses binary-addressed queries that pose a fan-out bottleneck for QAC0. This paper implements the test with explicit inputs and proves a bounded-error QAC0 upper bound for inverse-polylogarithmic gaps, giving a decision separation from AC0 at constant gap.
Problem
The standard Forrelation algorithm uses binary-addressed coherent lookup, which poses an unresolved fan-out bottleneck for implementing it in QAC0 on explicit inputs.
Source: §1 · p. 2Method
The construction uses a one-hot interference test and truncated phase-state repetition to implement the computation in QAC0.
Source: §1 · pp. 2–3Results
Takeaways & Limitations
2-fold Forrelation provides a natural promise-problem separation between QAC0 and AC0 at constant gap.
Source: §1 · pp. 1–2The test depends only on the square of ForrN(x, y), so it does not distinguish positive from negative Forrelation.
Source: §4.1 · p. 9
Abstract
from arXiv · showhide
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$.
1 Introduction
The introduction frames 2-fold Forrelation as a natural test of shallow quantum-versus-classical power and identifies binary-addressed coherent lookup as an obstacle to implementing it in QAC0. It presents a one-hot interference test and repetition scheme yielding a QAC0 upper bound and, at constant gap, a decision separation.
1 Introduction
- For every inverse-polylogarithmic gap, 2-fold Forrelation has a bounded-error polynomial-size QAC0 circuit, yielding a constant-gap decision separation from AC0.The circuit is correct on every promised input.Source: §1 · pp. 1–2
- The standard binary-addressed phase oracle requires coherent indexing, for which no polynomial-size constant-depth QAC0 construction is known without unbounded quantum fan-out.Unbounded fan-out suffices for binary-to-one-hot conversion, the operation underlying this bottleneck.Source: §1 · pp. 1–2
- One-hot W states let disjoint CZ gates apply input-dependent phases transversally, avoiding coherent binary-addressed lookup while summing phases over address pairs.The resulting amplitude is proportional to ForrN(x, y) before measurement squares it.Source: §1 · pp. 2–3
- The quantum test's rare-event probability has no constant background, unlike the classical two-query test's small bias around 1/2.Repeating until any trial accepts amplifies the quantum multiplicative separation to a constant additive gap, but drives both classical cases toward acceptance one.Source: §1 · p. 3
- Truncated phase-state repetition consolidates each input bit's phase and computes its occupancy parity in constant depth below a polylogarithmic cutoff.In the inverse-polylogarithmic-gap regime, branches exceeding the cutoff have negligible total weight, so the desired phases are reproduced up to negligible error.Source: §1 · p. 3
- Compared with Grier–Morris–Wu [GMW26] and Gretta–Gupta–Joshi, the result uses a standard single-copy input and gives pointwise promise correctness.Its tradeoff is a promise problem and a classical lower bound only against AC0.Source: §1 · p. 4
2 Preliminaries
The preliminaries fix the explicit-input circuit setting and collect the QAC0 primitives used in the construction. They also establish the classical constant-gap Forrelation size lower bound that supports the later separation.
2.1 Circuit Classes and Forrelation
- QAC0 circuits have constant depth and polynomial size, use arbitrary one-qubit and generalized Toffoli gates, and lack unbounded fan-out, measurements, postselection, and oracle gates.The input strings have length N each, with coordinates indexed by {0,1}^m and m = log2 N.Source: §2.1 · p. 5
2.2 QAC0 primitives
- The construction draws on exact polylogarithmic fan-out and W-state preparation, plus exact low-weight threshold computations.These are among the four prior-work ingredients recorded for the proof.Source: §2.2 · pp. 5–6
- Truncated parity agrees with Parity through Hamming weight T and is zero above T, giving an exact polynomial-size constant-depth QAC0 implementation when T is polylogarithmic.In phase-state repetition, occupancy parities consolidate each input bit's repeated phases; truncation approximates the desired phases when high occupancies occur only on negligible-weight branches.Source: §2.2 · p. 6
2.3 Forrelation Classical Circuit Lower Bounds
- exp(N^Ω_d(1)) size is required for fixed-depth bounded-error randomized AC0 circuits solving constant-gap Forrelation.The lower bound is pointwise for inputs satisfying the promise, although distributions are used to establish it.Source: §2.3 · p. 7
3 Main Results
The main results give a bounded-error QAC0 upper bound for explicit-input 2-fold Forrelation at inverse-polylogarithmic gap. At constant gap, this yields a separation from bounded-error randomized AC0, while threshold circuits solve the promise for every gap.
3 Main Results
- For δ(N) ≥ log^-c N, explicit-input 2-fold Forrelation lies in Promise-BQAC0 with depth O_c(1), size N^O_c(1), and polynomial total width.The circuit receives the explicit 2N-bit input (x, y).Source: §3 · p. 7
- O(N^2)-size deterministic constant-depth threshold circuits solve the promise for every gap function δ(N) ∈ (0, 1].They compute the N^2 pair indicators in parallel and use one threshold gate to distinguish the promised ranges.Source: §3 · pp. 7–8
- At constant gap, 2-fold Forrelation separates polynomial-size constant-depth QAC0 circuits from bounded-error randomized AC0 circuits, which require exp(N^Ω_d(1)) size at fixed depth.The result concerns the same explicit input of length 2N.Source: §3 · pp. 7–8
4 Proof of the QAC0 Forrelation circuit
The proof constructs a one-hot Forrelation test with acceptance probability Forr_N(x, y)^2/N, then coherently amplifies it to obtain a bounded-error QAC^0 circuit for every inverse-polylogarithmic promise gap.
4.1 A Single One-Hot Forrelation Test
- The test appends binary labels to the one-hot registers, applies the Walsh–Hadamard sign, and projects the registers back to make signed amplitudes interfere.The one-hot registers are retained while labels are appended; controlled-Z gates on corresponding label bits supply the phase (−1)^{u·v}.Source: §4.1 · pp. 8–9
- The one-hot test accepts with probability Forr_N(x, y)^2/N, giving a single-test basis for amplification.It retains the Forrelation value only through its square, so it does not distinguish positive from negative values.Source: §4 · p. 8, §4.1 · p. 9
- The squared test cannot distinguish positive from negative Forrelation, so the promise separates positive YES instances from small-magnitude NO instances.Source: §4.1 · p. 9
4.2 Amplification and Proof of Theorem 3.1
- For every inverse-polylogarithmic gap, coherent amplification yields completeness at least 2/3 and soundness at most 1/3 with constant-depth, polynomial-size circuits.The construction uses R = Θ(N/δ^2) effective tests from a single copy of each input string.Source: §4.2 · p. 10