⚛️ quantum physics

The Low-Individual-Degree Test Without the Diagonal-Lines Test Is Not Quantum-Sound

This paper demonstrates that the diagonal-lines test is essential for the quantum soundness of the low-individual-degree test and cannot be removed without an alternative compatibility mechanism, thereby showing that a proposed simplification in the MIP*=RE proof does not preserve the required soundness.

Original authors: Tianrun Zhao

Published 2026-09-14

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Tianrun Zhao

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

In the strange and counterintuitive world of quantum computing, scientists often rely on a clever trick to verify that a machine is doing what it claims to be doing. Imagine a game where two players, who cannot communicate with each other, are asked questions about a massive, complex pattern. To prove they are truly following a single, consistent set of rules, they must answer in a way that lines up perfectly. In the classical world, if their answers match up along every straight line drawn through the pattern, we can be sure they are describing one single, global object. This logic is the foundation of "low-degree tests," a tool used to check if local answers come from a single global polynomial, a mathematical shape that curves gently rather than twisting wildly.

However, the quantum world is far more slippery. In quantum mechanics, the act of measuring a system can change it, and different measurements might not be compatible with one another. This means two players sharing a quantum state might give answers that look perfect when checked along specific directions, yet fail to represent a single, coherent reality. For years, researchers believed that checking consistency along horizontal and vertical lines was enough to guarantee this global harmony, even in the quantum realm. They thought that if the answers aligned perfectly on these grid-like paths, the underlying quantum measurements must be working together correctly. This belief was crucial for a major breakthrough in computer science that proved quantum computers could solve problems previously thought impossible.

A researcher has now shown that this belief is incorrect. They demonstrated that checking only the horizontal and vertical lines is not enough to force the quantum players to agree on a single global truth. By constructing a specific quantum strategy, they proved that two players can pass every test involving these straight lines with perfect scores, yet still be fundamentally disconnected from one another. Their answers would look consistent on the grid, but the underlying quantum measurements would fail to align in the way required for a true global solution. This finding means that a specific check, known as the diagonal-lines test, cannot be removed from the verification process without adding a different mechanism to ensure the players are truly compatible.

The researcher built this counterexample using a mathematical landscape defined by a finite field, a system where numbers wrap around after reaching a certain prime number. They designed a strategy where two players share a maximally entangled quantum state, a special connection that links their actions regardless of distance. In this setup, the players are asked to provide answers for points and lines within a two-dimensional grid. The rules of their game require them to report values that match a polynomial of a specific degree. The researcher engineered their quantum measurements so that whenever a player is asked about a point on a horizontal or vertical line, their answer perfectly matches the polynomial reported for that entire line. They also ensured that if both players are asked about the same point, they always give the exact same answer.

Despite this flawless performance on all the standard checks, the strategy fails the ultimate test of global consistency. The researcher calculated that the players' measurements do not commute, meaning the order in which they are performed changes the outcome, a sign that they are not describing a single, unified reality. Specifically, they showed that the average error in this alignment is not a tiny, negligible number that vanishes as the system grows larger. Instead, the error remains stubbornly high, bounded away from zero by a constant value. Even as the grid becomes infinitely large, the players remain a fixed distance away from being able to describe a single global polynomial. This proves that the diagonal-lines test, which checks consistency along slanted paths, is not just a redundant step but a necessary component to catch this specific type of quantum deception.

The construction relies on a clever mapping of points to vectors in a higher-dimensional space, using a specific mathematical formula that ensures the measurements align perfectly along rows and columns but clash whenever both coordinates change. This creates a situation where the players are locally consistent but globally incompatible. The researcher confirmed that this failure is not a fluke of a single calculation but a fundamental obstruction. They showed that no matter what global measurement a third party tries to use to verify the players' answers, the strategy will always fail to match that global view by a significant margin. This result forces a reevaluation of how we verify quantum computations, confirming that we cannot simply assume that local consistency on a grid implies global truth.

This work does not suggest that quantum computers are broken or that the major result they helped prove is false. Rather, it clarifies the precise conditions needed to make that result hold. The original proof that quantum computers can solve these hard problems relied on a test that included the diagonal lines. This paper confirms that removing that part of the test would have been a mistake. The diagonal check is the missing piece that forces the quantum players to stop acting like independent local actors and start behaving as part of a single, coherent whole. Without it, the illusion of a global polynomial can be maintained even when the underlying reality is fractured.

The implications reach beyond just this one test. The study highlights a deep difference between the classical and quantum worlds. In the classical world, if you check a pattern along every straight line, you know the whole picture is consistent. In the quantum world, you must check along the diagonals as well to be sure. The researcher's work serves as a reminder that in the quantum realm, what looks perfect from one angle can be deeply flawed from another. Their proof is rigorous and complete, leaving no room for doubt that the diagonal-lines test is essential for the soundness of these quantum verification protocols. It closes the door on a potential shortcut in quantum verification, ensuring that future proofs remain built on a foundation that is truly solid.

Technical Summary: The Low-Individual-Degree Test Without the Diagonal-Lines Test Is Not Quantum-Sound

Problem Statement
The paper addresses a specific question regarding the quantum soundness of the classical low-individual-degree test, a critical component in the proof of the complexity class equality $\text{MIP}^* = \text{RE}$ [JNV+21]. In the corrected analysis by Ji, Natarajan, Vidick, Wright, and Yuen [JNV+20], the low-individual-degree test is decomposed into three subtests: the axis-parallel lines test, the self-consistency test, and the diagonal-lines test. The diagonal-lines test serves a specific role in the quantum setting: it provides a compatibility guarantee between point measurements associated with arbitrary pairs of points, a property that is automatic for classical global functions but non-trivial for quantum measurements.

