Computational Complexity

Monday, October 27, 2003

 
Quantum Leaping to Conclusions

Posted by Lance

A quantum computing graduate student sent me email over the weekend. He had thought he had proven some surprising results about the class PP and was wondering if he was making some mistake. After some discussion here was his reply:

Ok I get it. Somehow I jumped to the conclusion that P^PP was PP.
There is one more for your blog: A⊆ B implies B⊆ A^B but not A^B⊆ B (duh!)

He goes on to say he made his quantum leap to conclusions since for the quantum class BQP, P^BQP=BQP, he thought the same property must hold for all classes.

I present this because he suggested it for my weblog and as a public service for those who might make a similar mistake. Yes, in case you were wondering, for reasonable classes A (like A=P), B⊆A^B without needing to assume A⊆B.

9:13 AM # 0 comments

Comment Feeds: This Post All