QIP (complexity)

In computational complexity theory, the class QIP (which stands for Quantum Interactive Proof) is the quantum computing analogue of the classical complexity class IP, which is the set of problems solvable by an interactive proof system with a polynomial-time verifier and one computationally unbounded prover. Informally, IP is the set of languages for which a computationally unbounded prover can convince a polynomial-time verifier to accept when the input is in the language (with high probability) and cannot convince the verifier to accept when the input is not in the language (again, with high probability). In other words, the prover and verifier may interact for polynomially many rounds, and if the input is in the language the verifier should accept with probability greater than 2/3, and if the input is not in the language, the verifier should be reject with probability greater than 2/3. In IP, the verifier is like a BPP machine. In QIP, the communication between the prover and verifier is quantum, and the verifier can perform quantum computation. In this case the verifier is like a BQP machine.

By restricting the number of messages used in the protocol to at most k, we get the complexity class QIP(k). QIP and QIP(k) were introduced by John Watrous,[1] who along with Kitaev proved in a later paper[2] that QIP = QIP(3), which shows that 3 messages are sufficient to simulate a polynomial-round quantum interactive protocol. Since QIP(3) is already QIP, this leaves 4 possibly different classes: QIP(0), which is BQP, QIP(1), which is QMA, QIP(2) and QIP.

Kitaev and Watrous also showed that QIP is contained in EXP, the class of problems solvable by a deterministic Turing machine in exponential time.[2] QIP(2) was then shown to be contained in PSPACE, the set of problems solvable by a deterministic Turing machine in polynomial space.[3] Both results were subsumed by the 2009 result that QIP is contained in PSPACE,[4] which also proves that QIP = IP = PSPACE, since PSPACE is easily shown to be in QIP using the result IP = PSPACE.

  1. ^ Watrous, John (2003), "PSPACE has constant-round quantum interactive proof systems", Theor. Comput. Sci., 292 (3), Essex, UK: Elsevier Science Publishers Ltd.: 575–588, doi:10.1016/S0304-3975(01)00375-9, ISSN 0304-3975
  2. ^ a b Kitaev, Alexei; Watrous, John (2000), "Parallelization, amplification, and exponential time simulation of quantum interactive proof systems", STOC '00: Proceedings of the thirty-second annual ACM symposium on Theory of computing, ACM, pp. 608–617, ISBN 978-1-58113-184-0
  3. ^ Jain, Rahul; Upadhyay, Sarvagya; Watrous, John (2009), "Two-Message Quantum Interactive Proofs Are in PSPACE", FOCS '09: Proceedings of the 2009 50th Annual IEEE Symposium on Foundations of Computer Science, IEEE Computer Society, pp. 534–543, ISBN 978-0-7695-3850-1
  4. ^ Jain, Rahul; Ji, Zhengfeng; Upadhyay, Sarvagya; Watrous, John (2010), "QIP = PSPACE", STOC '10: Proceedings of the 42nd ACM symposium on Theory of computing, ACM, pp. 573–582, ISBN 978-1-4503-0050-6