The central question investigated is whether the diagonal-lines test is strictly necessary. Specifically, does perfect (or near-perfect) consistency on all axis-parallel lines and self-consistency checks suffice to force point measurements to approximately commute globally, thereby ensuring the existence of a global low-degree polynomial measurement? While [JNV+20] provided a counterexample for parameters $(m, d, q) = (2, 2, 4)$ , this example did not address the "large-field regime" where $d/q \to 0$ , which is relevant for the soundness of low-degree tests. This paper investigates whether the obstruction persists in this asymptotic regime.

Methodology
The author constructs a two-prover projective strategy for the reduced low-individual-degree test (containing only axis-parallel lines and self-consistency checks) over the finite field $\mathbb{F}_q$ with parameters $(m, d) = (2, 2)$ , where $q$ is any odd prime.

Hilbert Space and State: The strategy utilizes a Hilbert space $H = \mathbb{C}^{\mathbb{F}_q^3}$ and a maximally entangled state $|\Phi\rangle = \frac{1}{\sqrt{q^3}} \sum_{z \in \mathbb{F}_q^3} |z\rangle \otimes |z\rangle$ .
Point Measurements: For each point $u = (x, y) \in \mathbb{F}_q^2$ , the author defines a point measurement $A^u_a$ using Weyl operators. The construction relies on a specific label function $w: \mathbb{F}_q^2 \to \mathbb{F}_q^3 \oplus \mathbb{F}_q^3$ defined as:
$w(x, y) = (1, y, y^2; xy^2, -2xy, x)$
The measurement operators are constructed via Fourier projections:
$A^u_a = \frac{1}{q} \sum_{t \in \mathbb{F}_q} \omega^{-ta} W(tw(u))$
where $W$ denotes the generalized Weyl operator. Bob's measurements are defined as the transpose of Alice's.
Line Measurements: For axis-parallel lines $\ell$ , the strategy defines line measurements based on the subspace $S_\ell$ spanned by $\{w(u) : u \in \ell\}$ . The author proves that $S_\ell$ is an isotropic subspace with respect to the symplectic form, ensuring that the Weyl operators restricted to this subspace commute. This allows the construction of valid projective measurements for line answers that are consistent with the point measurements on that line.
Symplectic Property: A crucial property of the label $w$ is that its symplectic pairing satisfies $\langle w(u), w(v) \rangle = (x' - x)(y' - y)^2$ . This quantity vanishes if and only if $u$ and $v$ lie on the same axis-parallel line (i.e., $x=x'$ or $y=y'$ ), and is non-zero otherwise.

Key Results
The constructed strategy yields the following results:

Perfect Acceptance: The strategy passes both the self-consistency test and the axis-parallel lines test with probability 1. The point measurements and line measurements are perfectly refined; specifically, the line measurement operators refine the point measurement operators on the corresponding line.
Failure of Global Soundness: Despite passing the reduced tests perfectly, the strategy fails to admit a global low-individual-degree polynomial measurement.
- Commutator Error: For independent uniform points $u, v$ , the average state-dependent commutator error is calculated exactly:
  $\mathbb{E}_{u,v} \sum_{a,b} \| ([A^u_a, A^v_b] \otimes I) |\Phi\rangle \|^2 = 2 \left(1 - \frac{1}{q}\right)^3$
  As $q \to \infty$ (the large-field regime where $d/q \to 0$ ), this error approaches 2, rather than 0.
- Distance from Global Measurements: The author proves that for any projective measurement $G = \{G_g\}$ on Bob's space with outcomes being functions $g: \mathbb{F}_q^2 \to \mathbb{F}_q$ , the consistency with the constructed strategy is bounded away from 1:
  $\mathbb{E}_{u} \sum_{a} \sum_{g: g(u)=a} \langle \Phi | A^u_a \otimes G_g | \Phi \rangle \leq 1 - \frac{1}{16}\left(1 - \frac{1}{q}\right)^3 \leq 1 - \frac{1}{54}$
  This bound holds uniformly for all odd primes $q \geq 3$ .

Significance and Claims
The paper concludes that axis-parallel consistency alone is insufficient to enforce the global compatibility required for quantum soundness in the low-individual-degree test. Consequently, the diagonal-lines test (or an equivalent explicit compatibility mechanism) cannot be removed from the test suite without compromising the soundness guarantee.

The author explicitly states that their result does not rule out replacing the diagonal-lines test with another explicit compatibility test; it only demonstrates that the specific reduction to axis-parallel lines and self-consistency is inadequate. The work highlights a structural obstruction analogous to the Mermin–Peres magic square, where local compatibility (rows and columns) does not imply global commutativity.

The paper claims this result is significant for the foundational understanding of $\text{MIP}^* = \text{RE}$ , clarifying that replacing the "conditional linear functions" by "coordinate deletion functions" in the proof of $\text{MIP}^* = \text{RE}$ , as mentioned in [JNV+20], does not by itself preserve the required soundness. The construction relies on standard tools from harmonic analysis on finite abelian groups and finite-dimensional quantum mechanics, specifically utilizing the symplectic phase-space formulation of Weyl–Heisenberg systems.

Technical Summary: The Low-Individual-Degree Test Without the Diagonal-Lines Test Is Not Quantum-Sound

More like this