In
computational complexity theory
In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and explores the relationships between these classifications. A computational problem ...
, the class QIP (which stands for Quantum Interactive Proof) is the
quantum computing
A quantum computer is a computer that exploits quantum mechanical phenomena. On small scales, physical matter exhibits properties of wave-particle duality, both particles and waves, and quantum computing takes advantage of this behavior using s ...
analogue of the classical
complexity class
In computational complexity theory, a complexity class is a set (mathematics), set of computational problems "of related resource-based computational complexity, complexity". The two most commonly analyzed resources are time complexity, time and s ...
IP, which is the set of problems solvable by an
interactive proof system with a
polynomial-time
In theoretical computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations p ...
verifier and one computationally unbounded prover. Informally, IP is the set of
language
Language is a structured system of communication that consists of grammar and vocabulary. It is the primary means by which humans convey meaning, both in spoken and signed language, signed forms, and may also be conveyed through writing syste ...
s 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, who along with Kitaev proved in a later paper
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 Exp or EXP may stand for:
* Exponential function, in mathematics
* Expiry date of organic compounds like food or medicines
* Experience point
An experience point (often abbreviated as exp or XP) is a unit of measurement used in some tabletop r ...
, the class of problems solvable by a
deterministic Turing machine in exponential time.
QIP(2) was then shown to be contained in
PSPACE
In computational complexity theory, PSPACE is the set of all decision problems that can be solved by a Turing machine using a polynomial amount of space.
Formal definition
If we denote by SPACE(''f''(''n'')), the set of all problems that can ...
, the set of problems solvable by a deterministic Turing machine in polynomial space. Both results were subsumed by the 2009 result that QIP is contained in PSPACE,
which also proves that QIP = IP = PSPACE, since PSPACE is easily shown to be in QIP using the result
IP = PSPACE.
References
External links
*
{{ComplexityClasses
Probabilistic complexity classes
Quantum complexity theory