⚛️ quantum physics

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

This paper constructs a recursive oracle relative to which there exists a unary language in $\mathsf{EQP}$ that is not in $\mathsf{IP}$ (or $\mathsf{PH}$ ), thereby establishing a non-relativizing separation between exact quantum polynomial time and interactive proof systems through a refined Forrelation problem with exact correlation promises.

Original author: Sinan Oral, Supartha Podder

Published 2026-11-10

📖 6 min read🧠 Deep dive

CC BY 4.0

Original author: Sinan Oral, Supartha Podder

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 author. For technical accuracy, refer to the original paper. Read full disclaimer

In the world of computing, there is a fundamental question about what different kinds of machines can actually solve. On one side, we have classical computers, the machines that power our daily lives, which process information by following strict, step-by-step logical rules. On the other side are quantum computers, a newer and more exotic technology that uses the strange laws of physics to explore many possibilities at once. For decades, scientists have wondered if these two types of machines are truly different in their power, or if a clever enough classical computer could eventually mimic any quantum task. To test this, researchers often use a theoretical tool called an "oracle." Think of an oracle as a mysterious black box that answers specific questions instantly. By giving both a classical and a quantum computer access to the same black box, scientists can see if the quantum machine can solve a problem that the classical one simply cannot, no matter how much time or effort it spends. This setup helps reveal the true limits of classical logic when faced with quantum speed.

A recent study by researchers at Stony Brook University has pushed this investigation further, settling a specific debate about the limits of classical verification. The team constructed a very specific type of black box and a corresponding problem that a quantum computer can solve with absolute certainty using just three questions to the box. However, they proved that no classical computer, even one allowed to interact with a powerful, unrestricted helper, can ever solve this same problem with the same level of certainty. This result is significant because it shows that the gap between quantum and classical computing is not just a matter of speed, but of fundamental capability. Even if a classical computer is allowed to ask for help from a super-intelligent prover, it still cannot verify the quantum solution for this specific task. The researchers demonstrated that this separation holds true even when the quantum computer is required to be perfectly exact, leaving no room for error or probability.

The core of their discovery revolves around a mathematical puzzle known as "Forrelation." Imagine two lists of numbers, where each number is either positive or negative. The puzzle asks you to find out how closely these two lists are related to each other through a specific mathematical transformation. In this new study, the researchers focused on a version of the puzzle where the relationship between the lists is promised to be exactly one-half or exactly negative one-half. A quantum computer can determine which of these two cases is true by asking the black box for information just three times. It does this by creating a delicate interference pattern, where the answers from the box cancel each other out in one scenario and reinforce each other in the other, leading to a clear, definite answer.

The challenge for the researchers was to prove that a classical computer could not do the same thing. They had to show that for any strategy a classical computer might use, there would always be a pair of lists that looked identical to the classical machine but actually belonged to different categories. To do this, they had to create a very specific set of rules for generating these lists. They started with a random distribution of numbers and then carefully adjusted the counts of positive and negative signs to hit the exact target values required by the puzzle. This adjustment process, which they called a "repair," was the most difficult part of the work. They had to ensure that while they fixed the numbers to meet the exact requirements, they did not accidentally make the lists look different to a classical observer. If the lists looked too different, a classical computer might easily spot the difference and solve the puzzle.

The researchers succeeded in creating these "repaired" distributions. They proved that even after making these precise adjustments, the resulting lists remained indistinguishable to any classical computer operating within the limits of current complexity theory. This includes computers that can run interactive proofs, where a verifier asks questions to a powerful prover, and computers that operate within the polynomial hierarchy, a broad class of complex logical problems. The proof showed that no matter how many messages were exchanged or how deep the logical reasoning went, the classical computer could not reliably tell the difference between the two types of lists. The quantum computer, by contrast, could distinguish them with absolute certainty using only three queries.

This finding strengthens our understanding of the boundary between quantum and classical computing. It confirms that there are problems where quantum mechanics offers a unique advantage that cannot be replicated by classical logic, even with the help of unlimited computational power from a prover. The researchers did not just suggest this possibility; they provided a rigorous mathematical construction that rules out the idea that classical computers could ever catch up in this specific scenario. Their work relies on a uniform quantum algorithm that works the same way for every input, using a fixed set of basic operations. This uniformity ensures that the quantum advantage is not a fluke of a specific setup but a robust feature of the quantum approach.

The implications of this work extend beyond just solving a theoretical puzzle. It helps define the true power of quantum computers in a world where they might one day be used for real-world applications. By showing that certain problems are fundamentally out of reach for classical verification, the study highlights the unique role quantum machines will play in the future of computation. The researchers' method of carefully repairing distributions to maintain indistinguishability while enforcing exact constraints is a novel technique that could be useful in other areas of theoretical computer science. It demonstrates a high level of control over complex mathematical structures, allowing them to engineer scenarios where quantum mechanics shines and classical logic fails.

In the end, the study provides a clear answer to a long-standing question about the nature of computation. It shows that the ability of a quantum computer to solve a problem with absolute certainty using very few steps is a capability that no classical system, no matter how clever or powerful, can replicate. This separation is not just a gap in efficiency, but a gap in kind. The researchers have built a bridge between abstract theory and concrete proof, showing that the quantum world operates on rules that are fundamentally different from our everyday experience. Their work stands as a testament to the power of quantum mechanics and a reminder that the limits of classical computing are more rigid than we might have hoped.

