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.
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 poly(m) dependence of the individual-degree theorem persists, as discussed in Section 1.2 of arXiv:2009.12982.
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.
Low degree tests play an important role in classical complexity theory, serving as basic ingredients in foundational results such as MIP=NEXP [BFL91] and the PCP theorem [AS98,ALM+98]. Over the last ten years, versions of these tests which are sound against quantum provers have found increasing applications to the study of nonlocal games and the complexity class~MIP∗. The culmination of this line of work is the result MIP∗=RE [arXiv:2001.04383]. One of the key ingredients in the first reported proof of MIP∗=RE is a two-prover variant of the low degree test, initially shown to be sound against multiple quantum provers in [arXiv:1302.1242]. Unfortunately a mistake was recently discovered in the latter result, invalidating the main result of [arXiv:1302.1242] as well as its use in subsequent works, including [arXiv:2001.04383]. We analyze a variant of the low degree test called the low individual degree test. Our main result is that the two-player version of this test is sound against quantum provers. This soundness result is sufficient to re-derive several bounds on~MIP∗ that relied on [arXiv:1302.1242], including MIP∗=RE.
For general max-k-XORSAT with k≥3, no polynomial-time algorithm can do substantially better than random guessing on worst-case instances unless P=NP: approximating beyond the random-assignment value of 1/2 is NP-hard. The picture changes when each variable appears in at most D constraints. In that bounded-degree setting, polynomial-time algorithms can provably beat the random baseline by an additive amount of order 1/D. For Boolean instances, this scaling is known to be optimal: the matching hardness result is due to Trevisan, while the corresponding algorithmic guarantee was established by Barak et al. Whether the same holds over general finite fields, and what it implies for quantum algorithms, has not been established. We make this connection explicit and extend the hardness to max-Ek-LINSAT(q,r) with bounded degree D and over arbitrary finite fields Fq, proving that it is NP-hard to exceed r/q+Oq,r(1/D). These results provide the complexity-theoretic benchmark for the bounded-degree instances targeted by decoded quantum interferometry (DQI), QAOA, and classical heuristics. Any quantum advantage on bounded-degree instances is therefore confined to the constant prefactor. We further show that in the context of DQI and on (k,D)-regular instances, this prefactor is sensitive to the nature of the decoder: DQI with classical decoders faces an information-theoretic 1/DlogD barrier that prevents it from matching the hardness scaling, while DQI with quantum decoders is compatible with the 1/D scaling -- identifying quantum decoding as the key ingredient for matching the complexity-theoretic scaling with DQI.
A locally testable code is an error-correcting code that admits very efficient probabilistic tests of membership. Tensor codes provide a simple family of combinatorial constructions of locally testable codes that generalize the family of Reed-Muller codes. The natural test for tensor codes, the axis-parallel line vs. point test, plays an essential role in constructions of probabilistically checkable proofs. We analyze the axis-parallel line vs. point test as a two-prover game and show that the test is sound against quantum provers sharing entanglement. Our result implies the quantum-soundness of the low individual degree test, which is an essential component of the MIP* = RE theorem. Our proof also generalizes to the infinite-dimensional commuting-operator model of quantum provers.
Decoded quantum interferometry (DQI) and its Hamiltonian extension (HDQI) prepare states whose amplitudes are low-degree polynomials of an objective, using Fourier transforms and coherent decoding. We recast this approach as quantum state transduction through algebra homomorphisms. We transfer an efficiently preparable operator state of a degree-D polynomial in a source Hamiltonian HA to the corresponding polynomial state of a target Hamiltonian HB=π(HA), where π is a unital ∗-homomorphism between the finite-dimensional source and target C∗-algebras. The transduction uses operator Fourier transforms and relative decoding to recover source operators rather than individual term-selection labels. The relative distance drel is the first degree at which source and target traces disagree. We prove that 2D<drel is equivalent to preserving all inner products between degree-D polynomials. Moreover, drel≥dord, where dord is the ordinary distance used in (H)DQI, and we give families with dord=O(1) but drel=Θ(n) and efficient decoders. Our framework replaces the complicated pilot state preparation by the more modular task of preparing a source polynomial state. DQI and HDQI arise as relation-free special cases. The framework accommodates nonuniform coefficients and noncommuting interactions and extends to fermionic, qudit, and bosonic systems, with applications to approximate optimization and Gibbs sampling. As evidence of advantages, for a nonlinear pairwise variant of optimal polynomial intersection where constant dord limits DQI-style preparations, relative decoding yields an ideal quantum score of 0.643 versus 0.606 for the best tested classical heuristic, a gap exceeding 3 percentage points.
A locally testable code is an error-correcting code that admits very efficient probabilistic tests of membership. Tensor codes provide a simple family of combinatorial constructions of locally testable codes that generalize the family of Reed-Muller codes. The natural test for tensor codes, the axis-parallel line vs. point test, plays an essential role in constructions of probabilistically checkable proofs. We analyze the axis-parallel line vs. point test as a two-prover game and show that the test is sound against quantum provers sharing entanglement. Our result implies the quantum-soundness of the low individual degree test, which is an essential component of the MIP* = RE theorem. Our proof also generalizes to the infinite-dimensional commuting-operator model of quantum provers.