tag:blogger.com,1999:blog-3722233.post113509374802229316..comments2020-01-28T04:52:17.089-05:00Comments on Computational Complexity: Pulling Out The QuantumnessLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger2125tag:blogger.com,1999:blog-3722233.post-1135299185810837042005-12-22T19:53:00.000-05:002005-12-22T19:53:00.000-05:00Quantum zero-knowledge proofs have to deal with th...Quantum zero-knowledge proofs have to deal with this issue, as well. One of the most popular techniques for constructing a simulator to show a protocol is zero-knowledge is "rewinding" : that is, we fix the random string used by a cheating verifier and restart the verifier whenever anything goes "wrong" in the attempted simulation. Then we can try again; because the random string is fixed, we know that so long as the simulator gives the cheating verifier the same messages, it will have the same answers. Then we can look for the "right" place to answer differently on the new run. With a quantum cheating verifier, you can't do this.<BR/><BR/>Nevertheless, there is some recent progress on quantum zero-knowledge proofs. It's a long shot, but maybe that'd be worth looking at in the context of this question.David Molnarnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1135159134228054312005-12-21T04:58:00.000-05:002005-12-21T04:58:00.000-05:00You ask whether there's an oracle relative to whic...You ask whether there's an oracle relative to which NP^BQP is not in BQP^NP. Isn't NP^(AM intersect coAM) just the same as AM? If so, then there's a very good reason why this problem is hard: if BQP is in AM, then NP^BQP is in AM is in BQP^NP. Therefore any such oracle would also yield an oracle relative to which BQP is not in AM.<BR/><BR/>On the other hand, I <I>can</I> give an oracle relative to which BQP^NP and even P^NP are not in NP^BQP. :) (ODDMAXBIT.)Scotthttps://www.blogger.com/profile/12161309448306097395noreply@blogger.com