⚛️ quantum physics

IQP circuits for 2-Forrelation

This paper demonstrates that the 2-Forrelation problem, which optimally separates classical and quantum query complexity, can be solved using minimal Instantaneous Quantum Polynomial-time (IQP) circuits with efficient classical post-processing, thereby strengthening oracle separations between $\mathsf{BPP}^{\mathsf{IQP}}$ and the polynomial hierarchy while offering a new pathway for verifying quantum advantage in decision problems.

Original authors: Quentin Buzet, André Chailloux

Published 2026-04-17

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Quentin Buzet, André Chailloux

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: The Quantum "Magic Trick"

Imagine you are trying to solve a puzzle that is incredibly hard for a normal computer (a classical computer) but easy for a quantum computer. This specific puzzle is called 2-Forrelation.

Think of 2-Forrelation as a game where you have two secret recipes (functions $f$ and $g$ ). The goal is to figure out if these two recipes are "secretly related" in a very specific, hidden way.

Classical computers are like detectives who have to check every single ingredient in the recipes one by one. To solve this, they would need to taste millions of ingredients, which takes forever.
Standard Quantum computers are like wizards who can taste the whole recipe at once with just a few magical glances. They solve it instantly.

The big question the authors asked was: "Do we need a full-blown wizard (a standard quantum computer) to solve this, or can we get away with a simpler magic trick?"

They discovered that we can! We can solve this hard puzzle using a much simpler, more restricted type of quantum machine called an IQP circuit.

What is an IQP Circuit? (The "Instantaneous" Machine)

To understand the breakthrough, we need to understand the difference between a standard quantum computer and an IQP (Instantaneous Quantum Polynomial-time) circuit.

Standard Quantum Computer: Imagine a complex orchestra where instruments play one after another. The violin plays, then the flute, then the drums. The order matters, and the musicians must stay perfectly in sync (coherent) for a long time. This is hard to build because if the orchestra gets noisy or loses sync, the music fails.
IQP Circuit: Imagine a choir where everyone sings at the exact same time. Because they all sing simultaneously, they don't need to worry about who goes first. In technical terms, all the "gates" (the musical notes) in an IQP circuit commute, meaning they can be played in any order or all at once.

Why does this matter?
Because they happen all at once, IQP circuits are much easier to build and less prone to errors. They are "weaker" than full quantum computers, but the authors proved they are still strong enough to solve the 2-Forrelation puzzle.

The Secret Ingredient: The "Quadratic" Key

How did they make this simple machine solve a hard puzzle? They used a clever mathematical trick involving a specific shape called a Quadratic Function.

Think of the 2-Forrelation puzzle as trying to measure the "overlap" between two waves.

The standard way to do this involves a complex dance of steps (Hadamard gates) that the simple IQP machine can't do.
The authors found a mathematical "key" (the function $Q(x)$ ) that acts like a translator.

This key has a special property: it can turn a complicated interaction between two variables into a simple sum. It's like having a magic decoder ring that translates a secret code written in a complex language into a simple list of numbers.

By using this key, they were able to "hide" the complex parts of the puzzle inside the simple, simultaneous structure of the IQP circuit. They essentially tricked the simple machine into doing the heavy lifting by arranging the ingredients (the math) just right.

The Results: Why This Changes Everything

The paper has three major takeaways, explained simply:

1. We Can Do It with Less Power

They proved that you don't need a super-powerful, error-prone quantum computer to solve this specific problem. A simpler, more stable "instantaneous" machine (IQP) can do it with just two quick checks (queries).

Analogy: It's like realizing you don't need a Ferrari to win a race; a sturdy, reliable bicycle is fast enough if you know the right shortcut.

2. Beating the "Polynomial Hierarchy" (The Classical Wall)

In computer science, there is a theoretical wall called the Polynomial Hierarchy (PH). It represents the limit of what classical computers can do, even with infinite time and resources, for certain types of problems.

The authors showed that their simple IQP machine can solve the 2-Forrelation puzzle, but no classical computer (even a super-advanced one) can solve it efficiently.
The Impact: This proves that even "weak" quantum computers are strictly more powerful than the most advanced classical computers for this task. It's a definitive "Quantum Advantage."

3. A New Way to Prove Quantum Power (Without the Headache)

Usually, to prove a quantum computer is better, scientists ask it to generate a random pattern (sampling) that is too hard to check. This is like asking a magician to pull a rabbit out of a hat, but the only way to verify it's a real rabbit is to watch the whole trick, which is hard to do.

