On speeding up factoring with quantum SAT solvers.

Area of Science:

• Quantum Computing
• Number Theory
• Computational Complexity

Background:

• Integer factorization is crucial for cryptography.
• Current quantum algorithms for factorization (like Shor's) are distinct from SAT solving.
• Previous attempts to use quantum SAT solvers for direct factorization have faced significant challenges.

Purpose of the Study:

• To investigate the application of quantum SAT solvers to a sub-problem within integer factorization.
• To develop a novel approach for finding smooth numbers using SAT circuits for quantum solvers.
• To assess the potential of this method to compete with classical algorithms like the Number Field Sieve.

Main Methods:

• Formulating the problem of finding smooth numbers as a SAT problem.
• Designing a SAT circuit specifically for quantum SAT solvers (e.g., annealers).
• Analyzing the potential speedup of quantum SAT solvers over classical brute-force search for smooth numbers.

Main Results:

• A SAT circuit for identifying smooth numbers has been developed.
• The proposed method's efficiency is contingent on quantum SAT solvers achieving asymptotic speedups.
• If such speedups are realized, the factoring algorithm is projected to be faster than the classical Number Field Sieve.

Conclusions:

• Restricting SAT solvers to the smooth number search problem offers a more viable quantum approach to factorization.
• The success of this method hinges on advancements in quantum SAT solving capabilities.
• This work presents a potential pathway for quantum advantage in integer factorization through a refined application of SAT solvers.