The class of problems for which there exists a BQP machine M such that:
In other words, it's the same as QRG(k) for , the class of problems that admit quantum interactive proofs with competing provers in which there's no communication from the verifier back to the provers. QRG(1) is the quantum version of RG(1).
Defined in [JW09], where it was shown that QRG(1) is contained in PSPACE .
QRG(1) trivially contains QMA (and indeed PQRG(1)).
QRG(1) is trivially contained in QRG(2) (and hence PSPACE).
Like QPH, but the provers may entangle their earlier proofs with their later proofs.
Defined in [GY24], and was shown to collapse to QRG(1).
The hierarchy collapses even with a polynomial number of rounds, whereas PH with polynomial rounds equals PSPACE.
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?
