[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Anyone seen the 'quantum cryptanalysis' thread?
>
> As I'm sure somebody else has pointed out somewhere along this thread, the
> ability to simultaneously analyze a superposition of an arbitrarilly large
> subset of all possible imputs (as our theoretical quantum cryptanalytic
> device might) implies to ability to solve, in polynomial time, any
> exponential time problem.
>
I just wanted to point out that I'm not sure this is true.
I might be wrong; I'm a total newbie here. However, my impression
was that it is *not* known that "anything in NP is solvable in
quantum polytime (BQP)".
I think it's been shown that, relative to a random oracle, it's not
true that NP is contained in BQP. Then again, I'm told that oracle
results are often misleading and usually not worth a bean. <shrug>
I don't know much about this stuff. :-(
[This oracle result is mentioned in Schor's paper.]
Hopefully someone more clueful than I will explain this stuff :-)
-------------------------------------------------------------------------------
David Wagner [email protected]