We study the randomized classical query complexity of cyclic Forrelation, a cyclic analogue of $k$-Forrelation [AA15, STOC'15; BS21, STOC'21]. Given $k$ Boolean functions $f_1,\ldots,f_k:\mathbb{F}_2^n\to\{-1,1\}$, the goal is to estimate $T_k=N^{-1}\operatorname{Tr}(D_{f_1}H^{\otimes n}\cdots D_{f_k}H^{\otimes n}),$ where $D_{f_i}=\operatorname{diag}(f_i(x):x\in\mathbb{F}_2^n)$, $H$ is the Hadamard gate, and $N=2^n$. This normalized-trace problem can be solved with $k$ quantum queries in the DQC1 model. Its classical query complexity was left open in [JLS+26, FOCS'26], which conjectured a lower bound of $\widetildeΩ(N^{1-2/k})$.
We establish a nearly complete characterization of the nonadaptive classical query complexity of cyclic Forrelation. For even $k\ge 4$, we prove a tight bound of $Θ_k(N^{1-2/k})$ for constant additive error. For odd $k\ge 5$, we obtain a lower bound of $Ω_k(N^{1-2/(k-1)})$ and an upper bound of $O_k(N^{1-2/k})$. Surprisingly, $k=3$ admits a polylogarithmic-query nonadaptive classical algorithm, disproving the conjecture in this case. These results suggest an unexpected parity-dependent structure: the nonadaptive complexity may be governed by the independence number of the $k$-cycle, leading to the exponent $1-1/\lfloor k/2\rfloor$, rather than the previously conjectured $1-2/k$, which was motivated by a Fourier-growth heuristic. Finally, allowing adaptivity, we prove a lower bound of $Ω(N^{1/4})$ for every $k\ge4$.
Although formally close to $k$-Forrelation, the cyclic structure leads to rather different classical behavior and requires different techniques. Our lower bounds are based on hidden-shift collision constructions, and our upper bounds follow from randomized sampling together with cycle-specific conditional-moment estimates. Our results provide a systematic understanding of its query advantages over classical computation.
AI Summary
The paper studies the randomized classical query complexity of cyclic Forrelation: estimating $T_k=N^{-1}\operatorname{Tr}(D_{f_1}H^{\otimes n}\cdots D_{f_k}H^{\otimes n})$ for Boolean phase oracles, with $N=2^n$. This normalized-trace task admits a DQC1 algorithm using $O(k)$ queries at constant additive accuracy. The question is how its classical complexity differs from standard, matrix-element Forrelation.
For fixed even $k\ge4$, the nonadaptive classical complexity is $\Theta_k(N^{1-2/k})$ at constant error. More generally, for $k=2m$, it is $\Theta(m\min\{N,N^{1-1/m}\varepsilon^{-2/m}\})$ at additive error $\varepsilon$. For odd $k\ge5$, constant-error nonadaptive bounds are $\Omega_k(N^{1-2/(k-1)})$ and $O_k(N^{1-2/k})$. In contrast, $k=3$ admits an $O(n\log n)$-query nonadaptive algorithm at constant error, refuting a previous conjecture predicting an $N^{1/3}$ lower bound. Against adaptive classical algorithms, the paper proves $\Omega(N^{1/4})$ queries for every $k\ge4$.
The nonadaptive lower bounds encode a hidden sign in shifted random functions, requiring multiway query collisions; quadratic phases transfer the construction to odd cycles. Upper bounds use Cartesian-product sampling and cycle-dependent conditional second moments. The three-cycle algorithm instead uses a Fourier identity and nonadaptive Goldreich–Levin coefficient recovery. The adaptive lower bound uses random masks on hidden-subspace cosets and a transcript-coupling argument.
Matching constant-error bounds remain open for odd cycles and adaptive algorithms. The paper conjectures that the nonadaptive exponent is $1-1/\lfloor k/2\rfloor$, determined by the cycle’s independence number; its current sampling estimator cannot attain this exponent for odd cycles.
Little sign of AI-generated textAI use disclosed
The manuscript was written by the authors, with assistance from GPT-6 in revising the exposition, polishing the language, and checking the arguments.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
We study the randomized classical query complexity of cyclic Forrelation, a cyclic analogue of k-Forrelation [AA15, STOC'15; BS21, STOC'21]. Given k Boolean functions f1,…,fk:F2n→{−1,1}, the goal is to estimate Tk=N−1Tr(Df1H⊗n⋯DfkH⊗n), where Dfi=diag(fi(x):x∈F2n), H is the Hadamard gate, and N=2n. This normalized-trace problem can be solved with k quantum queries in the DQC1 model. Its classical query complexity was left open in [JLS+26, FOCS'26], which conjectured a lower bound of Ω(N1−2/k).
We establish a nearly complete characterization of the nonadaptive classical query complexity of cyclic Forrelation. For even k≥4, we prove a tight bound of Θk(N1−2/k) for constant additive error. For odd k≥5, we obtain a lower bound of Ωk(N1−2/(k−1)) and an upper bound of Ok(N1−2/k). Surprisingly, k=3 admits a polylogarithmic-query nonadaptive classical algorithm, disproving the conjecture in this case. These results suggest an unexpected parity-dependent structure: the nonadaptive complexity may be governed by the independence number of the k-cycle, leading to the exponent 1−1/⌊k/2⌋, rather than the previously conjectured 1−2/k, which was motivated by a Fourier-growth heuristic. Finally, allowing adaptivity, we prove a lower bound of Ω(N1/4) for every k≥4.
Although formally close to k-Forrelation, the cyclic structure leads to rather different classical behavior and requires different techniques. Our lower bounds are based on hidden-shift collision constructions, and our upper bounds follow from randomized sampling together with cycle-specific conditional-moment estimates. Our results provide a systematic understanding of its query advantages over classical computation.
The paper studies the randomized classical query complexity of cyclic Forrelation: estimating Tk=N−1Tr(Df1H⊗n⋯DfkH⊗n) for Boolean phase oracles, with N=2n. This normalized-trace task admits a DQC1 algorithm using O(k) queries at constant additive accuracy. The question is how its classical complexity differs from standard, matrix-element Forrelation.
For fixed even k≥4, the nonadaptive classical complexity is Θk(N1−2/k) at constant error. More generally, for k=2m, it is Θ(mmin{N,N1−1/mε−2/m}) at additive error ε. For odd k≥5, constant-error nonadaptive bounds are Ωk(N1−2/(k−1)) and Ok(N1−2/k). In contrast, k=3 admits an O(nlogn)-query nonadaptive algorithm at constant error, refuting a previous conjecture predicting an N1/3 lower bound. Against adaptive classical algorithms, the paper proves Ω(N1/4) queries for every k≥4.
The nonadaptive lower bounds encode a hidden sign in shifted random functions, requiring multiway query collisions; quadratic phases transfer the construction to odd cycles. Upper bounds use Cartesian-product sampling and cycle-dependent conditional second moments. The three-cycle algorithm instead uses a Fourier identity and nonadaptive Goldreich–Levin coefficient recovery. The adaptive lower bound uses random masks on hidden-subspace cosets and a transcript-coupling argument.
Matching constant-error bounds remain open for odd cycles and adaptive algorithms. The paper conjectures that the nonadaptive exponent is 1−1/⌊k/2⌋, determined by the cycle’s independence number; its current sampling estimator cannot attain this exponent for odd cycles.
The 2-Forrelation problem provides an optimal separation between classical and quantum query complexity and is also the problem used for separating BQP and PH relative to an oracle. A natural question is therefore to ask what are the minimal quantum resources needed to solve this problem. We show that 2-Forrelation can be solved using Instantaneous Quantum Polynomial-time (IQP) circuits, a restricted model of quantum computation in which all gates commute. Concretely, signed 2-Forrelation can be solved by a classical random choice between two one-query IQP circuits, while the absolute-value variant uses two independent executions of this randomized procedure. This answers a recent open question of Girish (STOC 2026) on the power of commuting quantum computations. For the Raz-Tal distribution, this randomization is unnecessary. We use this to show that there is an oracle O such that IQPO⊆PHO, strengthening the result of Raz and Tal (STOC 2019). It also yields an oracle separation between IQP and DQC1. We prove Fourier growth bounds for multi-query IQP circuits, including bounds in terms of the size of their accepting set. Our results suggest a possible route toward decision-based quantum advantage within the restricted IQP model. The key ingredient is an algebraic identity of the quadratic function Q(x)=∑i<jxixj that allows extracting inner-product phases within an IQP circuit.
We study the computational complexity of estimating the normalized trace 2−nTr[f(A)] for a log-local Hamiltonian A acting on n qubits. This problem arises naturally in the DQC1 model, yet its complexity is only understood for a limited class of functions f(x).
We show that if f(x) is a continuous function with approximate degree Ω(poly(n)), then estimating 2−nTr[f(A)] up to constant additive error is DQC1-complete, under a technical condition on the polynomial approximation error of f(x). This condition holds for a broad class of functions, including exponentials, trigonometric functions, logarithms, and inverse-type functions. We further prove that when A is sparse, the classical query complexity of this problem is exponential in the approximate degree. Together, these results identify the approximate degree as the key parameter governing the complexity of normalized trace estimation: it characterizes both the quantum complexity (via efficient DQC1 algorithms) and the classical hardness, yielding an exponential quantum-classical separation. Our proof develops a unified framework that cleanly combines circuit-to-Hamiltonian constructions, periodic Jacobi operators, and tools from polynomial approximation theory, including the Chebyshev equioscillation theorem.
The unitary synthesis problem (Aaronson-Kuperberg, CCC 2007) asks whether every n-qubit unitary U is computable by efficient quantum circuits relative to some classical oracle f=fU depending on U. Recently, Lombardi-Ma-Wright (STOC 2024) proved that Haar-random unitaries cannot be efficiently synthesized by algorithms that make 1 query (or poly(n) parallel queries) to an arbitrary classical oracle. In this work, we prove several results about the hardness (and easiness!) of variants of unitary synthesis. Our results include: (1) 1-query vs. 2-query unitary synthesis: we prove 1-query lower bounds for synthesizing random permutation unitaries P∣x⟩=∣π(x)⟩, as well as random alternating-basis phase unitaries F2⋅H⊗n⋅F1. This gives 1-query lower bounds for "explicit" families of unitaries that have efficient (even 2-query) synthesis algorithms. (2) Upper bound for complex phase unitaries: we also consider complex phase unitaries ∣x⟩↦αx∣x⟩, which have a clean 2-query synthesis algorithm with no obvious 1-query algorithm. In this case, we prove an upper bound: there are 1-query algorithms (relative to binary phase oracles) that constant-approximate these unitaries in diamond distance. In order to prove our lower bounds, we introduce and analyze two new cryptographic games: the oracle state search game and the oracle Choi state game. Compared to prior work, our framework is mathematically simple, more flexible in what it can prove, and more accurately captures the hardness of synthesizing unitaries that are not "fully random". Finally, we also use the search game to prove a new hardness-of-approximation result for quantum programs (synthesizing unitaries relative to quantum advice) for phase unitaries, giving a sharper separation between 1-query unitary synthesis and quantum programs.
The quantum query complexity of subgraph-containment problems, which ask whether a given subgraph H is present in an input graph G, has been the subject of considerable study. However, even for relatively simple subgraphs, such as paths and cycles, a complete understanding of their query complexities remains elusive. In this work, we consider several variants of path- and cycle-containment problems in the adjacency matrix model, where we search for paths or cycles of constant length k. We compare the settings where the graphs are directed or undirected, where the goal is to detect or find the existence of a path/cycle, and where the path/cycle we are looking for has length exactly k, or at most k. We also consider several promise versions of these problems, where we suppose that the input graph has a certain structure. We characterize the relative difficulty of these variants of the path/cycle-containment problems, by relating them to one another using randomized reductions, and grouping them into equivalence classes.
When we restrict our attention to path-containment problems, we get a dichotomy result. Some of the path-containment problems can be solved using a linear number of queries, and all the others are equivalent to one another (and additionally to several cycle-containment problems) under randomized reductions, up to constant overhead. For the latter equivalence class, we prove a novel quantum-walk-based algorithm that achieves query complexity O(n3/2−αk), where αk∈Θ(c−k) and c=3+17/2≈1.33, beating the previous best upper bound O(n3/2) on its query complexity. We also provide a conditional lower bound based on the graph-collision problem, which implies that this equivalence class does not admit linear-query quantum algorithms unless graph collision admits an O(n) query algorithm.
We study the query complexity of testing quantum juntas. Given an unknown n-qubit unitary or quantum channel, the goal is to decide whether it acts nontrivially on at most k qubits or is ε-far from every such operation. For unitaries, we consider the forward-only model, where the tester has access to U, but not to U† or controlled-U. We give tight bounds for both unitary and channel junta testing. For sufficiently large k, n≥2k, and a broad range of ε, both problems have query complexity Θ(k/(ε2logk)). Our upper bounds are achieved by simple nonadaptive testers using product inputs and single-qubit measurements. For junta channels, this closes the gap by Bao and Yao (COLT 23, TPAMI 2025) between an O(k) upper bound and a Ω(k) lower bound at constant ε, establishing the optimal Θ(k/logk) query complexity. At the heart of both bounds is a strong connection between quantum junta testing and classical support-size testing. For the upper bounds, we reduce quantum junta testing to a generalized support-size problem for distributions over random subsets, and develop a new tester with improved sample complexity. For the lower bounds, we proceed in the reverse direction, reducing classical support-size testing to quantum junta testing through a phase-masked hard ensemble and showing that forward quantum queries can be exactly classicalized on average. Together, these reductions identify support-size testing as the classical core of quantum junta testing and yield matching lower bounds. At constant ε, they also give a separation between Θ(k/logk) forward queries and O(k) queries with inverse access.
Motivated by limitations on the depth of near-term quantum devices, we study the depth-computation trade-off in the query model, where depth corresponds to the number of adaptive query rounds and the computation per layer corresponds to the number of parallel queries per round. We achieve the strongest known separation between quantum algorithms with r versus r−1 rounds of adaptivity. We do so by using the k-fold Forrelation problem introduced by Aaronson and Ambainis (SICOMP’18). For k=2r, this problem can be solved using an r round quantum algorithm with only one query per round, yet we show that any r−1 round quantum algorithm needs an exponential (in the number of qubits) number of parallel queries per round. Our results are proven following the Fourier analytic machinery developed in recent works on quantum-classical separations. The key new component in our result are bounds on the Fourier weights of quantum query algorithms with bounded number of rounds of adaptivity. These may be of independent interest as they distinguish the polynomials that arise from such algorithms from arbitrary bounded polynomials of the same degree.