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:2604.15248

IQP circuits for 2-Forrelation

Quentin Buzet, André Chailloux

quant-phcs.CCSubmitted Apr 16, 2026• Announced Apr 17, 2026• 0 citations• Revised Aug 24, 2026 (v2)
v1 · Apr 16, 2026v2 · Aug 24, 2026v3 · Oct 2, 2026
arXivHTMLPDF

Abstract

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, two $\mathsf{IQP}$ circuits with two quantum queries and efficient classical processing suffice. For the signed variant of 2-Forrelation, even a single $\mathsf{IQP}$ circuit and query suffices. This answers a recent open question of Girish (arXiv:2510.06385) on the power of commuting quantum computations. We use this to show that $(\mathsf{BPP}^{\mathsf{IQP}})^O \not\subseteq \mathsf{PH}^O$ relative to an oracle $O$, strengthening the result of Raz and Tal (STOC 2019). Our results show that $\mathsf{IQP}$ circuits can be used for classically hard decision problems, thus providing a new route for showing quantum advantage with $\mathsf{IQP}$ circuits, avoiding the verification difficulties associated with sampling tasks. We also prove Fourier growth bounds for $\mathsf{IQP}$ circuits in terms of the size of their accepting set. 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.

Comments
30 pages, revised and strengthened Fourier growth section

Related papers

$\mathsf{BQP} \subseteq \mathsf{IP}$ Does Not Relativize

Adam Bouland, Andrew Huang, Anand Natarajan +2 more

We construct an oracle relative to which $\mathsf{BQP} \not\subseteq \mathsf{IP}$, resolving a long-standing open question in quantum complexity theory. Together with recent work due to Aaronson et al., our work also gives the first oracle separation between $\mathsf{IP}$ and $\mathsf{MIP}$, answering a question dating back to Fortnow's thesis. Our separation is based on the Forrelation problem, where given Boolean functions $f$ and $g$, the goal is to determine if $f$ is correlated with the Fourier spectrum of $g$. While this task is solvable by a query-efficient quantum algorithm, we show that it admits no classical interactive protocol with polynomial communication and a polynomial-query verifier. Our proof is based on (i) a new structural result showing how to approximate Avg-Max circuits (which are well-known to capture the power of interactive proofs in the oracular setting) by convex functions with small first and second derivatives and (ii) a novel analysis establishing that the Forrelation distribution suggested by Aaronson and Ambainis fools such functions. Our results imply that any prover-efficient classical interactive protocol for $\mathsf{BQP}$ must rely on non-relativizing techniques. This might serve as a partial explanation for the lack of progress towards doubly-efficient, unconditionally sound classical verification of quantum computation.

quant-pharXiv:2609.25680•Sep 23, 2026•0 citations

Oracle Separations in the Fourier Hierarchy

Atul Mantri

The Fourier hierarchy $\mathrm{FH}_0\subseteq\mathrm{FH}_1\subseteq\mathrm{FH}_2\subseteq\cdots$, introduced by Shi (TCS 2005), measures a quantum computation by the number of Hadamard layers it uses. Between two layers the circuit may permute basis states and attach phases, but it may not create superposition; the layers are its only source of interference. The first level is exactly $\mathrm{BPP}$, while the second already solves Simon's problem and, through phase estimation, factors integers. Shi conjectured that every additional layer strictly increases computational power, and asked, as a first step, for oracle separations between consecutive levels. To our knowledge, the question was open at every level $k\ge2$. We prove that for every constant $k\ge2$ there is an oracle relative to which $\mathrm{FH}_k\subsetneq\mathrm{FH}_{k+1}$. The separating problem is built from Forrelation (Aaronson and Ambainis, STOC 2015): the level above solves it with a constant number of queries, whereas at level $k$ it stays hard even for circuits making exponentially many queries. This holds for both of the usual ways of giving a circuit access to an oracle, the phase oracle and the standard oracle, which writes its answer into a register. The two are not interchangeable: relative to an oracle, the standard oracle is strictly more powerful at the same number of layers. We also separate the union of all the levels from $\mathrm{BQP}$ relative to an oracle. The lower bounds rest on a structural property of the hierarchy: the number of Hadamard layers limits how adaptively a circuit can query its oracle. With a phase oracle, a circuit with $k$ layers is reproduced exactly by an algorithm making only $k-1$ rounds of parallel queries, which brings known lower bounds for such algorithms to bear. The standard oracle lets a circuit branch on earlier answers, and that case needs a separate argument.

quant-pharXiv:2609.11830•Sep 11, 2026•0 citations

The Quantumly Fast and the Classically Forrious

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

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.

arXiv:2602.07503•Feb 7, 2026•0 citations

