QIP (complexity)
In
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
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
.
References
- ISSN 0304-3975
- ^ ISBN 978-1-58113-184-0
- ISBN 978-0-7695-3850-1
- ISBN 978-1-4503-0050-6
External links
- Complexity Zoo: QIP