International Association
for Cryptologic Research

MIP* is the class of languages decidable by an efficient classical verifier interacting with multiple quantum provers that share entangled qubits but cannot communicate. Notably, MIP* was proved to equal RE, the class of all recursively enumerable languages. We introduce the complexity class Clifford–MIP*, which restricts quantum provers to Clifford operations and classical post-processing of measurement results, while still allowing shared entangled qubits in any quantum state. We show that any strategy in this model can be simulated by classical provers with shared random bits, and therefore admits a local hidden-variable description. Consequently, Clifford–MIP*=MIP, a vastly smaller complexity class compared to 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 Clifford–MIP* computational model. This rules out a proposed approach for significantly improving the efficiency of quantum advantage tests that are based on compiling non-local games into single-prover interactive protocols.