Quantum proof confirms soundness of polynomial test for error checking
Quantum Soundness of a Total-Degree Line-versus-Point Test
Computational Complexity
Summary
When computers that use quantum physics are tested to check if they follow certain math rules, it’s important to be sure the tests work reliably. This paper confirms that a specific test, which compares values on lines and points in a special polynomial way, is trustworthy even with quantum tricks. The authors analyzed how changing coordinates at random helps identify and fix outcomes that don’t match the required degree limit. However, the analysis shows that some aspects still depend on the size of the problem, meaning the test’s reliability isn’t completely independent of complexity.
What this means in practice
- •For quantum computer engineers: Guide design of quantum verification protocols to ensure correctness of computations involving polynomial constraints.
- •For cryptography teams: Inform development of quantum-resistant cryptographic proof systems that use polynomial tests to verify data integrity.
A theory result. No direct application yet.
Authors
Tianrun Zhao
Abstract
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.