IQP circuits for 2-Forrelation

arXiv:2604.15248 · quant-ph, cs.CC · Submitted 2026-04-16 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: Quantum Radio. Generated commentary on the latest quantum physics and condensed matter papers.

Kai: I'm Kai, and with me are Mira and Lev, guest researcher.

Mira: Today's paper: "IQP circuits for 2-Forrelation".

Kai: The 2-Forrelation problem, which provides an optimal separation between classical and quantum query complexity, can be solved using Instantaneous Quantum Polynomial-time (IQP) circuits.

Mira: First, who's behind it and why it matters.

Title and authors: Kai: So we're looking at "IQP circuits for two-Forrelation" by Buzet and Chailloux, and the title itself suggests they're digging into what minimal quantum resources are actually required to solve this problem <ref:2604.15248#pg0,IQP circuits for 2-Forrelation>. It points toward a specific computational model that is more restricted than what we usually think of when discussing full quantum computation.

Mira: I agree with Kai; the authors are trying to define the boundaries of what IQP circuits can handle, which is a very specific area in complexity theory right now. It moves us away from just asking if something is hard for BQP and instead asks what happens when you restrict the gate structure significantly, like having all gates commute.

Lev: From an error correction standpoint, if we were to run this on real hardware, we'd have to be really careful about the decoherence because IQP circuits rely on this commutativity property that might be tricky to maintain in a physical system.

Kai: Exactly, and the abstract tells us they show that two-Forrelation can actually be solved using just two quantum queries within an IQP circuit, or even just one query for the signed variant <ref:2604.15248#pg0,show that 2-Forrelation can>. That's a big statement about how powerful this restricted model is compared to what we usually consider standard quantum algorithms.

Mira: It really highlights the distinction between general BQP and this more constrained model because it shows that two-Forrelation sits within IQP, suggesting that the power needed for certain problems isn't necessarily tied to the full expressive power of BQP <ref:2604.15248#pg0>.

Lev: That separation is interesting because it suggests we can find quantum advantage demonstrations in areas where verification is tough without needing the massive resources associated with full BQP computations.

Kai: And this leads us into what the paper actually describes about how they construct these circuits and what that means for practical computation.

The paper's summary: Kai: The core of "IQP circuits for two-Forrelation" is showing that you can solve the two-Forrelation problem using an IQP circuit, which is a model where all gates commute because they are diagonal in the computational basis <ref:2604.15248#pg0,IQP circuits for 2-Forrelation>. They show that this model requires just two quantum queries for the general version and even just one query for the signed variant.

Mira: That finding is significant because it demonstrates that IQP circuits are powerful enough to tackle problems that are classically hard, which is a new way to look at showing quantum advantage without having to deal with all the verification hurdles associated with sampling tasks.

Lev: If this holds up on real hardware, we'd be looking at algorithms where the complexity isn't just about the number of queries but how efficiently those queries can be structured within this commutative framework.

Kai: The authors build their solution using a specific quadratic function Q(x) that satisfies an identity involving sums and products modulo two which they use to construct diagonal operators D and an accepting set F to get the desired acceptance probability <ref:2604.15248#pg0>.

Mira: That construction is clever because it uses this specific algebraic property of Q(x) to satisfy the bentness condition, which is what allows them to hit those exact acceptance probabilities like one/two + sqrt one/two (f, g) for odd n <ref:2604.15248#pg1>.

Lev: The reliance on these specific algebraic identities means that the structure of the problem—the functions f and g—is heavily constrained by the properties of Q(x) they chose to use.

Kai: They also handle different input sizes by using a "simple one-bit padding" argument for even n, which reduces it back to an odd case on a larger input size, giving them the final acceptance probability of one/two + one/four (f, g) for those cases.

The paper's improvements: Kai: One of the key improvements discussed in this paper is how they extend the result to the absolute value variant of two-Forrelation, where they show that two independent runs of an IQP computation can achieve an acceptance probability based on two(f, g) for odd n and two(f, g) for even n <ref:2604.15248#pg0>.

Mira: That extension using two independent runs is interesting because it shows how we can leverage the structure of the problem to get better bounds, specifically moving from a single query dependence to a squared dependence in some cases.

Lev: If we think about running this on hardware, having two independent runs might mean running slightly different circuits or measurements simultaneously, which could be useful for error mitigation strategies.

Kai: The paper also establishes that there exists an oracle O such that (BPPIQP) O is not contained in PHO, which strengthens the earlier result from Raz and Tal by showing a separation between these two complexity classes.

Mira: That oracle separation is important because it formally proves there's a problem solvable efficiently in this restricted quantum model that can't be solved by any algorithm in the Polynomial Hierarchy, which is a significant theoretical statement about computational limits.

Lev: Proving that BPPIQP O is outside PHO gives us a concrete complexity boundary; it tells us exactly where the power of this restricted quantum computation stops relative to classical complexity classes.

