pith. sign in

arxiv: 2604.15248 · v1 · submitted 2026-04-16 · 🪐 quant-ph · cs.CC

IQP circuits for 2-Forrelation

Quentin Buzet , Andr\'e Chailloux This is my paper

Pith reviewed 2026-05-10 11:41 UTC · model grok-4.3

classification 🪐 quant-ph cs.CC
keywords IQP circuits2-Forrelationquantum query complexityoracle separationcommuting gatesquantum advantageFourier growth
0
0 comments X

The pith

IQP circuits solve 2-Forrelation using two queries and classical post-processing.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes that the 2-Forrelation problem, which has an optimal separation between classical and quantum query complexity, can be solved inside the restricted model of Instantaneous Quantum Polynomial-time circuits where all gates commute. Two IQP circuits together with two quantum queries and efficient classical processing are sufficient for the standard version, while the signed variant requires only one circuit and one query. This resolves an open question on the power of commuting quantum computations and yields a stronger oracle separation between BPP raised to IQP and the polynomial hierarchy. The construction also opens a route to quantum advantage on decision problems that avoids the verification challenges of sampling-based demonstrations.

Core claim

2-Forrelation can be solved using IQP circuits, with two IQP circuits and two quantum queries plus classical post-processing sufficing for the standard problem and a single IQP circuit and query sufficing for the signed variant. The construction rests on an algebraic identity of the quadratic function Q(x) = sum_{i < j} x_i x_j that extracts inner-product phases inside an IQP circuit. The same identity also yields Fourier growth bounds for IQP circuits measured by the size of the accepting set.

What carries the argument

The algebraic identity of the quadratic function Q(x) = sum_{i < j} x_i x_j that extracts inner-product phases inside an IQP circuit.

If this is right

  • IQP circuits suffice for a problem with optimal classical-quantum query separation.
  • An oracle separation (BPP^IQP)^O notsubseteq PH^O follows directly.
  • IQP circuits become a tool for classically hard decision problems rather than only sampling tasks.
  • Fourier growth of IQP circuits is bounded by the size of their accepting sets.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Similar algebraic identities may reduce other query-complexity separations to the IQP model.
  • Decision-problem formulations could lower the experimental bar for demonstrating commuting-gate advantage compared with sampling.
  • The single-query signed case suggests even tighter resource bounds may exist for related correlation problems.

Load-bearing premise

The quadratic function Q(x) admits an algebraic identity that extracts inner-product phases inside an IQP circuit.

What would settle it

Explicit 2-Forrelation instances on which the output distribution of the proposed two-IQP-circuit procedure fails to match the correct correlation value with high probability would falsify the claim.

Figures

Figures reproduced from arXiv: 2604.15248 by Andr\'e Chailloux, Quentin Buzet.