The Problem: Verifying these "sampling" experiments is a nightmare.
The Solution: Because 2-Forrelation is a decision problem (Yes/No answer), it's much easier to verify. You just check the answer.
The Benefit: This opens a new door for showing off quantum advantage. We can build simpler, easier-to-verify experiments that prove quantum computers are superior, without needing to trust complex, uncheckable random patterns.

Summary

The authors of this paper took a famous, hard quantum puzzle (2-Forrelation) and showed that it can be solved by a simpler, more robust type of quantum computer (IQP).

They did this by finding a clever mathematical shortcut (the quadratic function) that allows the simple machine to bypass the need for complex, sequential steps. This proves that even "weak" quantum computers are powerful enough to outsmart the best classical computers, offering a new, easier path to demonstrating the true power of quantum technology.

1. Problem Statement and Context

The 2-Forrelation Problem:
The 2-Forrelation problem involves distinguishing between two functions $f, g: \{0, 1\}^n \to \{-1, +1\}$ based on their "forrelation" value:
$\Phi(f, g) = \frac{1}{2^{3n/2}} \sum_{x,y \in \{0, 1\}^n} (-1)^{x \cdot y} f(x)g(y)$
The task is to decide if $|\Phi(f, g)|$ is large or small.

Classical Hardness: It requires $\Theta(2^{n/2})$ randomized queries.
Quantum Efficiency: It can be solved with $O(1)$ quantum queries (specifically 2 queries in the standard BQP model).
Complexity Significance: It provides an optimal separation between classical and quantum query complexity and was used by Raz and Tal [RT22] to separate the complexity classes BQP and the Polynomial Hierarchy (PH) relative to an oracle.

The Open Question:
While 2-Forrelation is solvable in BQP, it is not believed to be BQP-complete. A natural question arises: What are the minimal quantum resources required to solve it? Specifically, can it be solved by Instantaneous Quantum Polynomial-time (IQP) circuits?

IQP Model: A restricted model where all gates commute (diagonal in the X-basis). They are structurally simpler than general BQP circuits and are candidates for demonstrating quantum advantage via sampling.
The Gap: Previous work showed 2-Forrelation is solvable in $1/2$ -BQP but requires exponential queries for DQC1. It was unknown if IQP (which is contained in $1/2$ -BQP) could solve it. Girish [Gir25] explicitly asked if 2-Forrelation is solvable in IQP and, if not, to prove Fourier growth bounds.

2. Methodology and Key Techniques

The authors construct explicit IQP computations to solve 2-Forrelation. An IQP computation is defined as running one or more IQP circuits with efficient classical pre-processing and post-processing (captured by the class BPPIQP).

A. The Core Construction (Single Query)

The standard BQP circuit for 2-Forrelation interleaves Hadamard gates between oracle calls ( $H \to O \to H \to O \to H$ ). IQP circuits have the structure $H^{\otimes m} D H^{\otimes m}$ , where $D$ is diagonal.

Challenge: The oracle $O_{f,g}$ is diagonal in the computational basis, so it can be absorbed into $D$ . However, the standard algorithm requires a Hadamard layer between the two oracles, which IQP lacks.
Solution: The authors use a quadratic function $Q(x) = \sum_{i<j} x_i x_j$ $Q (x) = \sum_{i < j} x_{i} x_{j}$ over $\mathbb{F}_2$ $F_{2}$ .
- Key Identity: $Q(x) + Q(y) + Q(x+y) = x \cdot y + |x||y| \pmod 2$ .
- Parity Splitting: When $|x+y|$ is odd, $|x||y| \equiv 0 \pmod 2$ , simplifying the identity to $Q(x) + Q(y) + Q(x+y) = x \cdot y$ .
- Construction: They define specific diagonal operators $D$ and acceptance sets $F$ using functions $\rho_0, \rho_1$ derived from $(-1)^{Q(x)}$ and a "bent" function $\sigma$ .
- Result: By randomly choosing between two circuits (one targeting pairs with odd Hamming weight sum, one for even), they achieve an acceptance probability proportional to $\Phi(f, g)$ .

B. Handling $|\Phi(f, g)|$ (Signed vs. Absolute Value)

Signed Variant: A single IQP circuit with 1 query suffices to distinguish based on the sign of $\Phi(f, g)$ .
Absolute Value Variant: To distinguish based on $|\Phi(f, g)|$ $∣Φ (f, g) ∣$ , the authors run the signed circuit twice independently. They accept if both runs yield the same outcome (both accept or both reject).
- This squares the bias: $P_{acc} \approx \frac{1}{2} + c \cdot \Phi^2(f, g)$ .
- This requires 2 quantum queries to the joint oracle $O_{f,g}$ .

C. Fourier Growth Bounds

The paper also establishes upper bounds on the Fourier growth of IQP circuits.

Definition: $L_{1, \ell}(p)$ measures the weight of degree- $\ell$ Fourier coefficients of the acceptance probability polynomial $p$ .
Result: For a $d$ -query IQP circuit with acceptance set size $|F|$ , the level-2 Fourier growth is bounded by $\sqrt{\min(|F|, 2^{nd})}$ .
Implication: Since solving 2-Forrelation requires $L_{1,2} = \Omega(2^{n/2})$ , any IQP circuit solving it must have an acceptance set of size $|F| = \Omega(2^n)$ . The authors' construction achieves $|F| = 2^n$ , proving the bound is tight.

3. Key Contributions and Results

Solvability in IQP:
- Signed 2-Forrelation: Solvable by 1 IQP circuit and 1 quantum query (with classical pre/post-processing).
- Absolute Value 2-Forrelation: Solvable by 2 IQP circuits (run sequentially) and 2 quantum queries.
- This answers the open question of Girish [Gir25] affirmatively.
Oracle Separation (BPPIQP vs. PH):
- Using the IQP solution for 2-Forrelation, the authors prove that relative to an oracle $O$ :
  $(\text{BPPIQP})^O \not\subseteq \text{PH}^O$
- Significance: This strengthens the Raz-Tal result ( $\text{BQP}^O \not\subseteq \text{PH}^O$ ). Since IQP is a strictly weaker model than BQP, showing that even this restricted model can separate from PH implies that the "quantum advantage" for this problem does not require full BQP power.
Fourier Growth Bounds:
- Proved that any IQP circuit solving 2-Forrelation with constant advantage must have an exponentially large acceptance set ( $|F| = \Omega(2^n)$ ).
- This contrasts with standard BQP circuits for 2-Forrelation, which often accept on a single outcome (e.g., $0^n$ ). This highlights a structural difference: IQP requires a high-dimensional output space to achieve the necessary Fourier weight.

4. Significance and Implications

Mapping the Quantum Landscape: The results refine our understanding of the hierarchy between classical (BPP), restricted quantum (IQP, DQC1, $1/2$ -BQP), and full quantum (BQP) computation. 2-Forrelation is shown to sit within the power of IQP, placing it lower in the hierarchy than previously thought.
Quantum Advantage Experiments:
- Current proposals for quantum advantage often rely on sampling problems (e.g., Boson Sampling, IQP sampling), which are notoriously difficult to verify classically.
- Since 2-Forrelation is a decision problem (Yes/No) and solvable by IQP, it offers a new pathway for demonstrating quantum advantage.
- If instances of 2-Forrelation can be constructed with efficiently implementable oracles, they could lead to classically verifiable quantum advantage experiments, bypassing the verification bottlenecks of sampling tasks.
Algebraic Insight: The work demonstrates the utility of quadratic forms over $\mathbb{F}_2$ (specifically the Reed-Muller code structure) in designing quantum algorithms within restricted models.

Summary Table

Feature	Standard BQP	IQP (This Work)
Queries for 2-Forrelation	1 (Signed), 2 (Abs)	1 (Signed), 2 (Abs)
Circuit Structure	Interleaved Hadamards	$H D H$ (Commuting gates)
Acceptance Set Size	Small (e.g., $\|0^n\rangle$ )	Large ( $\|F\| = \Omega(2^n)$ )
Fourier Growth ( $L_{1,2}$ )	$\Theta(2^{n/2})$	$\Theta(2^{n/2})$ (Tight bound)
Complexity Class	$\text{BQP}^O \not\subseteq \text{PH}^O$	$(\text{BPPIQP})^O \not\subseteq \text{PH}^O$

In conclusion, the paper demonstrates that the "magic" required to solve 2-Forrelation and separate PH from quantum computation is already present in the restricted, commuting model of IQP, provided one allows for classical pre/post-processing and accepts a large output space.