Studies in Models of Quantum Proof Systems

Abstract

In this thesis, we study several problems related to quantum proof systems. The simplest quantum proof system is captured by the complexity class QMA. Interestingly, it is not known whether QMA retains its expressive power if we force it to have perfect completeness. Currently, the strongest result towards settling this question is by Kobayashi, Le Gall, and Nishimura. They showed that any QMA protocol can be converted to a one-sided error protocol, in which Arthur and Merlin initially share a constant number of EPR pairs and then Merlin sends his proof to Arthur. Our contribution is a conceptually simpler and more direct proof of the result of Kobayashi et al.

We prove one of the open problems posed by Beigi, Shor, and Watrous. We consider quantum interactive proof systems where, in the beginning, the verifier and the prover send messages to each other, with the combined length of all messages being at most logarithmic (in the input length); and at the end, the prover sends a polynomial-length message to the verifier. We show that this class has the same expressive power as QMA.

We also study two-player non-local games with shared entanglement. We show a parallel repetition theorem for the entangled value of any two-player one-round game, where the questions to the players are drawn independently.