  The assumed computationally difficulty of factoring large integers forms the
basis of security for RSA public-key cryptography, which specifically relies on
products of two large primes or semi-primes. The best-known factoring
algorithms for classical computers run in sub-exponential time. Since integer
factorization is in NP, one can reduce this problem to any NP-hard problem,
such as Boolean Satisfiability (SAT). While reducing factoring to SAT has
proved to be useful for studying SAT solvers, attempting to factor large
integers via such a reduction has not been found to be successful.
  Shor's quantum factoring algorithm factors any integer in polynomial time,
although large-scale fault-tolerant quantum computers capable of implementing
Shor's algorithm are not yet available, so relevant benchmarking experiments
for factoring via Shor's algorithm are not yet possible. In recent years,
however, several authors have attempted factorizations with the help of quantum
processors via reductions to NP-hard problems. While this approach may shed
some light on some algorithmic approaches for quantum solutions to NP-hard
problems, in this paper we study and question the practical effectiveness of
this approach for factoring large numbers. We find no evidence that this is a
viable path toward factoring large numbers, even for scalable fault-tolerant
quantum computers, as well as for various quantum annealing or other special
purpose quantum hardware.
