Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2602.07503

The Quantumly Fast and the Classically Forrious

Clément L. Canonne, Kenny Chen, Julián Mestre

Published Feb 7, 2026• 1 citation
arXivHTMLPDF

Abstract

We study the extremal Forrelation problem, where, provided with oracle access to Boolean functions $f$ and $g$ promised to satisfy either $\operatorname{forr}(f,g)=1$ or $\operatorname{forr}(f,g)=-1$, one must determine (with high probability) which of the two cases holds while performing as few oracle queries as possible. It is well known that this problem can be solved with one quantum query; yet, Girish and Servedio (ITCS 2026) recently showed this problem requires $\widetildeΩ(2^{n/4})$ classical queries, and conjectured the optimal bound to be $\widetildeΘ(2^{n/2})$. By generalizing their construction, we build on their result and prove a non-adaptive lower bound of $Ω(2^{(1/2- o(1))n})$, which matches the conjectured lower bound up to a vanishing constant in the exponent.

DOI
10.48550/arxiv.2602.07503

Related papers

Forrelation: A Problem That Optimally Separates Quantum from Classical Computing

Scott Aaronson, Andris Ambainis

We achieve essentially the largest possible separation between quantum and classical query complexities. We do so using a property-testing problem called Forrelation, where one needs to decide whether one Boolean function is highly correlated with the Fourier transform of a second function. This problem can be solved using 1 quantum query, yet we show that any randomized algorithm needs $\Omega(\sqrt{N}/\log N)$ queries (improving an $\Omega(N^{1/4})$ lower bound of Aaronson). Conversely, we show that this 1 versus $\widetilde{\Omega}(\sqrt{N})$ separation is optimal: indeed, any $t$-query quantum algorithm whatsoever can be simulated by an $O(N^{1-1/2t})$-query randomized algorithm. Thus, resolving an open question of Buhrman et al. [ SIAM J. Comput., 37 (2008), pp. 1387--1400] from 2002, there is no partial Boolean function whose quantum query complexity is constant and whose randomized query complexity is linear. We conjecture that a natural generalization of Forrelation achieves the optimal $t$ versus $\Omega(N^{1-1/2t})$ separation for all $t$. As a bonus, we show that this generalization is ${BQP}$-complete. This yields what is arguably the simplest ${BQP}$-complete problem yet known and gives a second sense in which Forrelation “captures the maximum power of quantum computation.”

arXiv:1411.5729•SIAM Journal on Computing•Jan 1, 2018•90 citations

Classical algorithms for Forrelation

Sergey B. Bravyi, David Gosset, Daniel Grier +1 more

We study the forrelation problem: given a pair of $n$-bit Boolean functions $f$ and $g$, estimate the correlation between $f$ and the Fourier transform of $g$. This problem is known to provide the largest possible quantum speedup in terms of its query complexity and achieves the landmark oracle separation between the complexity class BQP and the Polynomial Hierarchy. Our first result is a classical algorithm for the forrelation problem which has runtime $O(n2^{n/2})$. This is a nearly quadratic improvement over the best previously known algorithm. Secondly, we show that quantum query algorithm that makes $t$ queries to an $n$-bit oracle can be simulated by classical query algorithm making only $O(2^{n(1-1/2t)})$ queries. This fixes a gap in the literature arising from a recently discovered critical error in a previous proof; it matches recently established lower bounds (up to $poly(n,t))$ factors) and thus characterizes the maximal separation in query complexity between quantum and classical algorithms. Finally, we introduce a graph-based forrelation problem where $n$ binary variables live at vertices of some fixed graph and the functions $f,g$ are products of terms describing interactions between nearest-neighbor variables. We show that the graph-based forrelation problem can be solved on a classical computer in time $O(n)$ for any bipartite graph, any planar graph, or, more generally, any graph which can be partitioned into two subgraphs of constant treewidth. The graph-based forrelation is simply related to the variational energy achieved by the Quantum Approximate Optimization Algorithm (QAOA) with two entangling layers and Ising-type cost functions. By exploiting the connection between QAOA and the graph-based forrelation we were able to simulate the recently proposed Recursive QAOA with two entangling layers and $225$ qubits on a laptop computer.

arXiv:2102.06963•Feb 13, 2021•22 citations

Exponential quantum-classical query separations for cyclic Forrelation

Yuxin Zhang, Changpeng Shao

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.

quant-pharXiv:2610.41694•Nov 2, 2026•0 citations

IQP circuits for 2-Forrelation

Quentin Buzet, André Chailloux

