Mosca Michele, Verschoor Sebastian R
Institute for Quantum Computing, University of Waterloo, Waterloo, Canada.
Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Canada.
Sci Rep. 2022 May 14;12(1):7982. doi: 10.1038/s41598-022-11687-7.
The computational difficulty of factoring large integers forms the basis of security for RSA public-key cryptography. The best-known factoring algorithms for classical computers run in sub-exponential time. The integer factorization problem can be reduced to the Boolean Satisfiability problem (SAT). While this reduction has proved to be useful for studying SAT solvers, large integers have not been factored via such a reduction. Shor's quantum factoring algorithm factors integers in expected polynomial time. Large-scale fault-tolerant quantum computers capable of implementing Shor's algorithm are not yet available, preventing relevant benchmarking experiments. Recently, several authors have attempted quantum factorizations via reductions to SAT or similar NP-hard problems. While this approach may shed light on algorithmic approaches for quantum solutions to NP-hard problems, in this paper we study and question its practicality. 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.
大整数分解的计算难度构成了RSA公钥密码学安全性的基础。经典计算机上最著名的分解算法以亚指数时间运行。整数分解问题可以归约为布尔可满足性问题（SAT）。虽然这种归约已被证明对研究SAT求解器很有用，但尚未通过这种归约对大整数进行分解。肖尔量子分解算法能在预期的多项式时间内分解整数。目前还没有能够实现肖尔算法的大规模容错量子计算机，这使得相关的基准测试实验无法进行。最近，几位作者尝试通过归约到SAT或类似的NP难问题来进行量子分解。虽然这种方法可能会为NP难问题的量子解决方案的算法方法提供启示，但在本文中，我们研究并质疑其实际可行性。我们没有发现证据表明，即使对于可扩展的容错量子计算机以及各种量子退火或其他专用量子硬件来说，这是一条分解大数的可行途径。