Kai: Furthermore, they establish Fourier growth bounds, showing that the level-two Fourier growth is bounded by O(sqrt dN), which means for three-Forrelation, you can't solve it with constant advantage if the number of queries d is smaller than N one/three <ref:2604.15248#pg2>.

Conclusion: Kai: To wrap up the paper "IQP circuits for two-Forrelation," we see that these IQP computations are powerful enough to solve problems that separate classical and quantum query complexity, which is a new route for showing quantum advantage without needing complex verification tasks <ref:2604.15248#pg0,a new route for showing quantum advantage>.

Mira: Indeed, the work shows that this restricted model captures the necessary quantum power needed for two-Forrelation, proving that this model is strictly outside of PHO <ref:2604.15248#pg0>. It gives us concrete bounds on query complexity and Fourier growth, which helps us understand exactly how much computational structure we need to tackle these problems.

Lev: From my perspective in error correction, the results give us a target: we know the computational landscape for these specific quantum models, which is crucial when designing fault-tolerant systems that might operate under such constraints.

Kai: So while IQP circuits are more restricted than full BQP, this paper shows they are not entirely out of reach for solving certain hard decision problems, providing a new way to frame the pursuit of quantum advantage.

Mira: It really solidifies the idea that by focusing on problems like two-Forrelation, we can find theoretical avenues to demonstrate quantum advantage that bypass some of those verification bottlenecks we usually run into with sampling tasks <ref:2604.15248#pg0>.

Inria de Paris

quant-ph, cs.CC

Submitted: 2026-04-16

Updated: 2026-10-02

Comments: 30 pages, revised and strengthened Fourier growth section

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 91/100

The gist: The 2-Forrelation problem, which provides an optimal separation between classical and quantum query complexity, can be solved using Instantaneous Quantum Polynomial-time (IQP) circuits.

Key concepts

Instantaneous Quantum Polynomial-time (IQP): IQP circuits are a computational model where a quantum circuit can make only one query to an oracle. The paper shows that this restricted model is sufficient to solve 2-Forrelation, meaning it can compute the optimal separation between classical and quantum query complexity.
Oracle Of,g: This refers to a specific type of function or problem instance that a quantum circuit queries. The paper utilizes the fact that this oracle is diagonal in the computational basis, allowing it to be easily incorporated into the diagonal layer of an IQP computation.
Bentness Condition: The bentness condition is a mathematical property applied to a specific function called sigma. It ensures that the imaginary part of sigma evaluated at b stays within the range (-1, 1). This property is crucial for constructing diagonal operators that lead to the desired acceptance probability in the proof.
Fourier Growth Bounds: These bounds describe how quickly certain functions (related to quantum circuits) grow as their input size increases. The paper derives bounds like L1,2(p|ρ) = O(√N), which are used to show that 3-Forrelation cannot be solved with constant advantage by IQP circuits making few queries.

Terminology

BQP — 50× in this paper · explained in 2 episodes
Query Complexity — 9× in this paper · explained in 2 episodes
Verification — 8× in this paper · explained in 2 episodes
Quantum Circuits — 4× in this paper · explained in 2 episodes
BQP-complete — 2× in this paper · explained in 2 episodes
Core — 2× in this paper · explained in 2 episodes
Instantaneous Quantum Polynomial-time — 2× in this paper
Adaptation — 1× in this paper · explained in 1 episode
Adaptivity — 1× in this paper · explained in 1 episode
Ancilla Qubits — 1× in this paper · explained in 1 episode
Trace — 1× in this paper · explained in 2 episodes

Summary

The 2-Forrelation problem, which provides an optimal separation between classical and quantum query complexity, can be solved using Instantaneous Quantum Polynomial-time (IQP) circuits. This finding demonstrates that IQP circuits are powerful enough to solve classically hard decision problems, offering a new route for showing quantum advantage while avoiding the verification difficulties associated with sampling tasks.

The Core Result

The central contribution is showing that 2-Forrelation can be solved with an IQP computation, which is technically captured by the class BPPIQP. Specifically, Theorem 1 states that there exists an IQP computation making a single quantum query to Of,g that accepts with probability:

Pacc = 1/2 + √1/2Φ(f, g) if n odd

and

/2 + 1/4Φ(f, g) if n even.

Construction and Key Tools

The construction relies on the fact that the oracle Of,g is diagonal in the computational basis, allowing it to be absorbed into the diagonal layer of an IQP circuit. The key ingredient is a quadratic function Q(x) = Pi x ixj, which satisfies the identity:

Q(x) + Q(y) + Q(x + y) = x · y + xy (mod 2).

To achieve the desired acceptance probability, the paper constructs diagonal operators D and an accepting set F. For odd n, it uses functions ρ0 = ρ1 = (−1)Q and a specific function σ that satisfies a bentness condition:

Im(σb) ⊆ (−1, 1) (the bentness condition)

This leads to the acceptance probability:

/2 + √1/2Φodd(f, g), where Φodd(f, g) is the quantity restricted to summing over pairs (x, y) with x + y odd.

Handling Different Cases and Variants

The construction is adapted for different cases of n:

