Low individual degree test needs diagonal lines for quantum soundness
The Low-Individual-Degree Test Without the Diagonal-Lines Test Is Not Quantum-Sound
Computational Complexity
Summary
When testing certain mathematical properties to verify quantum systems, a set of tests is used to ensure correctness. The authors show that removing one of these tests called the diagonal-lines test breaks the ability to reliably detect errors in quantum settings. This means a key step in previous quantum verification proofs can’t be simplified without extra mechanisms. The paper provides examples demonstrating the necessity of the diagonal-lines test under certain conditions.
What this means in practice
- •For quantum protocol developers: Avoid simplifying verification steps in quantum proof systems that ensure security and correctness in interactive proofs.
- •For cryptographic protocol designers: Design sound verification methods that reliably detect cheating in protocols relying on quantum proofs or entanglement.
A theory result. No direct application yet.
Authors
Tianrun Zhao
Abstract
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.