We study three variants of multi-prover quantum Merlin-Arthur proof systems. We first show that the class of problems that can be efficiently verified using polynomially many quantum proofs, each of logarithmic-size, is exactly MQA (also known as QCMA), the class of problems which can be efficiently verified via a classical proof and a quantum verifier. We then study the class BellQMA(poly), characterized by a verifier who first applies unentangled, nonadaptive measurements to each of the polynomially many proofs, followed by an arbitrary but efficient quantum verification circuit on the resulting measurement outcomes. We show that if the number of outcomes per nonadaptive measurement is a polynomially-bounded function, then the expressive power of the proof system is exactly QMA. Finally, we study a class equivalent to QMA(m), denoted SepQMA(m), where the verifier's measurement operator corresponding to outcome "accept" is a fully separable operator across the m quantum proofs. Using cone programming duality, we give an alternate proof of a result of Harrow and Montanaro [FOCS, pp. 633--642 (2010)] that shows a perfect parallel repetition theorem for SepQMA(m) for any m.
We study three variants of multi-prover quantum Merlin-Arthur proof systems. We first show that the class of problems that can be efficiently verified using polynomially many quantum proofs, each of logarithmic-size, is exactly MQA (also known as QCMA), the class of problems which can be efficiently verified via a classical proof and a quantum verifier. We then study the class BellQMA(poly), characterized by a verifier who first applies unentangled, nonadaptive measurements to each of the polynomially many proofs, followed by an arbitrary but efficient quantum verification circuit on the resulting measurement outcomes. We show that if the number of outcomes per nonadaptive measurement is a polynomially-bounded function, then the expressive power of the proof system is exactly QMA. Finally, we study a class equivalent to QMA(m), denoted SepQMA(m), where the verifier's measurement operator corresponding to outcome "accept" is a fully separable operator across the m quantum proofs. Using cone programming duality, we give an alternate proof of a result of Harrow and Montanaro [FOCS, pp. 633--642 (2010)] that shows a perfect parallel repetition theorem for SepQMA(m) for any m.
We study three variants of multi-prover quantum Merlin-Arthur proof systems. We first show that the class of problems that can be efficiently verified using polynomially many quantum proofs, each of logarithmic-size, is exactly \class{MQA} (also known as QCMA), the class of problems which can be efficiently verified via a classical proof and a quantum verifier. We then study the class $\class{BellQMA}(\poly)$, characterized by a verifier who first applies unentangled, nonadaptive measurements to each of the polynomially many proofs, followed by an arbitrary but efficient quantum verification circuit on the resulting measurement outcomes. We show that if the number of outcomes per nonadaptive measurement is a polynomially-bounded function, then the expressive power of the proof system is exactly \class{QMA}. Finally, we study a class equivalent to \class{QMA}(m), denoted $\class{SepQMA}(m)$, where the verifier's measurement operator corresponding to outcome {\it accept} is a fully separable operator across the m quantum proofs. Using cone programming duality, we give an alternate proof of a result of Harrow and Montanaro [FOCS, pp. 633--642 (2010)] that shows a perfect parallel repetition theorem for $\class{SepQMA}(m)$ for any m.
For nearly three decades, the model of interactive proof systems and its variants have been central to many important and exciting developments in computational complexity theory such as exact characterization of some well known complexity classes, development of probabilistically checkable proof systems and theory of hardness of approximation, and formalization of fundamental cryptographic primitives. \n \nOn the other hand, the theory of quantum information, which is primarily concerned with harnessing quantum mechanical features for algorithmic, cryptographic, and information processing tasks has found many applications. In the past three decades, quantum information has been used to develop unconditionally secure quantum cryptography protocols, efficient quantum algorithms for certain problems that are believed to be intractable in classical world, and communication efficient protocols. \n \nIn this thesis, we study the impact of quantum information on the models of interactive proof systems and their multi-prover variants. We study various quantum models and explore two questions. The first question we address pertains to the expressive power of such models with or without resource constraints. The second question is related to error reduction technique of such proof systems via parallel repetition. \n \nThe question related to the expressive power of models of quantum interactive proof systems and their variants lead us to the following results. \n \n(1) We show that the expressive power of quantum interactive proof systems is exactly PSPACE, the class of problems that can be solved by a polynomial-space deterministic Turing machines and that also admit a classical interactive proof systems. This result shows that in terms of complexity-theoretic characterization, both the models are equivalent. The result is obtained using an algorithmic technique known as the matrix multiplicative weights update method to solve a semidefinite program that characterizes the success probability of the quantum prover. \n\t \n(2) We show that polynomially many logarithmic-size unentangled quantum proofs are no more powerful than a classical proof if the verifier has the ability to process quantum information. This result follows from an observation that logarithmic-size quantum states can be efficiently represented classically and such classical representation can be used to efficiently generate the quantum state. \n\t \n(3) We also establish that the model of multi-prover quantum Merlin Arthur proof system, where the verifier is only allowed to apply nonadaptive unentangled measurement on each proof and then a quantum circuit on the classical outcomes, is no more powerful than QMA under the restriction that there are only polynomial number of outcomes per proof. This result follows from showing that such proof systems also admit a QMA verification procedure. \n \nThe question related to error reduction via parallel repetition lead us to following results on a class of two-prover one-round games with quantum provers and a class of multi-prover QMA proof systems. \n \n(1) We establish that for a certain class of two-prover one-round games known as XOR games, admit a perfect parallel repetition theorem in the following sense. When the provers play a collection of XOR games, an optimal strategy of the provers is to play each instance of the collection independently and optimally. In particular, the success probability of the quantum provers in the n-fold repetition of an XOR game G with quantum value w(G) is exactly (w(G))^n. \n\t \n(2) We show a parallel repetition theorem for two-prover one-round unique games. More specifically, we prove that if the quantum value of a unique game is 1-e, then the quantum value of n-fold repetition of the game is at most (1-e^2/49)^n. We also establish that for certain class of unique games, the quantum value of the n-fold repetition of the game is at most (1-e/4)^n. For the special case of XOR games, our proof technique gives an alternate proof of result mentioned above. \n\t \n3. Our final result on parallel repetition is concerned with SepQMA(m) proof systems, where the verifier receives m unentangled quantum proofs and the measurement operator corresponding to outcome "accept" is a fully separable operator. We give an alternate proof of a result of Harrow and Montanaro [HM10] that states that perfect parallel repetition theorem holds for such proof systems. \n \nThe first two results follow from the duality of semidefinite programs and the final result follows from cone programming duality.
BellQMA protocols are a subclass of multi-prover quantum Merlin-Arthur protocols in which the verifier is restricted to perform nonadaptive,unentangled measurements on the quantum states received from each Merlin. In this paper, we prove that m-clause 3-SAT instances have BellQMA proofs of satisfiability with constant soundness gap, in which O(sqrt(m)polylog(m)) Merlins each send O(log m) qubits to Arthur. Our result answers a question of Aaronson et al., who gave a protocol with similar parameters that used entangled measurements; the analysis of our protocol is significantly simpler than that of Aaronson et al. Our result also complements recent work of Brandao, Christandl, and Yard, who showed upper bounds on the power of multiprover quantum proofs with unentangled but adaptive (LOCC) measurements.
This paper studies multiple-proof quantum Merlin-Arthur (QMA) proof systems in the setting when the completeness-soundness gap is small. Small means that we only lower-bound the gap with an inverse-exponential function of the input length, or with an even smaller function. Using the protocol of Blier and Tapp [arXiv:0709.0738], we show that in this case the proof system has the same expressive power as non-deterministic exponential time (NEXP). Since single-proof QMA proof systems, with the same bound on the gap, have expressive power at most exponential time (EXP), we get a separation between single and multi-prover proof systems in the 'small-gap setting', under the assumption that EXP is not equal to NEXP. This implies, among others, the nonexistence of certain operators called disentanglers (defined by Aaronson et al. [arXiv:0804.0802]), with good approximation parameters. We also show that in this setting the proof system has the same expressive power if we restrict the verifier to be able to perform only Bell-measurements, i.e., using a BellQMA verifier. This is not known to hold in the usual setting, when the gap is bounded by an inverse-polynomial function of the input length. To show this we use the protocol of Chen and Drucker [arXiv:1011.0716]. The only caveat here is that we need at least a linear amount of proofs to achieve the power of NEXP, while in the previous setting two proofs were enough. We also study the case when the proof-lengths are only logarithmic in the input length and observe that in some cases the expressive power decreases. However, we show that it doesn't decrease further if we make the proof lengths to be even shorter.
Interactive proof systems form an important complexity model that has been central to many prominent results in computational complexity theory, such as those on probabilistically checkable proofs, hardness of approximation, and fundamental cryptographic primitives. In this thesis, we study the quantum-enhanced version of interactive proof systems, in which each party has access to quantum computing resources. We focus on its power and limitations, which lead us to the following results. (*) We provide an alternative and conceptually simpler proof of Jain et al.’s recent breakthrough result, which demonstrates that the expressive power of quantum interactive proof systems coincides with that of its classical counterpart, and therefore PSPACE. (*) We determine the complexity of several variants of quantum competing-prover interactive proof systems, which introduce zero-sum games into interactive proof systems. In particular, we prove that the complexity class of two-turn quantum refereed games coincides with PSPACE, answering an important open problem of Jain et al.’s. Our result suggests that a more general model called double quantum interactive proof systems coincides with PSPACE, which subsumes and unifies all previous results on short refereed games. (*) We contribute to the study of two-prover quantum Merlin-Arthur games (QMA(2)), which exhibit an intriguing tradeoff between an intrinsic quantum ingredient, entanglement, and computational power. We prove a PSPACE upper bound for a variant of QMA(2) that is to date the most general one known in PSPACE. We also provide a quasi-polynomial time algorithm for optimizing linear functions over separable states, giving an alternative to the one proposed by Brandao et al. Our main technical contribution behind the above results is the equilibrium value method for obtaining space-efficient algorithms for a class of optimization problems that arise naturally in quantum computation. We also contribute to QMA-complete problems, where we demonstrate that the “Non-Identity Check” problem remains QMA-complete on circuits of poly-logarithmic depths, improving upon polynomial depths from previous results.