Explicit Separations for One-Query Unitary Synthesis

Fangqi Dong, Alex Lombardi, Fermi Ma

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 = f_U$ 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\lvert x\rangle = \lvert π(x)\rangle$, as well as random alternating-basis phase unitaries $F_2 \cdot H^{\otimes n} \cdot F_1$. 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 $\lvert x\rangle\mapsto α_x \lvert x\rangle$, 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.

quant-pharXiv:2607.26478•Jul 30, 2026•0 citations

The Space Just Above One Clean Qubit

Dale Jacobs, Saeed Adel Mehraban

Consider the model of computation where we start with two halves of a $2n$-qubit maximally entangled state. We get to apply a universal quantum computation on one half, measure both halves at the end, and perform classical postprocessing. This model, which we call $\frac12$BQP, was defined in STOC 2017 [ABKM17] to capture the power of permutational computations on special input states. As observed in [ABKM17], this model can be viewed as a natural generalization of the one-clean-qubit model (DQC1) where we learn the content of a high entropy input state only after the computation is completed. An interesting open question is to characterize the power of this model, which seems to sit nontrivially between DQC1 and BQP. In this paper, we show that despite its limitations, this model can carry out many well-known quantum computations that are candidates for exponential speed-up over classical computations (and possibly DQC1). In particular, $\frac12$BQP can simulate Instantaneous Quantum Polynomial Time (IQP) and solve the Deutsch-Jozsa problem, Bernstein-Vazirani problem, Simon's problem, and period finding. As a consequence, $\frac12$BQP also solves Order Finding and Factoring outside of the oracle setting. Furthermore, $\frac12$BQP can solve Forrelation and the corresponding oracle problem given by Raz and Tal [RT22] to separate BQP and PH. We also study limitations of $\frac12$BQP and show that similarly to DQC1, $\frac12$BQP cannot distinguish between unitaries which are close in trace distance, then give an oracle separating $\frac12$BQP and BQP. Due to this limitation, $\frac12$BQP cannot obtain the quadratic speedup for unstructured search given by Grover's algorithm [Gro96]. We conjecture that $\frac12$BQP cannot solve $3$-Forrelation.

arXiv:2410.08051•Oct 10, 2024•0 citations

2-Fold Forrelation is in QAC$^0$

Francisca Vasconcelos

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$.

