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)".
Well its quite possible that I am wrong since I didn't exactly have the easiest time reading the papers on the subject. But this is my reasoning: If you can create a machine that gives you a yes or no result (yes at least one of the subset of possible inputs entered into the machine contains the properties you are looking for [i.e. does not destructively interfere], or no there aren't any) then you can construct an quantum computer that tests for the property(s) the correct answer must have (in the case of factoring, the machine will test whether or not inputs divide the modulus). You can now repeatedly enter as inputs superpositions of inputs that include precisely half of all inputs that might (given the information that has already been gathered) be correct). You will now be able to mount a brute force attack searching through 2^n possibilities in order n time. It should be possible to nest these machines (although admitedly this does nasty things to the physical complexity of the quantum computer. It doesn't seem like the complexity would grow exponentially in the case of nesting [in fact it seems like it would go quadratically with the nesting level] but I'd have to think about it some more before I could claim to be confident of that.) thus allowing us to reduce any problem of time complexity e^X(n) (where X is either a polynomial in n or of the form e^X(n) [this goes on recursively]) to a problem of polynomial time complexity. JWS