I've heard lots of interesting results about quantum computing here. John Watrous has the following nifty theorem
about quantum interactive proofs:

Every language with a quantum interactive proof (and in particular all of PSPACE)
has a proof system that works as follows: Merlin sends some qbits to Arthur. Arthur flips a single classical coin
and sends it to Merlin. Merlin then sends over more qbits and Arthur performs some quantum operations and accepts or rejects. Even though Arthur's
only communication is a single random coin, this protocol has perfect completeness and soundness near one-half.

## No comments:

## Post a Comment