quant-pharXiv:2609.07060•Sep 8, 2026•0 citations
The 2-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 2-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, two IQP\mathsf{IQP}IQP circuits with two quantum queries and efficient classical processing suffice. For the signed variant of 2-Forrelation, even a single IQP\mathsf{IQP}IQP circuit and query suffices. This answers a recent open question of Girish (arXiv:2510.06385) on the power of commuting quantum computations. We use this to show that (BPPIQP)O⊈PHO(\mathsf{BPP}^{\mathsf{IQP}})^O \not\subseteq \mathsf{PH}^O(BPPIQP)O⊆PHO relative to an oracle OOO, strengthening the result of Raz and Tal (STOC 2019). Our results show that IQP\mathsf{IQP}IQP circuits can be used for classically hard decision problems, thus providing a new route for showing quantum advantage with IQP\mathsf{IQP}IQP circuits, avoiding the verification difficulties associated with sampling tasks. We also prove Fourier growth bounds for IQP\mathsf{IQP}IQP circuits in terms of the size of their accepting set. 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.
BQP⊆IP\mathsf{BQP} \subseteq \mathsf{IP}BQP⊆IP Does Not Relativize
We construct an oracle relative to which BQP⊈IP\mathsf{BQP} \not\subseteq \mathsf{IP}BQP⊆IP, resolving a long-standing open question in quantum complexity theory. Together with recent work due to Aaronson et al., our work also gives the first oracle separation between IP\mathsf{IP}IP and MIP\mathsf{MIP}MIP, answering a question dating back to Fortnow's thesis. Our separation is based on the Forrelation problem, where given Boolean functions fff and ggg, the goal is to determine if fff is correlated with the Fourier spectrum of ggg. While this task is solvable by a query-efficient quantum algorithm, we show that it admits no classical interactive protocol with polynomial communication and a polynomial-query verifier. Our proof is based on (i) a new structural result showing how to approximate Avg-Max circuits (which are well-known to capture the power of interactive proofs in the oracular setting) by convex functions with small first and second derivatives and (ii) a novel analysis establishing that the Forrelation distribution suggested by Aaronson and Ambainis fools such functions. Our results imply that any prover-efficient classical interactive protocol for BQP\mathsf{BQP}BQP must rely on non-relativizing techniques. This might serve as a partial explanation for the lack of progress towards doubly-efficient, unconditionally sound classical verification of quantum computation.
The Fourier hierarchy FH0⊆FH1⊆FH2⊆⋯\mathrm{FH}_0\subseteq\mathrm{FH}_1\subseteq\mathrm{FH}_2\subseteq\cdotsFH0​⊆FH1​⊆FH2​⊆⋯, introduced by Shi (TCS 2005), measures a quantum computation by the number of Hadamard layers it uses. Between two layers the circuit may permute basis states and attach phases, but it may not create superposition; the layers are its only source of interference. The first level is exactly BPP\mathrm{BPP}BPP, while the second already solves Simon's problem and, through phase estimation, factors integers. Shi conjectured that every additional layer strictly increases computational power, and asked, as a first step, for oracle separations between consecutive levels. To our knowledge, the question was open at every level k≥2k\ge2k≥2. We prove that for every constant k≥2k\ge2k≥2 there is an oracle relative to which FHk⊊FHk+1\mathrm{FH}_k\subsetneq\mathrm{FH}_{k+1}FHk​⊊FHk+1​. The separating problem is built from Forrelation (Aaronson and Ambainis, STOC 2015): the level above solves it with a constant number of queries, whereas at level kkk it stays hard even for circuits making exponentially many queries. This holds for both of the usual ways of giving a circuit access to an oracle, the phase oracle and the standard oracle, which writes its answer into a register. The two are not interchangeable: relative to an oracle, the standard oracle is strictly more powerful at the same number of layers. We also separate the union of all the levels from BQP\mathrm{BQP}BQP relative to an oracle. The lower bounds rest on a structural property of the hierarchy: the number of Hadamard layers limits how adaptively a circuit can query its oracle. With a phase oracle, a circuit with kkk layers is reproduced exactly by an algorithm making only k−1k-1k−1 rounds of parallel queries, which brings known lower bounds for such algorithms to bear. The standard oracle lets a circuit branch on earlier answers, and that case needs a separate argument.
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.
The unitary synthesis problem (Aaronson-Kuperberg, CCC 2007) asks whether every nnn-qubit unitary UUU is computable by efficient quantum circuits relative to some classical oracle f=fUf = f_Uf=fU​ depending on UUU. Recently, Lombardi-Ma-Wright (STOC 2024) proved that Haar-random unitaries cannot be efficiently synthesized by algorithms that make 1 query (or poly(n)(n)(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)⟩P\lvert x\rangle = \lvert π(x)\rangleP∣x⟩=∣π(x)⟩, as well as random alternating-basis phase unitaries F2⋅H⊗n⋅F1F_2 \cdot H^{\otimes n} \cdot F_1F2​⋅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⟩\lvert x\rangle\mapsto α_x \lvert x\rangle∣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.
Consider the model of computation where we start with two halves of a 2n2n2n-qubit maximally entangled state. We get to apply a universal quantum computation on one half, measure both halves at the end, and perform classical postprocessing. This model, which we call 12\frac1221​BQP, was defined in STOC 2017 [ABKM17] to capture the power of permutational computations on special input states. As observed in [ABKM17], this model can be viewed as a natural generalization of the one-clean-qubit model (DQC1) where we learn the content of a high entropy input state only after the computation is completed. An interesting open question is to characterize the power of this model, which seems to sit nontrivially between DQC1 and BQP. In this paper, we show that despite its limitations, this model can carry out many well-known quantum computations that are candidates for exponential speed-up over classical computations (and possibly DQC1). In particular, 12\frac1221​BQP can simulate Instantaneous Quantum Polynomial Time (IQP) and solve the Deutsch-Jozsa problem, Bernstein-Vazirani problem, Simon's problem, and period finding. As a consequence, 12\frac1221​BQP also solves Order Finding and Factoring outside of the oracle setting. Furthermore, 12\frac1221​BQP can solve Forrelation and the corresponding oracle problem given by Raz and Tal [RT22] to separate BQP and PH. We also study limitations of 12\frac1221​BQP and show that similarly to DQC1, 12\frac1221​BQP cannot distinguish between unitaries which are close in trace distance, then give an oracle separating 12\frac1221​BQP and BQP. Due to this limitation, 12\frac1221​BQP cannot obtain the quadratic speedup for unstructured search given by Grover's algorithm [Gro96]. We conjecture that 12\frac1221​BQP cannot solve 333-Forrelation.
2-Fold Forrelation is in QAC0^00
We show that 2-fold Forrelation with inverse-polylogarithmic promise gap can be solved, with bounded error, by polynomial-size QAC0^00 circuits. Unlike the standard oracle-based Forrelation algorithm, our circuits receive the input explicitly, in the same form as the AC0^00 circuits against which Forrelation is known to be hard. At constant gap, this yields a natural promise-problem separation between QAC0^00 and AC0^00.