Quantum Soundness of a Total-Degree Line-versus-Point Test

Technical Summary: Quantum Soundness of a Total-Degree Line-versus-Point Test

Problem Statement
This paper addresses the problem of establishing the quantum soundness of a specific low-degree test: the total-degree diagonal line-versus-point test. In the context of entangled provers, soundness requires demonstrating that if a strategy passes the test with high probability, the provers must effectively share a global measurement indexed by a polynomial of bounded degree.

The specific challenge addressed here is the distinction between individual degree (degree in each variable separately) and total degree (sum of degrees across all variables). While soundness for individual-degree tests was established by Ji, Natarajan, Vidick, Wright, and Yuen [1], extending this to total-degree tests is non-trivial because a polynomial of individual degree $d$ can have a total degree as large as $md$ (where $m$ is the number of variables). The test in question samples from a "diagonal" distribution of lines and requires answers consistent with polynomials of total degree at most $d$.

Methodology
The proof strategy relies on a reduction to the individual-degree soundness theorem [1, Theorem 3.10] followed by a degree-reduction step. The methodology proceeds in three main stages:

1. Coordinate Transformation and Reduction:
   The author employs a random invertible change of coordinates using an upper-triangular matrix $T \in GL_m(\mathbb{F}_q)$. By pulling back the strategy along the map $y \mapsto Ty$, the diagonal line distribution of the original test is transformed into a distribution that includes axis-parallel lines. This allows the application of the individual-degree soundness theorem from [1].

   • Key Insight: The transformed strategy yields projective decoders indexed by polynomials of individual degree $d$. However, when mapped back to the original coordinates, these polynomials have a total degree of at most $md$.

2. Bounding Excessive Degree Outcomes:
   The preliminary decoders obtained from the reduction may output polynomials with total degree up to $md$, which exceeds the required bound $d$. To address this, the author utilizes the "uniform-line slice" of the diagonal distribution.

   • Key Insight: Lemma 4 establishes that conditioning the diagonal distribution on specific parameters yields the uniform nondegenerate point-line distribution ($LinePt$).
   • Using this, Lemma 7 (the degree-collapse operator bound) demonstrates that any polynomial of total degree $D > d$ (where $D \leq md < q$) disagrees with every permitted line answer on most points of most lines. Specifically, the probability of agreement is bounded by $3D/q$. Consequently, the weight of outcomes corresponding to polynomials with total degree $> d$ is small.

3. Pruning and Relabeling:
   The final step involves a "pruning" operation. Outcomes corresponding to polynomials with total degree greater than $d$ are relabeled to the zero polynomial.

   • Key Insight: Lemma 8 shows that this deterministic relabeling preserves the projectivity of the measurements and the consistency between the two provers, provided the weight of the pruned outcomes is sufficiently small. The error introduced by this relabeling is bounded by the weight of the excessive-degree outcomes.

Key Contributions

• Quantum Soundness for Total-Degree Tests: The paper proves that the total-degree diagonal line-versus-point test is sound against entangled provers. If a strategy passes with probability $1-\epsilon$, there exist global projective measurements indexed by total-degree polynomials that approximate the provers' local measurements.
• Explicit Error Bounds: The author derives an explicit soundness bound $\nu_{tot}$ that depends on the error $\epsilon$, the field size $q$, the number of variables $m$, and the degree $d$.
• Dimension Dependence: The paper explicitly acknowledges that the resulting soundness bound retains a polynomial dependence on the dimension $m$ (specifically $m^4$), inherited from the individual-degree theorem of [1]. The reduction does not eliminate this dimension dependence.

Results
Theorem 1 states that for a projective strategy passing the degree-$d$ total-degree diagonal line-vs-point test with probability $1-\epsilon$, there exist projective measurements $G_A, G_B$ indexed by total-degree polynomials of degree at most $d$ such that:

1. The provers' point measurements are consistent with the global decoders up to error $\nu_{tot}$.
2. The two global decoders agree with each other up to error $\nu_{tot}$.

The bound is given by:
$$\nu_{tot} = C_0(k + 1)^2 m^4 \left( \epsilon^{c_0} + \left(\frac{d}{q}\right)^{c_0} + e^{-k/(2560000m^2)} \right)$$
where $k \geq md$, $c_0 = 1/40000$, and $C_0$ is a universal constant.

Significance and Claims
The paper claims to provide a rigorous quantum soundness proof for a total-degree test, a necessary component for certain protocols in quantum complexity theory (such as MIP* = RE, though the paper does not explicitly re-derive that result).

The author is modest regarding the limitations of their reduction:

• The reduction does not yield a dimension-independent soundness bound. The $poly(m)$ dependence persists because it is inherent to the individual-degree theorem [1] used as a subroutine.
• The proof relies on the field size $q$ being sufficiently large relative to $md$ (specifically $q > 6md$) to ensure that polynomials of excessive degree are distinguishable from valid answers.

The work serves as a technical bridge, adapting existing individual-degree soundness machinery to the total-degree setting via coordinate transformations and degree-pruning arguments, without inventing new applications or experimental proposals.