Quantum soundness of a variant of the multilinearity test (i.e. the case \(s=1\) ) played with three entangled provers is at the heart of the proof of \(\mathsf {NEXP}\subseteq \mathsf {MIP}^*\)  [1]}. This analysis is extended to general degree \(s\)  in [2]}, and to the case of two provers in [3]}. However, it was later discovered [4]} that the argument contained in [2]} contains a mistake. The case of two provers and general \(s\)  is essential in
the proof of the recent characterization \(\mathsf {MIP}^* = \mathsf {RE}\) , which shows that every recursively enumerable language (including the Halting problem) has an interactive proof in the entangled provers model [6]}. Our main contribution is a proof of soundness of the low individual degree test that is used in the proof of \(\mathsf {MIP}^*=\mathsf {RE}\) .The present paper is an updated version of an earlier arXiv posting by the same authors [7]}, which was posted after the mistake in the earlier works had been discovered. We discuss additional improvements compared to that earlier draft below. We show that quantum provers who succeed with high probability in the test must still – in a certain sense – respond according to a low individual degree polynomial.
Informally, our main result is the following:
