Quantum Interactive Protocol
Encyclopedia
In computational complexity theory
, the class QIP, which stands for Quantum Interactive Polynomial time, 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 language
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 also proved in the same 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 later showed that QIP is contained in EXP
, the class of problems solvable by a deterministic Turing machine in exponential time. QIP(2) was then shown to be contained in PSPACE
, 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.
Computational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...
, the class QIP, which stands for Quantum Interactive Polynomial time, is the quantum computing analogue of the classical complexity class
Complexity class
In computational complexity theory, a complexity class is a set of problems of related resource-based complexity. A typical complexity class has a definition of the form:...
IP
IP (complexity)
In computational complexity theory, the class IP is the class of problems solvable by an interactive proof system. The concept of an interactive proof system was first introduced by Shafi Goldwasser, Silvio Micali, and Charles Rackoff in 1985...
, which is the set of problems solvable by an interactive proof system
Interactive proof system
In computational complexity theory, an interactive proof system is an abstract machine that models computation as the exchange of messages between two parties. The parties, the verifier and the prover, interact by exchanging messages in order to ascertain whether a given string belongs to a...
with a polynomial-time verifier and one computationally unbounded prover. Informally, IP is the set of language
Formal language
A formal language is a set of words—that is, finite strings of letters, symbols, or tokens that are defined in the language. The set from which these letters are taken is the alphabet over which the language is defined. A formal language is often defined by means of a formal grammar...
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
BQP
In computational complexity theory BQP is the class of decision problems solvable by a quantum computer in polynomial time, with an error probability of at most 1/3 for all instances...
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
John Watrous (computer scientist)
John Harrison Watrous is an associate professor of computer science at the David R. Cheriton School of Computer Science at the University of Waterloo, a member of the Institute for Quantum Computing, an affiliate member of the Perimeter Institute for Theoretical Physics and a Fellow of the Canadian...
, who also proved in the same 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
BQP
In computational complexity theory BQP is the class of decision problems solvable by a quantum computer in polynomial time, with an error probability of at most 1/3 for all instances...
, QIP(1), which is QMA
QMA
In computational complexity theory, QMA, which stands for Quantum Merlin Arthur, is the quantum analog of the deterministic complexity class NP or the probabilistic complexity class MA...
, QIP(2) and QIP.
Kitaev and Watrous later showed that QIP is contained in EXP
EXPTIME
In computational complexity theory, the complexity class EXPTIME is the set of all decision problems solvable by a deterministic Turing machine in O time, where p is a polynomial function of n....
, the class of problems solvable by a deterministic Turing machine in exponential time. QIP(2) was then shown to be contained in PSPACE
PSPACE
In computational complexity theory, PSPACE is the set of all decision problems which can be solved by a Turing machine using a polynomial amount of space.- Formal definition :...
, 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.