Source-linked AI summary
Quantum Soundness of a Total-Degree Line-versus-Point Test
Honghao Fu, Nengkun Yu, Tianrun Zhao
TL;DR
The paper addresses quantum soundness for a diagonal line-versus-point test, asking whether entangled provers’ answers can be represented by consistent global polynomial measurements. It constructs polynomial decoders and controls excessive-degree outcomes; the reduction retains the individual-degree theorem’s dimension dependence.
Problem
For entangled provers, the question is whether polynomial-indexed global measurements can agree with point answers and with each other in the diagonal line-versus-point test.
Source: §1 · p. 1Method
A random invertible coordinate change permits use of the individual-degree soundness theorem; the resulting decoders are degree-filtered by relabeling excessive-degree outcomes as zero.
Source: §1 · pp. 1–2Results
The paper proves quantum soundness for the total-degree diagonal line-versus-point test and obtains projective measurements as stated in its theorem.
Source: §3 · p. 5Takeaways & Limitations
The uniform-line slice bounds excessive-degree outcomes, which can then be removed by a common relabeling that preserves projectivity and decoder agreement.
Source: §1 · p. 2, §5 · p. 9The reduction retains the dimension dependence of the cited individual-degree theorem.
Source: §1 · p. 2
Abstract
from arXiv · showhide
We prove quantum soundness of the total-degree diagonal line-vs-point test using the individual-degree soundness theorem of Ji, Natarajan, Vidick, Wright, and Yuen. A random change of coordinates yields projective polynomial decoders of total degree at most $md$. The uniform-line slice of the test bounds the weight of outcomes of degree greater than $d$, which are removed by a common relabeling. This reduction does not yield a dimension-independent soundness bound: the $\operatorname{poly}(m)$ dependence of the individual-degree theorem persists, as discussed in Section 1.2 of arXiv:2009.12982.
1 Introduction
The paper studies quantum soundness for a diagonal line-versus-point test, where global polynomial measurements should agree with point answers. Its reduction constructs polynomial decoders and controls outcomes whose total degree exceeds the test’s bound.
1 Introduction
- For entangled provers, soundness requires polynomial-indexed measurements whose evaluations agree with point answers and whose decoded labels agree with high probability.Source: §1 · p. 1
- A random invertible coordinate change enables use of the individual-degree soundness theorem, whose decoders can have total degree as large as md.Source: §1 · p. 1
- Relabeling excessive-degree outcomes by zero preserves projectivity and decoder agreement, but the reduction retains the cited theorem’s dimension dependence.Source: §1 · p. 2
2 Notation and conventions
The section establishes conventions for polynomial functions, measurements, and the point-line distributions used by the test. It distinguishes individual-degree from total-degree polynomial classes.
2 Notation and conventions
- The notation distinguishes functions represented by reduced polynomials of individual degree at most d from those of total degree at most d.Source: §2 · p. 2
- LinePt denotes sampling a uniform point and then a uniform nondegenerate affine line containing it.Source: §2 · p. 2
- The test has three equally likely branches: point-versus-line in either prover orientation, and point self-consistency.Source: §2 · pp. 3–4
- The convention treats a singleton line as degree zero, so it satisfies any nonnegative degree bound.Source: §2 · pp. 2, 4
3 Main result
The main result is a quantum-soundness theorem for the total-degree diagonal line-versus-point test. Its proof constructs preliminary decoders and then controls and relabels outcomes exceeding the degree bound.
3 Main result
- The paper states a quantum-soundness theorem for the total-degree diagonal line-versus-point test.Source: §3 · p. 5
- The theorem’s stated setup assumes a strategy passing with probability at least 1 − ϵ and a parameter k ≥ md.Source: §3 · p. 5
- The proof first constructs decoders of total degree at most md, then compares them with line measurements and relabels outcomes of degree greater than d.Source: §3 · p. 5
4 Constructing preliminary decoders
A random upper-triangular coordinate change reduces the test to the low-individual-degree setting, yielding projective polynomial decoders. Padding, degree control, and relabeling transfer the decoders back while preserving their consistency properties.
4 Constructing preliminary decoders
- Pulling the strategy back through T and padding degree-d total-degree line answers into the degree-md answer space produces a strategy for the low-individual-degree test.The padding assigns zero operators to extra outcomes and also handles singleton lines; relabeling preserves completeness and projectivity.Source: §4 · p. 6
- An upper-triangular coordinate change preserves diagonal rejection, while the axis-parallel rejection is bounded by the original diagonal rejection conditioned on vi ≠ 0.Averaging over the coordinate changes yields a fixed T with transformed rejection probability at most ρ.Source: §4 · pp. 6–7
- For q > md, the corollary gives projective polynomial measurements whose point-consistency errors and polynomial-label inconsistency are at most νind.The measurements are obtained by applying the individual-degree soundness theorem to the transformed strategy.Source: §4 · pp. 7–8
- An individual-degree-d polynomial has total degree at most md, and composition with T^-1 does not increase that degree.Relabeling by this composition preserves completeness, projectivity, polynomial-label consistency, and the point-consistency errors.Source: §4 · p. 8
5 Controlling total degree
The proof relates diagonal-test consistency to consistency on uniformly sampled point-line pairs, then uses that control to remove decoder outcomes whose total degree exceeds d. The key bridge is the uniform-line slice, whose probability is 1 − q^-m.
5 Controlling total degree
- Conditioned on i = m and v ≠ 0, the induced point-line distribution is exactly LinePt, so the diagonal test contains a uniform-line slice.The slice has probability α = 1 − q^-m.Source: §5 · p. 9
- Uniform-line errors are at most 2m times the corresponding diagonal-test errors, using α^-1 ≤ 2m.The comparison applies to either cross-prover orientation.Source: §5 · pp. 9–11
- For a decoder outcome P of total degree D > d, directions with nonzero top homogeneous part make P|ℓ have degree exactly D, exceeding the permitted line degree.The argument assumes D ≤ md < q.Source: §5 · pp. 11–12
- On the uniform-line slice, each degree-≤d line answer disagrees with such a restriction except at at most D points, while the exceptional directions are bounded using Schwartz–Zippel.The proof conditions on a nonzero direction and handles directions where the top homogeneous part vanishes separately.Source: §5 · p. 12
- The uniform-line inconsistency bounds the weight of excessive-degree decoder outcomes by µr ≤ τr/(1 − β) for each prover.The bound uses the degree-collapse operator estimate and retains the nonnegative bad-outcome terms.Source: §5 · pp. 13–14
- A common deterministic relabeling sends outcomes of degree greater than d to 0, yielding degree-≤d decoders whose three consistency errors obey the stated bound.Deterministic post-processing preserves self-consistency; point-consistency errors increase by at most the excessive-degree outcome mass.Source: §5 · p. 14
6 Proof of the soundness theorem
The soundness proof treats q ≤ 6md with trivial projective decoders, then handles q > 6md by combining the individual-degree decoders with the consistency and pruning lemmas. It bounds the resulting expression by the theorem’s stated νtot.
6 Proof of the soundness theorem
- For q ≤ 6md, trivial projective decoders have perfectly agreeing polynomial labels and point-consistency errors at most 1, so the claimed bound holds.Source: §6 · p. 15
- For q > 6md, the proof applies the individual-degree decoder result, converts its errors to uniform-line errors, and prunes outcomes above degree d.The conversion uses τr ≤ 3νind + 18mϵ; the field-size condition gives 1 − 3md/q > 1/2.Source: §6 · p. 15
- The proof then bounds the resulting error expression by νtot using the stated choices of K and ρ and the parameter inequalities.Source: §6 · p. 15