Class Description

XOR-MIP*[2,1]: MIP*[2,1] With 1-Bit Proofs

Same as MIP*[2,1], but with the further restriction that both provers send only a single bit to the verifier, and the verifier's output is a function of the exclusive-OR of those bits. There should exist 0<a<b<1 such that if the answer is "yes", then for some responses of the provers the verifier accepts with probability at least b, while if the answer is "no", then for all responses of the provers the verifier accepts with probability at most a.

Defined by [CHT+04], whose motivation was a connection to the Bell and CHSH inequalities of quantum physics.

XOR-MIP*[2,1] is contained in NEXP [CHT+04].

XOR-MIP*[2,1] is contained in QIP[2] [Weh06]

Linked From

MIP*: MIP With Quantum Provers

Same as MIP, except that the provers can share arbitrarily many entangled qubits. The verifier is classical, as are all messages between the provers and verifier.

Defined in [CHT+04], where evidence was given suggesting that MIP* does not "obviously" equal NEXP.

MIP* contains NEXP [IV12]. By contrast, MIP, the corresponding class without entanglement, equals NEXP (and even MIP[2,1] with two provers and one round equals NEXP).

Even MIP*[4,poly] and MIP[5,1] contain NEXP [IV12].

MIP*[2,1] contains XOR-MIP*[2,1].

In 2012 it was shown that QMIP = MIP* [RUV12]

In 2020 it was shown that MIP* = RE [JNVWY20].

More about...