John Watrous (University of Calgary):
Quantum Interactive Proof Systems
Interactive proof systems were first introduced in 1985, both as a natural
extension of the class NP and as a model for various cryptographic situations.
An interactive proof system consists of two interacting parties: a
computationally unbounded prover and a polynomial-time verifier. The prover
attempts to prove to the verifier that a given input string satisfies some
property, while the verifier tries to determine the validity of this proof.
Quantum interactive proof systems are interactive proof systems in which the
prover and verifier may perform quantum computations and exchange quantum
messages. In this talk I will survey some of the known facts about
quantum interactive proof systems, and discuss some of the tools that
are helpful for analyzing their properties.