Clifford Strategies in Interactive Protocols are Classically Simulatable

The complexity class $\text{MIP}^\ast$ consists of all languages decidable by an efficient classical verifier interacting with multiple entanglement-sharing and non-communicating quantum provers. Notably, $\text{MIP}^\ast$ was proved to equal $\text{RE}$, the class of all recursively enumerable languages. We introduce the complexity class $\text{Clifford-MIP}^\ast$, which restricts quantum provers to Clifford operations and classical post-processing of measurement results. We show that strategies in this model can be simulated by classical randomness-sharing provers. In other words, Clifford operations alone do not suffice to generate non-classical correlations in interactive protocols. Consequently, $\text{Clifford-MIP}^\ast = \text{MIP}$, a vastly smaller complexity class compared to $\text{RE}$. Moreover, we resolve an open question posed by Kalai et al. (STOC 2023), by showing that quantum advantage in any single-round non-local game requires at least two provers operating outside the $\text{Clifford-MIP}^\ast$ computational model. This rules out a proposed approach for significantly improving the efficiency of tests for quantum advantage that are based on compiling non-local games into single-prover interactive protocols.