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, two circuits with two quantum queries and efficient classical processing suffice. For the signed variant of 2-Forrelation, even a single 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 relative to an oracle , strengthening the result of Raz and Tal (STOC 2019). Our results show that circuits can be used for classically hard decision problems, thus providing a new route for showing quantum advantage with circuits, avoiding the verification difficulties associated with sampling tasks. We also prove Fourier growth bounds for circuits in terms of the size of their accepting set. The key ingredient is an algebraic identity of the quadratic function that allows extracting inner-product phases within an circuit.
AI Impact Assessments
(3 models)Scientific Impact Assessment: "IQP circuits for 2-Forrelation"
1. Core Contribution
This paper demonstrates that the 2-Forrelation problem—which achieves the optimal quantum-vs-classical query separation and underlies the Raz-Tal oracle separation of BQP from PH—can be solved using IQP circuits, a restricted model where all quantum gates commute. The key technical insight is an algebraic identity of the quadratic function Q(x) = Σ_{i<j} x_i x_j, which satisfies Q(x) + Q(y) + Q(x+y) = x·y + |x||y| (mod 2). When |x+y| is odd, the correction term vanishes, enabling extraction of inner-product phases within the commuting structure of an IQP circuit. The authors split the Forrelation sum into odd- and even-parity components, handle each with a separate IQP circuit, and combine them via classical randomization.
Concretely: (1) A single IQP circuit with one query solves signed 2-Forrelation; (2) Two IQP circuits with two queries solve the absolute-value variant; (3) This yields (BPP^IQP)^O ⊄ PH^O, strengthening Raz-Tal; (4) Fourier growth bounds for IQP circuits are established, showing any IQP circuit solving 2-Forrelation needs |F| = Ω(2^n) accepting outcomes.
2. Methodological Rigor
The paper is methodologically sound with clear, self-contained proofs. The construction is explicit and elementary—no heavy machinery beyond Fourier analysis on the Boolean cube and basic linear algebra. The framework established in Proposition 1 cleanly identifies the degrees of freedom (diagonal operator D and accepting set F) and the conditions they must satisfy (bentness condition on σ, efficient computability).
The impossibility result (Proposition 3) is proven directly and elegantly—showing no functions ρ₀, ρ₁, σ can achieve the full inner-product relation, which motivates the parity-splitting approach. The proof that the quadratic function Q resolves this on parity-restricted domains is tight and verifiable. The Fourier growth analysis in Section 5 uses standard matrix norm techniques (Frobenius/operator norm bounds via isometries) and the reduction from d-query to single-query via diagonal composition is clean.
One minor point: the even-n case requires padding, losing a constant factor in bias. The authors acknowledge this and note they don't know how to handle even n directly—this is transparent and honest. The reduction from d queries to a single query on an enlarged register is well-argued.
3. Potential Impact
Theoretical impact: This result significantly refines our understanding of the quantum complexity landscape below BQP. It places IQP computations—with their commuting gate structure—firmly outside PH relative to an oracle, which is a meaningful strengthening of Raz-Tal. The result answers an explicit open question from Girish (STOC'26), demonstrating timeliness.
Quantum advantage implications: Perhaps the most practically significant aspect is the observation that IQP circuits can solve a *decision* problem that is classically hard, rather than just producing hard-to-simulate sampling distributions. This circumvents the verification problem that has plagued IQP-based quantum advantage proposals. If concrete instances with efficiently implementable oracles can be identified, this could lead to new, verifiable quantum advantage experiments—a significant practical direction.
Structural insights: The Fourier growth bounds for IQP (Table 1) fill in an important entry in the landscape of circuit complexity bounds. The tight threshold |F| = Ω(2^n) reveals a qualitative difference from BQP circuits (which accept on a single string 0^n), showing that IQP must "spread" its acceptance over exponentially many outcomes.
Limitations on further generalization: The authors note that IQP cannot solve 3-Forrelation (by combining Girish's result with IQP ⊆ ½-BQP), which clearly delineates the boundary of what IQP can achieve.
4. Timeliness & Relevance
The paper is highly timely. It directly answers an open question from a recent paper accepted at STOC'26. The broader research program of understanding sub-BQP complexity classes (½-BQP, DQC_k, IQP) is an active area, and this paper makes a definitive contribution. The quantum advantage angle—finding verifiable demonstrations using restricted circuits—is a pressing practical concern as near-term quantum devices become more capable but remain limited in circuit depth and gate variety.
5. Strengths & Limitations
Strengths:
Limitations:
Overall Assessment: This is an elegant and well-executed theoretical contribution that answers a natural open question with a surprising positive result. The algebraic insight connecting the quadratic function to inner-product extraction within IQP circuits is both simple and powerful. The paper advances our understanding of restricted quantum models and opens promising new directions for verifiable quantum advantage. It represents a meaningful step in the quantum complexity theory research program.
Generated Apr 17, 2026
Comparison History (47)
Paper 2 makes a fundamental contribution to quantum computational complexity theory by showing IQP circuits can solve the 2-Forrelation problem, answering an open question and strengthening the Raz-Tal oracle separation. This provides a new route to quantum advantage with restricted quantum circuits, avoiding verification difficulties of sampling tasks. The result has broad theoretical implications across quantum complexity, quantum advantage demonstrations, and computational theory. Paper 1, while practically useful, presents an incremental advance in entangled photon-pair generation using a known material platform (LiNbO3), with more limited novelty and narrower impact scope.
Paper 2 likely has higher impact due to strong real-world applicability and timeliness: an integrated, telecom-band, tunable polarization-entangled photon source in thin-film lithium niobate aligns with scalable quantum photonics, communications, and networking, leveraging a widely adopted fabrication platform. If experimentally validated with high brightness/fidelity and manufacturability, it could be broadly enabling across multiple fields. Paper 1 is novel and rigorous in quantum complexity, answering an open question and strengthening oracle separations, but its impact is more specialized and primarily theoretical, with less direct near-term technological leverage.
Paper 1 offers a practically oriented algorithmic advance for near/early fault-tolerant quantum chemistry and materials simulation: it addresses a concrete bottleneck in sample-based diagonalization, provides analytic complexity gains, and reports substantial reductions in T-count and circuit depth versus iQPE—clear real-world relevance and timeliness. Paper 2 is highly novel and rigorous in complexity theory (IQP power, oracle separations, resolving an open question), but its impact is more specialized and indirect for applications. Overall, Paper 1 is more likely to influence both methods and deployments across quantum simulation workflows.
Paper 2 likely has higher scientific impact: it resolves a recent open question by showing 2-Forrelation is solvable with very restricted IQP resources, strengthens an important oracle separation result, and introduces new technical tools (algebraic identity + Fourier growth bounds) with potential reuse in complexity theory and quantum advantage. Its impact spans theoretical CS, quantum complexity, and foundations. Paper 1 is practically valuable for early fault-tolerant quantum chemistry, but its scope is narrower and its gains are largely algorithmic/engineering within an existing paradigm.
Paper 1 offers highly practical, record-breaking experimental results in quantum access networks. Its compatibility with existing optical infrastructure gives it immediate, immense potential for real-world deployment in secure communications. While Paper 2 provides important theoretical advancements in quantum complexity, Paper 1's combination of high key rates, hardware compatibility, and direct application to emerging quantum networks promises broader and more immediate scientific and technological impact.
Paper 2 likely has higher scientific impact due to immediate real-world applicability and demonstrated performance: an experimental, record-level (19.48 Mbps/user) fully passive QPON protocol compatible with existing optical access infrastructure, enabling scalable point-to-multipoint deployment. This combination of practicality, timeliness (networked QKD), and integration potential can influence both quantum communications and telecom engineering. Paper 1 is highly novel and rigorous in quantum complexity theory (IQP power, oracle separations), but its impact is primarily foundational and narrower in direct near-term applications compared to a deployable high-rate network protocol.
Paper 2 addresses a critical engineering bottleneck for quantum networks—dynamic routing of entanglement—with both theoretical design and experimental demonstration. Its practical implications for building scalable quantum internet infrastructure give it broader real-world impact across quantum computing, communications, and networking. Paper 1, while theoretically elegant in showing IQP circuits suffice for 2-Forrelation and strengthening oracle separations, has narrower impact within quantum complexity theory. Paper 2's experimental validation, encoding-agnostic design, and scalability projections position it for wider interdisciplinary influence.
Paper 2 makes a fundamental contribution to quantum complexity theory by showing IQP circuits suffice for 2-Forrelation, strengthening the Raz-Tal oracle separation and answering an open question. This connects restricted quantum computation models to foundational complexity separations and opens new routes for quantum advantage via decision problems rather than sampling. Paper 1 presents a solid engineering contribution (a new CA decoder for quantum error correction) but is more incremental within an established research direction. Paper 2's theoretical implications span quantum complexity, computational advantage, and circuit complexity with broader foundational impact.
Paper 2 addresses fundamental questions in quantum complexity theory, showing that restricted IQP circuits can solve classically hard decision problems. By providing a new route for demonstrating quantum advantage that avoids the verification difficulties of sampling tasks and strengthening a major result (Raz and Tal), it is likely to have a profound and lasting impact on the field of quantum computer science compared to the simulation framework in Paper 1.
Paper 1 offers highly practical, concrete architectural blueprints and resource estimates (11,495 atoms, 15 hours) for achieving fault-tolerant quantum advantage using neutral atoms. Its direct relevance to near-term hardware development and experimental realization provides a broader and more immediate scientific impact across physics, engineering, and computer science compared to Paper 2, which focuses on a theoretical complexity result and oracle separations, impacting a narrower subfield.
Paper 2 proposes a practical fault-tolerant architecture for neutral atom systems, directly addressing the bottleneck of realizing quantum advantage in near-term hardware. By reducing overhead and providing explicit benchmarks (11,495 atoms, 15 hours), it offers highly actionable insights for experimentalists and engineers. In contrast, Paper 1 presents significant theoretical advancements in quantum complexity and oracle separations, which, while valuable to theoretical computer science, have a narrower and less immediate real-world impact than the hardware-aware solutions in Paper 2.
Paper 1 offers a highly practical, scalable framework for preparing correlated quantum states in programmable platforms like Rydberg arrays, directly addressing a major bottleneck in experimental quantum computing. Its lack of reliance on prior Hamiltonian knowledge broadens its applicability. While Paper 2 provides significant theoretical advancements in quantum complexity and quantum advantage, Paper 1's direct relevance to rapidly advancing experimental technologies gives it higher potential for broad, near-term impact across quantum physics and engineering.
Paper 2 identifies a novel hardware-level side-channel vulnerability in scalable chip-based QKD systems. This discovery has immediate, practical implications for the engineering and security analysis of quantum communication networks, necessitating shifts in security-aware device design. While Paper 1 provides a strong foundational advancement in quantum complexity theory and quantum advantage, Paper 2's direct real-world applicability, intersection of quantum engineering and cybersecurity, and timely relevance to technologies nearing commercialization give it a higher potential for broad scientific and technological impact.
Paper 2 likely has higher impact: it resolves a recent open question by showing 2-Forrelation is solvable with highly restricted IQP (commuting) circuits, and strengthens oracle separations related to BQP vs PH—core complexity-theory results with broad relevance across quantum computation and theoretical CS. The contributions appear methodologically rigorous (explicit constructions, complexity consequences, new Fourier growth bounds, key algebraic identity) and timely. Paper 1 is innovative and potentially valuable for NISQ/VQA training, but its impact depends more on empirical robustness and adoption; its theoretical claims (TEE as regularizer, “edge of chaos”) may be less universally foundational.
Paper 2 resolves an open question about minimal quantum resources for 2-Forrelation, strengthens the landmark Raz-Tal oracle separation (BPP^IQP vs PH), and opens a new route for demonstrating quantum advantage via IQP circuits on decision problems rather than sampling. This has broad theoretical implications for computational complexity and quantum advantage foundations. While Paper 1 presents a useful quantum simulation framework with experimental validation, Paper 2's contributions to fundamental complexity theory—connecting IQP, quantum query complexity, and the BQP vs PH separation—are likely to have deeper and more lasting impact across quantum computing theory.
Paper 1 addresses a fundamental problem in quantum complexity theory, strengthening a seminal oracle separation result and offering a novel pathway to demonstrate quantum advantage using restricted (IQP) circuits without the usual sampling verification issues. This provides broader and more timely implications for quantum computing compared to Paper 2, which offers specialized insights into quantum chaos within a specific spin model.
Paper 1 has higher likely scientific impact due to clear theoretical novelty (IQP solving 2-Forrelation with minimal queries), resolution of a recent open question, and strengthened oracle separations (implicating core complexity-theoretic boundaries like BQP vs PH). Its results can influence multiple subareas (restricted quantum models, quantum advantage, Fourier analysis/Boolean functions). Paper 2 is timely and practically relevant for hybrid HPC–QPU operations, but its contributions are more engineering-incremental and likely narrower in long-term foundational impact.
Paper 1 resolves an open question about minimal quantum resources for a fundamental problem in quantum complexity theory, establishes new oracle separations (BPP^IQP vs PH), and opens a new route for quantum advantage with IQP circuits beyond sampling tasks. This has broad implications for quantum complexity theory and practical quantum advantage demonstrations. Paper 2 proposes a ground-state preparation method via nonlinear dissipation, which is interesting but incremental—building on prior work and facing practical challenges with nonlinear quantum dynamics. Paper 1's contributions to foundational complexity separations and quantum advantage give it higher impact potential.
Paper 1 demonstrates a practical breakthrough in superconducting qubit reset achieving residual excited-state populations below 10^-4, improving by 1-2 orders of magnitude over existing schemes. This directly addresses a critical bottleneck in quantum computing hardware—high-fidelity qubit initialization—with broad implications for error correction, repeated measurements, and scalable quantum processors. Paper 2 makes an elegant theoretical contribution to quantum complexity theory (IQP circuits solving 2-Forrelation), but its impact is more niche, primarily advancing our understanding of computational complexity separations rather than enabling new practical capabilities.
Paper 1 establishes a fundamental result in quantum complexity theory by showing IQP circuits can solve the 2-Forrelation problem, strengthening the Raz-Tal oracle separation and answering an open question. It opens a new route for quantum advantage via decision problems rather than sampling, which has broad theoretical implications. Paper 2 presents a useful experimental demonstration of Gaussian decoherence suppression, but is more incremental in nature. Paper 1's impact spans complexity theory, quantum computing foundations, and quantum advantage demonstrations, giving it broader and deeper theoretical significance.