Introduction

This project, titled “Semiprime Factorization Using AQC”, aims to compare different published methods of semiprime factorization using Adiabatic Quantum Computation (AQC). We will verify the scaling law proposed in these studies. The focus is on exploring various AQC techniques to find a more efficient way to factor semiprime numbers, which are difficult for classical computers to handle. You can find the project report here.

What is AQC?

Adiabatic Quantum Computation (AQC) is a type of quantum computing that uses quantum mechanics to find the lowest energy state of a problem, represented by a cost Hamiltonian. This method is similar to classical algorithms like Simulated Annealing (SA), which also seeks the best solution by exploring different possibilities. However, AQC can often do this faster and more accurately because it can use quantum effects, such as quantum tunneling, to escape local minima—places where a solution seems optimal but is not the best overall.

Understanding Semiprime Numbers

A semiprime number is a special type of composite number made by multiplying exactly two distinct prime numbers. For example, the number 15 is a semiprime because it is the product of the primes 3 and 5. Semiprimes are very important in cryptography, especially in systems like RSA encryption. The security of RSA relies on the fact that while it is easy to multiply two large primes to create a semiprime, it is very hard to do the reverse—factor the semiprime back into its prime components. This difficulty is what keeps our digital communications secure.

Methodology

The research follows a series of important steps:

1. Classical Preprocessing

In this first step, we generate initial guesses for the bit lengths of the two factors, which we will call $b_P$ and $b_Q$. We then create logical statements, known as clauses, based on these guesses. To make the problem easier to solve, we use boolean logic to reduce the number of variables involved. This reduction allows us to attempt AQC on current hardware.

2. Constructing the Cost Function

Next, we create a cost function $C$ that uses binary variables to represent the factorization problem. This function is crucial because it helps us understand how to approach the problem. We explore different ways to build this function, including using simple polynomial equations and multiplication tables, to see which method works best.

3. Reducing Variables with Rules

To simplify the problem further, we apply a set of logical rules that help us reduce the number of variables we need to consider. By cutting down on unnecessary variables, we can make the computation much less complex and more manageable.

4. Implementing AQC

Once we have a simplified version of the problem, we use AQC to find the ground state of the reduced Hamiltonians. This process involves making repeated measurements to identify the two prime factors $P$ and $Q$ of the semiprime number. The goal is to achieve sub-$b_N$ scaling, which means making the size of the problem smaller than the bit length of the composite number $N$.

5. Annealing Schedule

The annealing schedule refers to the time-dependent constants multiplied to the initial Hamiltonian and cost Hamiltonian. This schedule controls the rate of annealing, which is crucial for the success of the AQC process.

Results and Findings

Our project shows that AQC can be effectively used for semiprime factorization, and the results are promising. We found that while we can reduce many variables in our approach, we do not yet achieve the ideal scaling of sub-$b_N$. This means that there is still room for improvement. Future research will focus on finding the best Annealing Schedule to ensure we can verify and improve the efficiency of our method.

Conclusion

This research provides important insights into how quantum computing can help solve complex problems in number theory and cryptography. The findings suggest that AQC has the potential to be a powerful tool for tackling difficult mathematical challenges, which could lead to significant advancements in quantum algorithms and their applications.

Acknowledgments

I would like to express my sincere gratitude to Prof. Prasanta K. Panigrahi for his invaluable support and guidance throughout this project, which was part of my Master’s degree requirements at IISER Kolkata. His expertise and encouragement were instrumental in the success of this research.