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@princeton.edu