Figure 1
Figure 1. Figure 1: BQP circuit for 2-Forrelation with one query to Of and one query to Og A direct calculation shows that this circuit outputs 0n with probability Φ2 (f, g). Aaronson and Ambainis [AA15] also observed that 2-Forrelation can be solved with a single query to a joint oracle Of,g|b⟩|x⟩ = ( f(x)|0⟩|x⟩ if b = 0, g(x)|1⟩|x⟩ if b = 1, with the following n + 1 qubit circuit below. |0⟩ H Of,g H |0 n ⟩ H⊗n H⊗n [PITH_FU… view at source ↗
Figure 2
Figure 2. Figure 2: BQP circuit for 2-Forrelation with a single query to Of,g This circuit measures 0 on the first qubit with probability 1 2 + 1 2Φ(f, g), giving a constant bias for the signed variant. Regarding the classical hardness of 2-Forrelation, Aaronson and Ambainis [AA15] proved a nearly tight classical lower bound of Ω( 2 n/2 log(n) ) randomized queries. Bansal and Sinha [BS21] extended the tight separation to k-Fo… view at source ↗
Figure 3
Figure 3. Figure 3: On the left: generic 1 2 -BQP Circuit. On the right: generic DQCk circuit. Even DQC1, with just one clean qubit, can solve problems that are believed to be classically intractable, such as estimating the normalized trace of a unitary [KL98] or computing Jones polynomials [SJ08]. Moreover, any DQCk circuit with k = O(log n) can be simulated by a 1 2 -BQP circuit [JM24], so 1 2 -BQP is the more powerful mode… view at source ↗
Figure 4
Figure 4. Figure 4: Generic IQP circuit IQP circuits are structurally much easier to implement than regular BQP circuits. The fact that all gates can be applied simultaneously implies that the total coherence time of the circuit can be much lower. Error correction is also simpler as the only gates we apply in the central layer are diagonal in the Z basis. Despite its restricted structure, IQP is believed to be strictly more p… view at source ↗
Figure 5
Figure 5. Figure 5: Complexity classes below BQP. The 2-Forrelation can be solved in 1 2 -BQP but not in DQC1. Is 2-Forrelation solvable in IQP and if not, can we prove Fourier growth bounds? On the one side, the oracles Of and Og (or the oracle Of,g) are diagonal in the computa￾tional basis so they can easily be incorporated in the diagonal operator D of an IQP circuit. However, if we look at known quantum circuits for 2-For… view at source ↗
Figure 6
Figure 6. Figure 6: IQP circuit on n + 1 qubits with a single call to Of,g and with a projection on the accepting space A circuit of this form has two degrees of freedom: the choice of D and the choice of F. We write D = P x∈{0,1}n+1 e iφx|x⟩⟨x| with each φx ∈ [0, 2π). A natural case where the accepting probability has a simple form is when • D = P b∈{0,1} P x∈{0,1}n ρb(x)|bx⟩⟨bx| for functions ρ0, ρ1 : {0, 1} n → {−1, 1}. • … view at source ↗
Figure 7
Figure 7. Figure 7: Single-query IQP circuit with n oracle qubits and w ancilla qubits. Theorem 6. Let p : {−1, 1} {0,1} n → [0, 1] be the acceptance probability of a single-query IQP circuit with acceptance set F ⊆ {0, 1} m. Then p is a multilinear polynomial of degree at most 2 and ∥pb∥1 ≤ p min{|F|, 2 n}. In particular, for every restriction ρ, L1,2(p|ρ ) ≤ p min{|F|, 2 n} and L1,ℓ(p|ρ ) = 0 for every ℓ > 2. Proof. Define … view at source ↗
Figure 8
Figure 8. Figure 8: d-query IQP circuit on the enlarged register. with n = 2, n ′ = 3, and y 1 (x) (resp. y 2 (x)) equal to x on the first two (resp. last two) coordinates and 1 elsewhere. Since all oracles are diagonal, they compose entrywise: setting z(x) = Qd t=1 y t (x), we have Oy 1(x) · · · Oy d(x) = Oz(x) . Therefore the d-query circuit is equivalent to a single-query circuit on the enlarged register with oracle string… view at source ↗
Figure 9
Figure 9. Figure 9: Equivalent single-query IQP circuit. Writing p for the acceptance probability of this single-query circuit (a function of the n ′ -bit oracle string), the acceptance probability of the d-query circuit is r(x) = p(z(x)). The study of d-query IQP circuits thus reduces to substitutions in the oracle variables of a single-query IQP circuit. Theorem 7. Let r : {−1, 1} {0,1} n → [0, 1] be the acceptance probabil… view at source ↗
read the original 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The manuscript shows that the 2-Forrelation problem (and its signed variant) can be solved using IQP circuits: two IQP circuits with two quantum queries plus efficient classical post-processing suffice in general, while a single IQP circuit and query suffice for the signed case. The construction rests on an algebraic identity for the quadratic function Q(x) = sum_{i<j} x_i x_j that extracts inner-product phases inside commuting diagonal gates. The work also proves Fourier growth bounds for IQP circuits in terms of accepting-set size and uses the result to strengthen the oracle separation (BPP^IQP)^O notsubseteq PH^O, answering an open question of Girish.

Significance. If the central constructions hold, the result is significant: it demonstrates that a restricted commuting model (IQP) can solve a classically hard decision problem that separates BQP from PH relative to an oracle, thereby providing a new route to quantum advantage that avoids the verification difficulties of sampling tasks. The strengthening of the Raz-Tal separation and the new Fourier bounds are of independent interest for the analysis of commuting quantum circuits.

major comments (2)
  1. [§3.2] §3.2, construction following the Q(x) identity: the manuscript must explicitly verify that the phase oracle U_f (presumably diagonal) can be folded into the quadratic-phase gates while preserving strict commutativity of all gates and using at most two queries total; the current sketch leaves open whether an auxiliary non-commuting operation is implicitly required to realize the inner-product phase e^{i theta <f,g>}.
  2. [Theorem 5.1] Theorem 5.1 (Fourier growth bound): the bound is stated in terms of accepting-set size, but the proof relies on the same quadratic identity; it is unclear whether the bound remains tight when the circuit is composed with the two oracle calls, and a counter-example or explicit calculation for small n would strengthen the claim.
minor comments (2)
  1. The abstract cites arXiv:2510.06385 but the bibliography entry is missing; add the full reference.
  2. Notation for the signed 2-Forrelation variant is introduced only in the text; a displayed definition would improve readability.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their careful reading, positive assessment, and constructive suggestions. We address each major comment below and will incorporate the requested clarifications and calculations into the revised manuscript.

read point-by-point responses

  1. Referee: [§3.2] §3.2, construction following the Q(x) identity: the manuscript must explicitly verify that the phase oracle U_f (presumably diagonal) can be folded into the quadratic-phase gates while preserving strict commutativity of all gates and using at most two queries total; the current sketch leaves open whether an auxiliary non-commuting operation is implicitly required to realize the inner-product phase e^{i theta <f,g>}.

    Authors: The phase oracle U_f is diagonal in the computational basis. The algebraic identity for Q(x) allows the inner-product phase e^{i θ ⟨f,g⟩} to be realized exactly as a linear combination of quadratic-phase diagonal gates on the input bits. All gates in the construction (including those implementing U_f and the quadratic phases) are therefore diagonal and commute. No auxiliary non-commuting operations are used. We will add a detailed, gate-by-gate decomposition and explicit commutativity verification in the revised Section 3.2, confirming that the circuit uses precisely two queries. revision: yes

  2. Referee: [Theorem 5.1] Theorem 5.1 (Fourier growth bound): the bound is stated in terms of accepting-set size, but the proof relies on the same quadratic identity; it is unclear whether the bound remains tight when the circuit is composed with the two oracle calls, and a counter-example or explicit calculation for small n would strengthen the claim.

    Authors: Theorem 5.1 gives a general bound on the Fourier growth of any IQP circuit in terms of accepting-set size; the proof technique applies directly because the oracle calls in our 2-Forrelation construction are also implemented by diagonal phase gates and therefore remain within the IQP model. The bound holds for the composed circuit. To strengthen the claim as suggested, we will include an explicit calculation for small n (n=3 and n=4) in the revised manuscript, verifying that the bound remains valid and reasonably tight after composition with the two oracle calls. revision: yes

Circularity Check

0 steps flagged

No significant circularity; new circuit constructions are independent of target claim

full rationale

The paper introduces explicit IQP circuit constructions for 2-Forrelation that rely on a standard algebraic identity for the quadratic function Q(x) and new Fourier growth bounds. These steps are derived from first principles within the manuscript rather than reducing to fitted parameters, self-definitions, or load-bearing self-citations. Prior results (Raz-Tal, Girish) are used only for context and oracle separation strengthening, not as unverified premises for the core claim. The derivation chain remains self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The paper relies on standard quantum circuit axioms and prior results on Forrelation and oracle separations. The central new element is the algebraic identity for the quadratic function, treated as a domain assumption rather than derived here.

axioms (2)
  • standard math Standard axioms of quantum computation, including the definition and properties of IQP circuits with commuting gates.
    Invoked throughout to define the computational model used for the constructions.
  • domain assumption The algebraic identity of the quadratic function Q(x) = sum_{i<j} x_i x_j enables extraction of inner-product phases in IQP circuits.
    Cited in the abstract as the key ingredient for the circuit constructions; not derived in the provided text.

pith-pipeline@v0.9.0 · 5590 in / 1497 out tokens · 41346 ms · 2026-05-10T11:41:31.396793+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

5 extracted references · 5 canonical work pages

  1. [1]

    Pseudo- random Generators from the Second Fourier Level and Applications to AC0 with Parity Gates

    [CHLT19] Eshan Chattopadhyay, Pooya Hatami, Shachar Lovett, and Avishay Tal. Pseudo- random Generators from the Second Fourier Level and Applications to AC0 with Parity Gates. In Avrim Blum, editor,10th Innovations in Theoretical Computer Science Conference (ITCS 2019), volume 124 ofLeibniz International Proceed- ings in Informatics (LIPIcs), pages 22:1–2...

    work page 2019

  2. [2]

    [DJ92] David Deutsch and Richard Jozsa

    Schloss Dagstuhl – Leibniz-Zentrum f¨ ur Informatik. [DJ92] David Deutsch and Richard Jozsa. Rapid solution of problems by quantum computation.Proceedings of the Royal Society of London. Series A: Mathematical and Physical Sciences, 439(1907):553–558,

    work page 1907

  3. [3]

    Fourier spectrum of noisy quantum algorithms

    [Gir25] Uma Girish. Fourier spectrum of noisy quantum algorithms.arXiv preprint arXiv:2510.06385,

    work page arXiv

  4. [4]

    [IRR+21] Siddharth Iyer, Anup Rao, Victor Reis, Thomas Rothvoss, and Amir Yehudayoff

    Accepted at STOC’26 (to appear). [IRR+21] Siddharth Iyer, Anup Rao, Victor Reis, Thomas Rothvoss, and Amir Yehudayoff. Tight bounds on the fourier growth of bounded functions on the hypercube.arXiv preprint arXiv:2107.06309,

    work page arXiv

  5. [5]

    The space just above one clean qubit

    26 [JM24] Dale Jacobs and Saeed Mehraban. The space just above one clean qubit.arXiv preprint arXiv:2410.08051,

    work page arXiv