Hot answers tagged

3

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 ​ .



Only top voted, non community-wiki answers of a minimum length are eligible