PSPACE has 2-round quantum interactive proof systems

Details PSPACE has 2-round quantum interactive proof systems PSPACE has 2-round quantum interactive proof systems

1999-01-27

arxiv.org/abs/cs/9901015v1

Computer Science

Computational Complexity

13 pages

Scientific paper

In this paper we consider quantum interactive proof systems, i.e., interactive proof systems in which the prover and verifier may perform quantum computations and exchange quantum messages. It is proved that every language in PSPACE has a quantum interactive proof system that requires only two rounds of communication between the prover and verifier, while having exponentially small (one-sided) probability of error. It follows that quantum interactive proof systems are strictly more powerful than classical interactive proof systems in the constant-round case unless the polynomial time hierarchy collapses to the second level.

Affiliated with

Also associated with

No associations

Rating

PSPACE has 2-round quantum interactive proof systems does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with PSPACE has 2-round quantum interactive proof systems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and PSPACE has 2-round quantum interactive proof systems will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-598925