Please note: This master’s thesis presentation will be given online.
Soumik
Ghosh, Master’s
candidate
David
R.
Cheriton
School
of
Computer
Science
This thesis studies one-turn quantum refereed games, which are abstract zero-sum games with two competing computationally unbounded quantum provers and a computationally bounded quantum referee. The provers send quantum states to the referee, who plugs the two states into his quantum circuit, measures the output of the circuit in the standard basis, and declares one of the two players as the winner depending on the outcome of the measurement. The complexity class $\class{QRG(1)}$ comprises of those promise problems for which there exists a one-turn quantum refereed game such that one of the players wins with high probability for the yes-instances, and the other player wins with high probability for the no-instances, irrespective of the opponent’s strategy. $\class{QRG(1)}$ is a generalization of $\class{QMA}$ (or $\class{co-QMA}$), and can informally be viewed as $\class{QMA}$ with a no-prover (or $\class{co-QMA}$ with a yes-prover).
We have given a full characterization of $\class{QRG(1)}$, starting with appropriate definitions and known results, and building on to two new results about this class. Previously, the best known upper bound on $\class{QRG(1)}$ was $\class{PSPACE}$. We have proved that if one of the provers is completely classical, sending a classical probability distribution instead of a quantum state, the new class, which we name $\class{CQRG(1)}$, is contained in $\exists \cdot \class{PP}$ (non-deterministic polynomial-time operator applied to the class $\class{PP}$). We have also defined another restricted version of $\class{QRG(1)}$ where both provers send quantum states, but the referee measures one of the quantum states first, and plugs the classical outcome into the measurement, along with the other prover’s quantum state, into a quantum circuit, before measuring the output of the quantum circuit in the standard basis. The new class, which we name $\class{MQRG(1)}$, is contained in $\class{P}\cdot\class{PP}$ (the probabilistic polynomial time operator applied to $\class{PP}$). $\exists \cdot \class{PP}$ is contained in $\class{P} \cdot \class{PP}$, which is, in turn, contained in $\class{PSPACE}$. Hence, our results give better containments than $\class{PSPACE}$ for restricted versions of $\class{QRG(1)}$.