On the Power of Clifford Strategies in Interactive Protocols

The Gottesman-Knill theorem shows that Clifford circuits operating on stabilizer states can be efficiently simulated classically. However, in the setting of interactive protocols, it has remained unclear whether Clifford strategies with shared entanglement between provers offer any advantage over classical ones. We provide a negative answer to this question, demonstrating that even when Clifford provers are additionally allowed to perform general classical operations on measured qubits $-$ a computational model for which we introduce the complexity class $\text{Clifford-MIP}^\ast$ $-$ there is no advantage over classical strategies. Our results imply that $\text{Clifford-MIP}^\ast = \text{MIP}$. Furthermore, we utilize our findings to resolve an open question posed by Kalai et al. (STOC 2023). We show that quantum advantage in any non-local game requires at least two quantum provers operating outside the $\text{Clifford-MIP}^\ast$ computational model. This rules out a suggested approach for significantly improving the efficiency of tests for quantum advantage that are based on compiling non-local games.