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?


That tells us those problems are in BQP.

This answer describes a way of reducing factoring to SAT.
More elaborate approaches will give reductions from ​ RSA or ECC ​ to SAT.

On the other hand, if there is a polynomial-time reduction
from an NP-hard problem to ​ RSA or ECC ​ ​ then ​ ​ ​ BQP ∩ UP ∩ coUP ​ = ​ NP ​ .


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.