Anyone seen the 'quantum cryptanalysis' thread?

[David A. Wagner]

> 
> 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                                             dawagner at princeton.edu