QIP=PSPACE=IP
"Interactive proofs" are objects of fundamental significance in
Computational Complexity Theory and are different from the "static
proofs" as they exist in conventional Mathematics. In an Interactive
Proof "an all powerful Prover" tries to convince an efficient "polynomial time
bounded Verifier" of correctness of a claim using interaction between
them. As with any proof system, Interactive Proofs are required to be
"complete", that is true statements have valid proofs, and "sound"
that is false statements cannot be proven. The class of problems
having Interactive Proofs is denoted IP. The well known complexity
class NP can be captured by a one message Interactive Proof with
deterministic Verifier, and hence NP is contained in IP. The "P v/s NP"
question, which is arguably one of the biggest mysteries of modern
times, at a philosophical level asks if it is easier to verify proofs than to come up with them ?
After the complexity class IP was conceived, it was natural to ask how
powerful it is ? After a sequence of surprising results it was discovered
that IP = PSPACE, the latter being the class of problem that can be
solved using polynomial space. In other words, the problems whose
proofs can be efficiently verified in time, are precisely the problems
that can actually be efficiently solved in space. This was how "time"
equated with "space" in the Complexity Theory World.
About a decade ago the quantum analogue of IP, known as QIP was
considered, in which the Verifier is a polynomial time bounded quantum
machine and the Prover and the Verifier can exchange quantum messages
between them. It is easily seen that IP is contained in QIP, since a
classical verifier is also a quantum verifier. It was an open question from then on to understand the power of QIP more precisely, specifically in
comparison to PSPACE. We (Jain, Ji, Upadhyah, Watrous) settle this
long standing question and show that QIP is also contained in PSPACE
and hence QIP = PSPACE = IP. This unfortunately shows that Quantum Interactive Proofs do not have extra power over Classical
Interactive Proofs, such is the world, we got to live in it ! Also in other words, "quantum verification efficiently in time" equates "classical solution efficiently in space".
One of the main techniques used to obtain this result is to exhibit
fast parallel algorithms for solving a certain class of semi-definite programs that
capture the expressive power of Quantum Interactive Proofs. Fast
parallel algorithms for semi-definite programs appear to be a
powerful tool with possibly other interesting consequences as well.
Written by: Rahul Jain, Centre for Quantum Technologies
References:
- QIP=PSPACE ; Rahul Jain, Zhengfeng Ji, Sarvagya Upadhyay, John Watrous - Preprint available here.
