Source-linked AI summary
The Low-Individual-Degree Test Without the Diagonal-Lines Test Is Not Quantum-Sound
Tianrun Zhao
TL;DR
The paper asks whether the diagonal-lines test can be removed while preserving quantum soundness. It constructs a two-prover strategy over every odd prime field that passes the retained checks perfectly. Yet the strategy’s average state-dependent commutator error approaches 2 even as d/q tends to zero, showing that another compatibility mechanism is needed.
Problem
It is unknown whether perfect or near-perfect consistency on axis-parallel lines forces point measurements to approximately commute globally, especially in the large-field regime where d/q tends to zero.
Source: §1 · p. 2Method
The authors construct a two-prover projective strategy for the (m, d) = (2, 2) axis-parallel test over Fq for every odd prime q.
Source: §1 · p. 2Results
The retained checks pass with probability one, yet the average state-dependent commutator error approaches 2 rather than zero as d/q = 2/q tends to zero.
Source: §1 · p. 2Takeaways & Limitations
Axis-parallel consistency alone cannot enforce the global compatibility required for quantum soundness; the diagonal-lines test is one way to supply it, but another explicit compatibility test is not ruled out.
Source: §1 · p. 3The paper does not rigorously treat its proposed extensions: odd prime-power fields are described as straightforward, while even fields are more involved but treatable.
Source: §7 · p. 20
Abstract
from arXiv · showhide
To prove the quantum soundness of the classical low-individual-degree test, the authors of \cite{JNVWY20LID} defined three subtests, namely the axis-parallel lines test, the self-consistency test, and the diagonal-lines test. An interesting question is whether the diagonal-lines test can be removed. In this paper, we show that the diagonal-lines test cannot simply be removed without another compatibility mechanism. Consequently, replacing the "conditional linear functions" by "coordinate deletion functions" in the proof of MIP*=RE, as mentioned in \cite{JNVWY20LID}, does not by itself preserve the required soundness. The authors of \cite{JNVWY20LID} found an example that requires the diagonal-lines test when \((m, d, q) = (2, 2, 4)\); we give an example when \((m, d) = (2, 2)\) and \(q\) is any odd prime.
AI Disclosure
The authors say ChatGPT 5.5 Pro suggested the initial main idea, while the authors are responsible for the mathematical statements and proofs.
AI Disclosure
- ChatGPT 5.5 Pro suggested the initial main idea, and the authors are responsible for the mathematical statements and proofs.The paper was manually written by the authors.Source: AI Disclosure · p. 1
1 Introduction
The paper asks whether axis-parallel line checks and same-point consistency suffice for quantum soundness without diagonal-line checks. It constructs an odd-prime-field counterexample showing that retained checks can pass perfectly while global compatibility fails.
1 Introduction
- Quantum low-degree soundness followed earlier analyses, including the corrected theorem of Ji, Natarajan, Vidick, Wright, and Yuen [JNV+20], which supplies an ingredient for MIP∗= RE [JNV+21].The paper also situates classical low-degree testing in the history of PCPs [AS98, ALM+98].Source: §1 · p. 1
- The diagonal-lines test supplies compatibility between point measurements for arbitrary pairs, which is automatic for a classical global function but not for quantum measurements.The low-individual-degree test also includes axis-parallel line checks and same-point consistency.Source: §1 · pp. 1–2
- An earlier counterexample at (m, d, q) = (2, 2, 4) did not address the large-field regime where d/q tends to zero; the row-and-column magic-square analogy also does not yield that regime [JNV+20].The paper frames its result as extending the obstruction to that setting.Source: §1 · p. 2
- For every odd prime q, the (m, d) = (2, 2) strategy passes both orientations of every axis-parallel line-point check and same-point consistency with probability one, yet its average state-dependent commutator error approaches 2 as d/q = 2/q tends to zero.This extends the obstruction to the large-field regime.Source: §1 · p. 2
- The strategy remains at least 1/54 from every global low-individual-degree polynomial measurement, uniformly over odd primes q.The authors say the obstruction is not merely a failure of one particular commutator argument.Source: §1 · p. 2
- The construction combines finite-group harmonic analysis and quantum-information machinery with point labels whose measurements commute along rows and columns but not when both coordinates differ.On each axis-parallel line, the labels span an isotropic subspace whose joint Fourier measurement gives legal degree-at-most-two answers and exactly refines the point measurements.Source: §1 · pp. 2–3
- Axis-parallel consistency alone cannot enforce the global compatibility required for the usual quantum-soundness conclusion; the diagonal-lines test is one possible compatibility mechanism, but the result does not rule out alternatives.Source: §1 · p. 3
2 Low-individual-degree test
The reduced low-individual-degree test retains axis-parallel line checks and same-point self-consistency, omitting the diagonal-lines test.
2 Low-individual-degree test
- In the axis-parallel lines test, a player receives a point and a coordinate-parallel line through it, then reports a field value at the point and a univariate degree-at-most-d polynomial on the line.The verifier checks consistency between those answers.Source: §2 · p. 3
- In the self-consistency test, both players receive the same uniformly sampled point and the verifier accepts exactly when their field-valued answers agree.Source: §2 · p. 3
- The reduced test chooses the axis-parallel lines test or the self-consistency test with equal probability and omits the diagonal-lines test.Source: §2 · p. 3
- Each player has point measurements with outcomes in Fq and line measurements whose outcomes are univariate polynomials of degree at most d.The strategy is defined using finite-dimensional Hilbert spaces and a shared bipartite state.Source: §2 · p. 3
3 Main Result
The paper asks whether the diagonal-lines test is necessary and shows that the reduced test lacks the corresponding quantum soundness property. Its main theorem gives a perfectly accepted strategy for the reduced test at (m, d) = (2, 2) over every odd prime field.
3 Main Result
- The reduced test does not have the quantum soundness property corresponding to the full test.The full-test soundness guarantee described in the background tends to 1 for fixed m and d as ε tends to zero and q tends to infinity.Source: §3 · p. 4
- For every odd prime q, Theorem 1 gives a two-prover projective strategy for the reduced test at (m, d) = (2, 2) that is accepted with probability 1.Source: §3 · p. 4
4 Construction
The construction uses a q^3-dimensional Hilbert space and a maximally entangled state, then builds point and axis-parallel line measurements from Weyl operators and a label map adapted to the line structure.
4.1 Hilbert-space construction
- The Hilbert space has dimension q^3 and uses the standard orthonormal basis.Source: §4.1 · p. 4
4.2 Quantum-state choice
- The shared state is chosen to be maximally entangled and is also denoted |Φ⟩.Source: §4.2 · p. 4
4.3 Point-measurement construction
- Point measurements are built using generalized Pauli phase and shift operators and their associated Weyl operators.Source: §4.3 · pp. 5, 7
4.4 Line-measurement construction
- The label map makes symplectic pairings vanish on common axis-parallel lines and has degree-at-most-2 restrictions, enabling projective measurements for legal degree-2 line answers.Source: §4.4 · pp. 9, 11
5 Perfect acceptance
The constructed strategy passes the self-consistency and axis-parallel line tests with probability one. The proof establishes perfect agreement at the same point and perfect acceptance in both orientations of the line-point check.
5 Perfect acceptance
- The constructed strategy passes the self-consistency test and axis-parallel lines test with probability 1.Source: §5 · p. 12
5.1 Perfect self-consistency
- Alice and Bob always give the same answer, so the strategy passes self-consistency with probability 1.Source: §5.1 · p. 12
5.2 Perfect axis-parallel acceptance
- Every answer pair violating a = g(u) has probability zero, and both orientations of the axis-parallel line-point test pass with probability 1.Source: §5.2 · pp. 14–15
6 Obstruction to global quantum soundness
The section proves that the constructed point measurements remain a constant distance from consistency with any global function-valued projective measurement. An exact commutator calculation supports this obstruction, which also applies to global measurements outputting low-individual-degree polynomials.
6 Obstruction to global quantum soundness
- Every global function-valued projective measurement has average point-consistency with the constructed measurements bounded away from 1 by a universal constant.Source: §6 · p. 15
6.1 Exact commutator calculation
- The calculation distinguishes commuting measurements when c(u,v)=0 from the linearly independent Weyl-vector case when c(u,v)≠0, then evaluates the resulting sum.Source: §6.1 · pp. 16–17
- For independent uniform u and v, the section establishes an exact averaged commutator; each outcome pair contributes 2(q−1)/q^3 to the sum over q^2 pairs.Source: §6.1 · p. 17
6.2 Constant separation
- The global-measurement obstruction also holds when outcomes are low-individual-degree polynomials, a special class of functions.Source: §6.2 · pp. 18, 20
7 Discussion
The discussion describes extensions of the example to broader parameter settings, while noting that these generalizations are not rigorously treated in the paper.
7 Discussion
- The authors state that the suggested generalizations are not rigorously treated in the paper.Source: §7 · p. 20
- The example can be generalized to prime-power q; the odd-prime-power case is straightforward, while the q=2^k case is more involved but treatable.Source: §7 · p. 20
- The example can extend to m>2 by embedding it in higher-dimensional spaces and to d>2 because lower-degree polynomials are also higher-degree polynomials.Source: §7 · p. 20