This paper proves one of the open problem posed by Beigi et al. in arXiv:1004.0411v2. We consider quantum interactive proof systems where in the beginning the verifier and 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.
This paper proves one of the open problem posed by Beigi et al. in arXiv:1004.0411v2. We consider quantum interactive proof systems where in the beginning the verifier and 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.
Interactive proof systems with a laconic prover, studied by Goldreich, Vadhan, and Wigderson (CC, 2002), capture problems verifiable with logarithmic prover communication in the classical setting. For two-message quantum analogs, even a single-bit prover response contains quantum statistical zero-knowledge (QSZK), introduced by Watrous (FOCS 2002). However, restricting the verifier's question to classical public coins collapses the corresponding class to BQP, as shown by Beigi, Shor, and Watrous (ToC, 2011).
We further study two-message quantum interactive proof systems with a laconic prover. To this end, we introduce the class QIPℓ-bit(2), where ℓ is the length of the prover's response, and establish:
1. A natural complete characterization of QIPℓ-bit(2) by Multi-State Distinguishability. In particular, Quantum State Distinguishability (QSD) is QIPbit-complete. Since QSD is QSZK-hard, our result places QIPℓ-bit(2), for ℓ≥2, in a landscape "just above" QSZK.
2. Easy regimes for QIPℓ-bit(2) collapsing to QSZK. We prove that QSD[a,b] (and thus QIPbit[a,b]) is in QSZK when a(n)−b(n)≥1/O(logn), and combine this with an answer compression from QIPℓ-bit[2,c,s] to QIPbit to obtain another easy regime when 2c>(1+2ℓ/2)s. Remarkably, our improved polarization applies to SD and SZK, resolving an open problem in Sahai and Vadhan (JACM, 2003).
3. Quantum public coins also make the interaction useless: qc-QAM[O(logn)] with constant gap is in BQP, where qc-QAM[ℓ] is a subclass of QIPℓ-bit(2) in which the verifier's question is exactly halves of EPR pairs.
This paper presents stronger methods of achieving perfect completeness in quantum interactive proofs. First, it is proved that any problem in QMA has a two-message quantum interactive proof system of perfect completeness with constant soundness error, where the verifier has only to send a constant number of halves of EPR pairs. This in particular implies that the class QMA is necessarily included by the class QIP1(2)} of problems having two-message quantum interactive proofs of perfect completeness, which gives the first nontrivial upper bound for QMA in terms of quantum interactive proofs. It is also proved that any problem having an m-message quantum interactive proof system necessarily has an (m+1)-message quantum interactive proof system of perfect completeness. This improves the previous result due to Kitaev and Watrous, where the resulting system of perfect completeness requires m+2 messages if not using the parallelization result.
This paper presents stronger methods of achieving perfect completeness in quantum interactive proofs. It is proved that any problem in QMA has a two-message quantum interactive proof system with perfect completeness and constant soundness error, where the verifier has only to send a constant number of halves of EPR pairs. This in particular implies that the class QMA is necessarily included by the class QIP1(2) of problems having two-message quantum interactive proofs with perfect completeness, which gives the first nontrivial upper bound for QMA in terms of quantum interactive proofs. It is also proved that any problem having an m-message quantum interactive proof system necessarily has an (m+1)-message quantum interactive proof system with perfect completeness for every m≥2. This improves the previous construction due to Kitaev and Watrous, which increases the number of messages by two to achieve perfect completeness, if not using the parallelization result.
We introduce quantum interactive proof systems, which are interactive proof systems in which the prover and verifier may perform quantum computations and exchange quantum messages. It is proved that every language in PSPACE has a quantum interactive proof system that requires a total of only three messages to be sent between the prover and verifier and has exponentially small (one-sided) probability of error. It follows that quantum interactive proof systems are strictly more powerful than classical interactive proof systems in the constant-round case unless the polynomial time hierarchy collapses to the second level.
We initiate the study of quantum Interactive Oracle Proofs (qIOPs), a generalization of both quantum Probabilistically Checkable Proofs and quantum Interactive Proofs, as well as a quantum analogue of classical Interactive Oracle Proofs.
In the model of quantum Interactive Oracle Proofs, we allow multiple rounds of quantum interaction between the quantum prover and the quantum verifier, but the verifier has limited access to quantum resources. This includes both queries to the prover's messages and the complexity of the quantum circuits applied by the verifier. The question of whether QMA admits a quantum interactive oracle proof system is a relaxation of the quantum PCP Conjecture.
We show the following two main constructions of qIOPs, both of which are unconditional:
- We construct a qIOP for QMA in which the verifier shares polynomially many EPR pairs with the prover at the start of the protocol and reads only a constant number of qubits from the prover's messages.
- We provide a stronger construction of qIOP for QMA in which the verifier not only reads a constant number of qubits but also operates on a constant number of qubits overall, including those in their private registers. However, in this stronger setting, the communication complexity becomes exponential. This leaves open the question of whether strong qIOPs for QMA, with polynomial communication complexity, exist.
As a key component of our construction, we introduce a novel single prover many-qubits test, which may be of independent interest.
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.