About the EventInteractive 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 quantumenhanced 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 its classical counterpart, and therefore PSPACE.
(*) We solve the complexity of several variants of quantum competingprover interactive proof systems, which introduce zerosum games into interactive proof systems. In particular, we prove that the complexity class of twoturn 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 twoprover quantum MerlinArthur games (QMA(2)), which exhibit an intriguing correlation 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 quasipolynomial time algorithm for optimizing a linear function over separable states, giving an alternative to the one proposed by Brandao et al.
Our main technical contribution behind above results is the equilibrium value method for obtaining spaceefficient algorithms for a class of optimization problems that arise naturally in quantum computation.
We also contribute to QMAcomplete problems, where we demonstrate that the “Non
Identity Check” problem remains QMAcomplete on circuits of polylogarithmic depths, improving upon polynomial depths from previous results.
