QIP (complexity) | Wikipedia audio article
Channel: wikipedia tts
Date: 2019-01-13

This is an audio version of the Wikipedia Article:
https://en.wikipedia.org/wiki/QIP_(complexity)


00:03:00 IP



Listening is a more natural way of learning, when compared to reading. Written language only began at around 3200 BC, but spoken language has existed long ago.

Learning by listening is a great way to:
- increases imagination and understanding
- improves your listening skills
- improves your own spoken accent
- learn while on the move
- reduce eye strain

Now learn the vast amount of general knowledge available on Wikipedia through audio (audio article). You could even learn subconsciously by playing the audio while you are sleeping! If you are planning to listen a lot, you could try using a bone conduction headphone, or a standard speaker instead of an earphone.

Listen on Google Assistant through Extra Audio:
https://assistant.google.com/services/invoke/uid/0000001a130b3f91
Other Wikipedia audio articles at:
https://www.youtube.com/results?search_query=wikipedia+tts
Upload your own Wikipedia articles through:
https://github.com/nodef/wikipedia-tts
Speaking Rate: 0.7184659482989203
Voice name: en-US-Wavenet-D


"I cannot teach anybody anything, I can only make them think."
- Socrates


SUMMARY
=======
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 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, 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, 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.