The $2$-Forrelation problem provides an optimal separation between classical and quantum query complexity and is also the problem used for separating $\mathsf{BQP}$ and $\mathsf{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 ($\mathsf{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 $\mathsf{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 $\mathsf{IQP}^O \not\subseteq \mathsf{PH}^O$, strengthening the result of Raz and Tal (STOC 2019). It also yields an oracle separation between $\mathsf{IQP}$ and $\mathsf{DQC}_1$. We prove Fourier growth bounds for multi-query $\mathsf{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 $\mathsf{IQP}$ model. The key ingredient is an algebraic identity of the quadratic function $Q(x) = \sum_{i < j} x_ix_j$ that allows extracting inner-product phases within an $\mathsf{IQP}$ circuit.

quant-pharXiv:2604.15248•Apr 17, 2026•4 citations

Forrelation Is Extremally Hard

Uma Girish, Rocco A. Servedio

The Forrelation problem is a central problem that demonstrates an exponential separation between quantum and classical capabilities. In this problem, given query access to $n$-bit Boolean functions $f$ and $g$, the goal is to estimate the Forrelation function $\mathrm{forr}(f,g)$, which measures the correlation between $g$ and the Fourier transform of $f$. In this work we provide a new linear algebraic perspective on the Forrelation problem, as opposed to prior analytic approaches. We establish a connection between the Forrelation problem and bent Boolean functions and through this connection, analyze an extremal version of the Forrelation problem where the goal is to distinguish between extremal instances of Forrelation, namely $(f,g)$ with $\mathrm{forr}(f,g)=1$ and $\mathrm{forr}(f,g)=-1$. We show that this problem can be solved with one quantum query and success probability one, yet requires $\tildeΩ\left(2^{n/4}\right)$ classical randomized queries, even for algorithms with a one-third failure probability, highlighting the remarkable power of one exact quantum query. We also study a restricted variant of this problem where the inputs $f,g$ are computable by small classical circuits and show classical hardness under cryptographic assumptions.

arXiv:2508.02514•Leibniz international proceedings in informatics•Aug 4, 2025•5 citations

Optimal query complexity for fractional quantum evolution

Anthony Yuezhang Liu, Adam Wesołowski, Jayne Thompson +2 more

Given oracle access to an unknown unitary $U=e^{iH}$ , the fractional query problem asks how many queries are required to implement a noninteger power $U^t=e^{itH}$, $0<t<1$, when the spectrum is separated from the branch cut by a gap $δ$. Quantum singular value transformation gives an upper bound of $O\!\left(\frac{1}δ\log\frac{1}{\varepsilon}\right)$ queries for approximation error $\varepsilon$. We prove a matching lower bound for arbitrary query algorithms. Our argument reduces any $N$-query circuit to the approximation of $e^{itθ}$ by a trigonometric polynomial with degree bounded by $O(N)$, together with Remez inequality. This allows us to establish the lower bound of $Ω_τ\!\left(\frac{1}δ\log\frac{1}{\varepsilon}\right)$. Consequently, the optimal query complexity for fractional query problem is $Θ_τ\!\left(\frac{1}δ\log\frac{1}{\varepsilon}\right)$, showing that the known QSVT construction is asymptotically optimal. We also give an alternative lower bound proof based on constructing a linear functional that annihilates the approximant space, yielding a $Ω_τ\!\left(\log\frac{1}{\varepsilon}\right)$ bound uniform to $δ$.

quant-pharXiv:2610.01940•Oct 2, 2026•0 citations
We study the extremal Forrelation problem, where, provided with oracle access to Boolean functions fff and ggg promised to satisfy either forr⁡(f,g)=1\operatorname{forr}(f,g)=1forr(f,g)=1 or forr⁡(f,g)=−1\operatorname{forr}(f,g)=-1forr(f,g)=−1, one must determine (with high probability) which of the two cases holds while performing as few oracle queries as possible. It is well known that this problem can be solved with one quantum query; yet, Girish and Servedio (ITCS 2026) recently showed this problem requires Ω~(2n/4)\widetildeΩ(2^{n/4})Ω(2n/4) classical queries, and conjectured the optimal bound to be Θ~(2n/2)\widetildeΘ(2^{n/2})Θ(2n/2). By generalizing their construction, we build on their result and prove a non-adaptive lower bound of Ω(2(1/2−o(1))n)Ω(2^{(1/2- o(1))n})Ω(2(1/2−o(1))n), which matches the conjectured lower bound up to a vanishing constant in the exponent.
We achieve essentially the largest possible separation between quantum and classical query complexities. We do so using a property-testing problem called Forrelation, where one needs to decide whether one Boolean function is highly correlated with the Fourier transform of a second function. This problem can be solved using 1 quantum query, yet we show that any randomized algorithm needs Ω(N/log⁡N)\Omega(\sqrt{N}/\log N)Ω(N​/logN) queries (improving an Ω(N1/4)\Omega(N^{1/4})Ω(N1/4) lower bound of Aaronson). Conversely, we show that this 1 versus Ω~(N)\widetilde{\Omega}(\sqrt{N})Ω(N​) separation is optimal: indeed, any ttt-query quantum algorithm whatsoever can be simulated by an O(N1−1/2t)O(N^{1-1/2t})O(N1−1/2t)-query randomized algorithm. Thus, resolving an open question of Buhrman et al. [ SIAM J. Comput., 37 (2008), pp. 1387--1400] from 2002, there is no partial Boolean function whose quantum query complexity is constant and whose randomized query complexity is linear. We conjecture that a natural generalization of Forrelation achieves the optimal ttt versus Ω(N1−1/2t)\Omega(N^{1-1/2t})Ω(N1−1/2t) separation for all ttt. As a bonus, we show that this generalization is BQP{BQP}BQP-complete. This yields what is arguably the simplest BQP{BQP}BQP-complete problem yet known and gives a second sense in which Forrelation “captures the maximum power of quantum computation.”
We study the forrelation problem: given a pair of nnn-bit Boolean functions fff and ggg, estimate the correlation between fff and the Fourier transform of ggg. This problem is known to provide the largest possible quantum speedup in terms of its query complexity and achieves the landmark oracle separation between the complexity class BQP and the Polynomial Hierarchy. Our first result is a classical algorithm for the forrelation problem which has runtime O(n2n/2)O(n2^{n/2})O(n2n/2). This is a nearly quadratic improvement over the best previously known algorithm. Secondly, we show that quantum query algorithm that makes ttt queries to an nnn-bit oracle can be simulated by classical query algorithm making only O(2n(1−1/2t))O(2^{n(1-1/2t)})O(2n(1−1/2t)) queries. This fixes a gap in the literature arising from a recently discovered critical error in a previous proof; it matches recently established lower bounds (up to poly(n,t))poly(n,t))poly(n,t)) factors) and thus characterizes the maximal separation in query complexity between quantum and classical algorithms. Finally, we introduce a graph-based forrelation problem where nnn binary variables live at vertices of some fixed graph and the functions f,gf,gf,g are products of terms describing interactions between nearest-neighbor variables. We show that the graph-based forrelation problem can be solved on a classical computer in time O(n)O(n)O(n) for any bipartite graph, any planar graph, or, more generally, any graph which can be partitioned into two subgraphs of constant treewidth. The graph-based forrelation is simply related to the variational energy achieved by the Quantum Approximate Optimization Algorithm (QAOA) with two entangling layers and Ising-type cost functions. By exploiting the connection between QAOA and the graph-based forrelation we were able to simulate the recently proposed Recursive QAOA with two entangling layers and 225225225 qubits on a laptop computer.
We study the randomized classical query complexity of cyclic Forrelation, a cyclic analogue of kkk-Forrelation [AA15, STOC'15; BS21, STOC'21]. Given kkk Boolean functions f1,…,fk:F2n→{−1,1}f_1,\ldots,f_k:\mathbb{F}_2^n\to\{-1,1\}f1​,…,fk​:F2n​→{−1,1}, the goal is to estimate Tk=N−1Tr⁡(Df1H⊗n⋯DfkH⊗n),T_k=N^{-1}\operatorname{Tr}(D_{f_1}H^{\otimes n}\cdots D_{f_k}H^{\otimes n}),Tk​=N−1Tr(Df1​​H⊗n⋯Dfk​​H⊗n), where Dfi=diag⁡(fi(x):x∈F2n)D_{f_i}=\operatorname{diag}(f_i(x):x\in\mathbb{F}_2^n)Dfi​​=diag(fi​(x):x∈F2n​), HHH is the Hadamard gate, and N=2nN=2^nN=2n. This normalized-trace problem can be solved with kkk 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)\widetildeΩ(N^{1-2/k})Ω(N1−2/k). We establish a nearly complete characterization of the nonadaptive classical query complexity of cyclic Forrelation. For even k≥4k\ge 4k≥4, we prove a tight bound of Θk(N1−2/k)Θ_k(N^{1-2/k})Θk​(N1−2/k) for constant additive error. For odd k≥5k\ge 5k≥5, we obtain a lower bound of Ωk(N1−2/(k−1))Ω_k(N^{1-2/(k-1)})Ωk​(N1−2/(k−1)) and an upper bound of Ok(N1−2/k)O_k(N^{1-2/k})Ok​(N1−2/k). Surprisingly, k=3k=3k=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 kkk-cycle, leading to the exponent 1−1/⌊k/2⌋1-1/\lfloor k/2\rfloor1−1/⌊k/2⌋, rather than the previously conjectured 1−2/k1-2/k1−2/k, which was motivated by a Fourier-growth heuristic. Finally, allowing adaptivity, we prove a lower bound of Ω(N1/4)Ω(N^{1/4})Ω(N1/4) for every k≥4k\ge4k≥4. Although formally close to kkk-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 222-Forrelation problem provides an optimal separation between classical and quantum query complexity and is also the problem used for separating BQP\mathsf{BQP}BQP and PH\mathsf{PH}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 222-Forrelation can be solved using Instantaneous Quantum Polynomial-time (IQP\mathsf{IQP}IQP) circuits, a restricted model of quantum computation in which all gates commute. Concretely, signed 222-Forrelation can be solved by a classical random choice between two one-query IQP\mathsf{IQP}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 OOO such that IQPO⊈PHO\mathsf{IQP}^O \not\subseteq \mathsf{PH}^OIQPO⊆PHO, strengthening the result of Raz and Tal (STOC 2019). It also yields an oracle separation between IQP\mathsf{IQP}IQP and DQC1\mathsf{DQC}_1DQC1​. We prove Fourier growth bounds for multi-query IQP\mathsf{IQP}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\mathsf{IQP}IQP model. The key ingredient is an algebraic identity of the quadratic function Q(x)=∑i<jxixjQ(x) = \sum_{i < j} x_ix_jQ(x)=∑i<j​xi​xj​ that allows extracting inner-product phases within an IQP\mathsf{IQP}IQP circuit.
The Forrelation problem is a central problem that demonstrates an exponential separation between quantum and classical capabilities. In this problem, given query access to nnn-bit Boolean functions fff and ggg, the goal is to estimate the Forrelation function forr(f,g)\mathrm{forr}(f,g)forr(f,g), which measures the correlation between ggg and the Fourier transform of fff. In this work we provide a new linear algebraic perspective on the Forrelation problem, as opposed to prior analytic approaches. We establish a connection between the Forrelation problem and bent Boolean functions and through this connection, analyze an extremal version of the Forrelation problem where the goal is to distinguish between extremal instances of Forrelation, namely (f,g)(f,g)(f,g) with forr(f,g)=1\mathrm{forr}(f,g)=1forr(f,g)=1 and forr(f,g)=−1\mathrm{forr}(f,g)=-1forr(f,g)=−1. We show that this problem can be solved with one quantum query and success probability one, yet requires Ω~(2n/4)\tildeΩ\left(2^{n/4}\right)Ω~(2n/4) classical randomized queries, even for algorithms with a one-third failure probability, highlighting the remarkable power of one exact quantum query. We also study a restricted variant of this problem where the inputs f,gf,gf,g are computable by small classical circuits and show classical hardness under cryptographic assumptions.
Given oracle access to an unknown unitary U=eiHU=e^{iH}U=eiH , the fractional query problem asks how many queries are required to implement a noninteger power Ut=eitHU^t=e^{itH}Ut=eitH, 0<t<10<t<10<t<1, when the spectrum is separated from the branch cut by a gap δδδ. Quantum singular value transformation gives an upper bound of O ⁣(1δlog⁡1ε)O\!\left(\frac{1}δ\log\frac{1}{\varepsilon}\right)O(δ1​logε1​) queries for approximation error ε\varepsilonε. We prove a matching lower bound for arbitrary query algorithms. Our argument reduces any NNN-query circuit to the approximation of eitθe^{itθ}eitθ by a trigonometric polynomial with degree bounded by O(N)O(N)O(N), together with Remez inequality. This allows us to establish the lower bound of Ωτ ⁣(1δlog⁡1ε)Ω_τ\!\left(\frac{1}δ\log\frac{1}{\varepsilon}\right)Ωτ​(δ1​logε1​). Consequently, the optimal query complexity for fractional query problem is Θτ ⁣(1δlog⁡1ε)Θ_τ\!\left(\frac{1}δ\log\frac{1}{\varepsilon}\right)Θτ​(δ1​logε1​), showing that the known QSVT construction is asymptotically optimal. We also give an alternative lower bound proof based on constructing a linear functional that annihilates the approximant space, yielding a Ωτ ⁣(log⁡1ε)Ω_τ\!\left(\log\frac{1}{\varepsilon}\right)Ωτ​(logε1​) bound uniform to δδδ.