This work is licensed under a
Creative Commons License.
|
Tuesday, September 24, 2002
Posted by Lance
Howdy from Canada. I have limited internet access here in Banff so there won't be many posts this week.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.11:23 PM
# 0 comments
Links to this post:
Weblog Home
Archives
