Nondeterministic complexity in quantum and classical models of computation
Purewal, Tarsem Singh
MetadataShow full item record
Nondeterminism has played a fundamental role in our understanding of clas-sical computational complexity. In particular, it led to NP-completeness, whichis one of the most important concepts in the discipline of computer science. Inaddition, when studied in the context of randomization, nondeterminism helpeduncover the PCP theorems, which have increased our understanding of why solu-tions to certain problems are dif cult to approximate.In this thesis we explore this important concept in the context of quantumcomputation. We begin by examining the probabilistic notion of quantum nonde-terminism that was introduced by Adleman, Demarrais and Huang. We surveya result due to Fenner, Homer, Green and Pruim that shows the equality of thecomplexity classes NQP and coC=P. Using this equality and a result of de Wolf'srelating to nondeterministic quantum query complexity, we give a constructionof an oracle relative to which NP and NQP are distinct. In addition, we improvethe best known algebraic characterization of nondeterministic quantum querycomplexity, showing that this complexity measure can be characterized in termsof the minimal degree of real-valued polynomials. Next, we study the characterization of quantum nondeterminism as certi -cate veri cation. In particular, we examine the complexity class QMA which isa class of quantum Merlin-Arthur games. We begin by showing that a problemclaimed by Kitaev, Shen, and Vyalyi to be QMA-complete is, in fact, the language . Next we generalize this technique to show that in one of the circuit character-izations of QMA originally proposed by Watrous, one cannot assume that Arthuruses a clean quantum circuit without trivializing the entire theory. We also provethat Merlin cannot help a nondeterministic quantum Arthur, where Arthur isnondeterministic in the probabilistic sense.Finally, we examine a model of quantum nondeterminism, originally proposedby Aaronson, that is allowed to utilize a resource known as postselection. Weshow that a related, though different, notion of postselection can be appliedin classical nondeterministic computation, and we prove several fundamentalresults about this model.