Space-efficient Simulations of Quantum Interactive Proofs.

Abstract

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.