Same as QRG(2), except that now the verifier can process the yes-prover's answer before preparing the no-prover's question.
Defined in [GW05], where it was also shown that SQG contains QIP.
SQG is contained in EXP [Gut05].
SQG is trivially contained in QRG(4) (and hence EXP).
SQG trivially contains QRG(2) (and hence PSPACE).
SQG is contained in PSPACE [GW10]. Hence SQG = QRG(2) = RG(2) = PSPACE and the addition of quantum information, combined with the ability of the verifier to process the one prover's answer before preparing the other prover's question, has no effect on the complexity of two-turn (one-round) zero-sum games.
Same as RG, except that now the verifier is a BQP machine, and can exchange polynomially many quantum messages with the competing provers.
The two provers are computationally unbounded, but must obey the laws of quantum mechanics. Also, we can assume without loss of generality that the provers share no entanglement, because adversaries gain no advantage by sharing information.
Defined in [Gut05], where it was also shown that QRG is contained in NEXP ∩ coNEXP.
QRG trivially contains RG (and hence EXP), as well as SQG.
QRG is contained in EXP [GW07]. Hence QRG = RG = EXP and finding optimal strategies for zero-sum quantum games is no harder than finding optimal strategies for zero-sum classical games.
Same as QRG, except that now the verifier exchanges exactly k messages with each prover where k is a polynomial-bounded function of the input length. Messages are exchanged in parallel. QRG(k) is the quantum version of RG(k). By definition, QRG(poly) = QRG. See also QRG(1) and QRG(2).
QRG(k) trivially contains RG(k) for each k (and hence PSPACE when ). QRG(4) trivially contains SQG.
QRG(k) is trivially contained in QRG for each k (and hence EXP).
Other than these trivial bounds, very little is known of QRG(k) for intermediate values of k. For example, does QRG(k) = RG(k) for each k?
Same as QRG, except that now the verifier can exchange only two messages with each prover. Messages are exchanged in parallel, so the verifier cannot process the answer from one prover before preparing the question for the other. QRG(2) is the quantum version of RG(2). See also QRG(k).
QRG(2) trivially contains RG(2) (and hence PSPACE).
QRG(2) is trivially contained in SQG (and hence PSPACE). Hence QRG(2) = RG(2) = PSPACE and finding optimal strategies for two-turn zero-sum quantum games is no harder than finding optimal strategies for two-turn zero-sum classical games.
