If quantum computers operate in BQP and (using Shor's algorithm) they are able to factor large integers and break the discrete log problem, what does that tell us about the complexity class of these problems?
I just read an article that claims that it is unlikely that RSA or ECC will ever be reduced to NP-complete problems, but given Shor's algorithm isn't that impossible? Or what about the other way: if someone does find such a reduction, does that tell us anything about the relation of BQP and NP?