For even n, a simple one-bit padding argument extends the construction from odd n to solve the problem by reducing it to an odd case on a larger input size (n+1). This yields an acceptance probability of 1/2 + 1/4Φ(f, g).
For the absolute value variant of 2-Forrelation, Theorem 2 shows that two independent runs of the IQP computation can be used to achieve an acceptance probability:

/2 + 1/4Φ 2(f, g) if n odd

and

/2 + 1/8Φ 2(f, g) if n even.

Oracle Separation and Complexity Bounds

The result extends the oracle separation between BQP and PH. Theorem 3 shows that there exists an IQP computation solving the m-fold Raz–Tal distinguishing problem with constant advantage for m = Θ(n4). This implies that there is an oracle O such that BPPIQPO ≠ PHO. Furthermore, Fourier growth bounds are established:

L1,2(pρ) = O(√N)

This implies that any constant-advantage IQP circuit for 2-Forrelation must have an accepting set of size F = Ω(N).

Fourier Growth Analysis

The paper derives explicit Fourier growth bounds for d-query IQP circuits. Theorem 6 shows that the level-2 Fourier growth is bounded by:

L1,2(pρ) = O(√dN)

This bound implies that 3-Forrelation cannot be solved with constant advantage by IQP circuits making d = o(N(1/3)) queries. This recovers the separation of 3-Forrelation from IQP directly at the level of Fourier growth.

Query Dependence

Theorem 2 provides an upper bound on the number of queries needed for 2-Forrelation:

/2 + 1/4Φ 2(f, g) if n odd

and

/2 + 1/8Φ 2(f, g) if n even.

Conclusion

The work concludes that the quantum power needed to solve 2-Forrelation is already available in IQP computations, a model significantly more restricted than BQP. The results establish that IQP circuits are strictly outside the reach of the polynomial hierarchy (BPPIQPO ≠ PHO) and provide tight bounds on their query complexity and Fourier growth. It also suggests that while IQP circuits are proposed for near-term quantum advantage via sampling problems, 2-Forrelation's decision nature bypasses verification bottlenecks.

How it works

Improvements for AI systems

As a fastidious researcher, I have analyzed this paper, IQP circuits for 2-Forrelation by Buzet and Chailloux. This work establishes that problems like 2-Forrelation (which separates quantum and classical query complexity optimally) can be solved using Instantaneous Quantum Polynomial-time (IQP) circuits.

The core improvement suggested by this research is not about building a specific AI model architecture, but rather about establishing a new theoretical framework for understanding the limits of quantum computation relative to restricted models, specifically IQP circuits.

Here are the specific improvements and what the improved system can do:

The primary improvement suggested by this paper is the development of a new computational model that bridges classical complexity (BPP) and full quantum computation (BQP), providing a more accessible theoretical path for demonstrating quantum advantage without relying on complex verification tasks.

Improvement: Implementation of Quantum Advantage via IQP Circuits.
Capability: The improved AI system can solve decision problems (like 2-Forrelation) that are classically hard using only a single query to a restricted quantum oracle, followed by efficient classical post-processing (the class BPPIQP).
Specific Application: This allows for the construction of quantum advantage demonstrations in fields like sampling or optimization where verifying the output distribution is computationally intractable. The system can solve problems that require an exponential number of queries in standard models but only a polynomial number of calls to this restricted IQP oracle (as shown by Theorem 3).
Improvement: Enhanced Oracle Separation for Complexity Classes.
Capability: The system can provide a formal proof that there exists an oracle separating the complexity class BPPIQP from the Polynomial Hierarchy (PH), i.e., showing that there is a problem solvable efficiently in this restricted quantum model that cannot be solved by any algorithm in PH (Theorem 4).
Improvement: Quantifiable Fourier Growth Bounds for Restricted Quantum Computation.
Capability: The system can provide rigorous, tight upper bounds on the complexity of approximating the acceptance probability of any IQP circuit. Specifically, it demonstrates that to solve a problem like 3-Forrelation with constant advantage, an IQP circuit requires a query complexity scaling as much as O(N/3), which is strictly less powerful than the query bounds achievable by full BQP or 1/2-BQP models for that specific problem.
Improvement: Tailored Quantum Circuit Design for Specific Function Classes.
Capability: The system can utilize specialized diagonal unitary operators (the "D" in the IQP circuit) constructed using quadratic functions like the Reed–Muller code structure, to extract inner-product phases within the computation efficiently, which is key to solving 2-Forrelation.

In essence, this research improves AI by providing a precise blueprint for exploiting quantum features (like phase information encoded in diagonal operators) within a structurally constrained quantum model (IQP), allowing for more robust and theoretically grounded proofs of quantum advantage that bypass the verification bottlenecks associated with general BQP sampling tasks.

Abstract

The 2-Forrelation problem provides an optimal separation between classical and quantum query complexity and is also the problem used for separating and 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 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 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 O O, strengthening the result of Raz and Tal (STOC 2019). It also yields an oracle separation between and 1. We prove Fourier growth bounds for multi-query 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 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 circuit.