Please use this identifier to cite or link to this item:
Title: Studies in Models of Quantum Proof Systems
Keywords: quantum proof systems, QMA, perfect completeness, interactive proofs, non-local games, parallel repetition
Issue Date: 29-Sep-2014
Citation: ATTILA PERESZLENYI (2014-09-29). Studies in Models of Quantum Proof Systems. ScholarBank@NUS Repository.
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.
Appears in Collections:Ph.D Theses (Open)

Show full item record
Files in This Item:
File Description SizeFormatAccess SettingsVersion 
PhD_Thesis.pdf628.03 kBAdobe PDF



Page view(s)

checked on Nov 9, 2018


checked on Nov 9, 2018

Google ScholarTM


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.