Class Description

QMIPne: Quantum Multi-Prover Interactive Proofs With No Prior Entanglement

Same as QMIP, except that now the provers have no prior entanglement.

Defined in [KM02], where it was also shown that QMIPne = NEXP. Thus, QMIPne contains QMIPle.

Linked From

QMIP: Quantum Multi-Prover Interactive Proofs

The quantum generalization of MIP, and the multi-prover generalization of QIP.

A quantum multi-prover interactive proof system is the same as a classical one, except that all messages and verifier computations are quantum. As in MIP, there is no communication among the provers; however, the provers share unlimited prior entanglement. The number of provers and number of rounds can both be polynomial in n.

Defined in [KM02].

Shown to be equal to MIP* in [RUV12], and thus RE [JNVWY20].

QMIP contains NEXP simply because MIP* contains NEXP [IV12]. Since we know that NEXP = QMIPne, this tells us that giving the provers unlimited prior entanglement does not make the class less powerful.

More about...


QMIPle: Quantum Multi-Prover Interactive Proofs With Limited Prior Entanglement

Same as QMIP, except that now the provers share only a polynomial number of EPR pairs, instead of an unlimited number.

Defined in [KM02], where it was also shown that QMIPle is contained in NEXP = QMIPne.

More about...