Technical Summary: EQP ⊆ IP Does Not Relativize

Problem Statement
The paper addresses the question of whether the containment of quantum complexity classes within classical interactive proof systems relativizes. Specifically, it investigates whether $EQP$ (the class of decision problems solvable exactly in quantum polynomial time) is contained in $IP$ (Interactive Proofs) and $PH$ (the Polynomial Hierarchy) relative to an arbitrary oracle. While it is known that $BQP \subseteq PSPACE = IP$ in the unrelativized world, Bouland, Huang, Natarajan, Shalit, and Tal [BHNST26] recently showed that this containment does not relativize by constructing an oracle $O$ for which $BQP^O \not\subseteq IP^O$ . This paper extends that separation to the exact quantum setting, proving that there exists a recursive oracle $O$ such that $EQP^O \not\subseteq IP^O$ and $EQP^O \not\subseteq PH^O$ .

Methodology
The authors construct a recursive Boolean oracle $O$ and a unary language $L$ that separates these classes. The separation is based on a variant of the Forrelation problem, a promise problem distinguishing between two Boolean functions $f, g: \{0, 1\}^n \to \{\pm 1\}$ based on their normalized correlation with the Fourier transform of the other.

Exact Promise: Unlike previous works that used approximate correlations, this paper focuses on the exact promise where the Forrelation value is exactly $+1/2$ or $-1/2$ .
Quantum Algorithm: A uniform polynomial-time quantum algorithm is constructed that solves this promise problem with certainty using exactly three phase queries. The algorithm utilizes amplitude amplification on a standard one-query interference test.
Classical Indistinguishability: The core technical challenge is constructing probability distributions $E_{n, \sigma}$ (for $\sigma \in \{+1, -1\}$ ) supported exactly on the promise sets $L_{n, \sigma}$ (where Forrelation is $\sigma/2$ ) such that these distributions are indistinguishable from the uniform distribution by any resource-bounded classical test (either an interactive verifier or a bounded-depth circuit).

Key Technical Contributions
The paper introduces a novel "repair method" to bridge the gap between continuous Gaussian distributions and exact discrete promise sets while preserving indistinguishability:

Gaussian Reference and Conditional Independence: The construction starts with a Gaussian-sign distribution $G_{n, \sigma}$ and transitions to a conditional product distribution $P_{n, \sigma}$ . This step involves replacing the magnitudes of the underlying Gaussian variables with independent Gaussians to ensure that, conditioned on the sign vector $f$ , the signs of $g$ are independent.
Count Repair: To enforce the exact Forrelation promise (an integer constraint on the sum of weighted signs), the authors introduce a "count repair" procedure. They partition the coordinates into "weight bins" based on the Fourier coefficients of $f$ . Within each bin, they deterministically adjust the number of positive signs to satisfy the global energy constraint exactly.
Indistinguishability Preservation: The paper proves that this repair process does not significantly alter the acceptance probability of classical tests.
- For Convex Tests (modeling Interactive Proofs), the authors use a coupling argument based on conditional means and the Lipschitz property of the tests. They show that the fractional change in bin counts is small enough that the expectation difference is negligible.
- For Boolean Tests (modeling $PH$ ), they utilize the concept of "restriction-stable criticality." By leaving a narrow window of uncertainty around the bin thresholds, they construct a random restriction that both the repaired distribution and the product distribution extend with high probability. This allows the application of known bounds on decision tree depth under random restrictions.
Analytic Tools: The paper employs the Lindeberg method and Price's formula to bound the errors introduced by replacing magnitudes and interpolating covariances, ensuring that the transition from the Gaussian reference to the exact distribution incurs only vanishing error terms.

Results
The main result is Theorem 1.1: There exist a recursive Boolean oracle $O$ and a unary language $L$ such that:

$L \in EQP^O$ (decided by a 3-query exact quantum algorithm).
$L \notin IP^O$ .
$L \notin PH^O$ .

The separation holds for interactive proofs with private randomness and unrestricted provers, and for the entire polynomial hierarchy. The proof relies on showing that for any fixed classical candidate (verifier or circuit), there exists a sufficiently large input length where the candidate fails to distinguish the exact distributions $E_{n, +}$ and $E_{n, -}$ from the uniform distribution, and consequently fails to distinguish the promise sets.

Significance
The paper claims to strengthen the oracle separation of Bouland et al. [BHNST26] from $BQP$ to $EQP$ . This is significant because $EQP$ represents the class of problems solvable by quantum computers with zero error probability, a stricter requirement than the bounded-error class $BQP$ . The result demonstrates that the obstruction to relativizing $BQP \subseteq IP$ is robust and persists even when the quantum algorithm is required to be exact.

Furthermore, the paper highlights that the separation is achieved with a remarkably low query complexity (three queries) for the quantum algorithm, contrasting with previous exact quantum separations that often required unbounded recursion or higher query counts. The construction of distributions supported on exact promise sets while maintaining indistinguishability from uniform distributions is presented as a new technical tool that may be applicable to other problems involving exact quantum advantages.

The authors explicitly state that the separation is achieved via a recursive oracle constructed through exhaustive search over decidable promise sets, ensuring the oracle is computable, though not necessarily polynomial-time computable. The work does not propose new experimental implementations or applications outside the theoretical framework of complexity theory and oracle separations.

Technical Summary: EQP ⊆ IP Does Not Relativize

More like this