Incomputational complexity theory, the classQIP (which stands forQuantum Interactive Proof) is thequantum computing analogue of the classicalcomplexity classIP, which is the set of problems solvable by aninteractive proof system with apolynomial-time verifier and one computationally unbounded prover. Informally, IP is the set oflanguages 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 aBPP 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 aBQP machine.
By restricting the number of messages used in the protocol to at mostk, we get the complexity class QIP(k). QIP and QIP(k) were introduced byJohn 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 isBQP, QIP(1), which isQMA, QIP(2) and QIP.
Kitaev and Watrous also showed that QIP is contained inEXP, the class of problems solvable by adeterministic Turing machine in exponential time.[2] QIP(2) was then shown to be contained inPSPACE, 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 resultIP = PSPACE.
| General | |||||||||
|---|---|---|---|---|---|---|---|---|---|
| Theorems | |||||||||
| Quantum communication |
| ||||||||
| Quantum algorithms | |||||||||
| Quantum complexity theory | |||||||||
| Quantum processor benchmarks | |||||||||
| Quantum computing models | |||||||||
| Quantum error correction | |||||||||
| Physical implementations |
| ||||||||
| Quantum programming | |||||||||
