Open Access
ARTICLE
Effects of T-Factor on Quantum Annealing Algorithms for Integer Factoring Problem
1 State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications, Beijing, 100876, China
2 School of Mathematics and Computer Science, Shaanxi University of Technology, Hanzhong, 723000, China
3 School of Cyberspace Science and Technology, Beijing Institute of Technology, Beijing, 100081, China
* Corresponding Author: Licheng Wang. Email:
Journal of Quantum Computing 2023, 5, 41-54. https://doi.org/10.32604/jqc.2023.045572
Received 31 August 2023; Accepted 10 November 2023; Issue published 12 December 2023
Abstract
The hardness of the integer factoring problem (IFP) plays a core role in the security of RSA-like cryptosystems that are widely used today. Besides Shor’s quantum algorithm that can solve IFP within polynomial time, quantum annealing algorithms (QAA) also manifest certain advantages in factoring integers. In experimental aspects, the reported integers that were successfully factored by using the D-wave QAA platform are much larger than those being factored by using Shor-like quantum algorithms. In this paper, we report some interesting observations about the effects of QAA for solving IFP. More specifically, we introduce a metric, called T-factor that measures the density of occupied qubits to some extent when conducting IFP tasks by using D-wave. We find that T-factor has obvious effects on annealing times for IFP: The larger of T-factor, the quicker of annealing speed. The explanation of this phenomenon is also given.Keywords
The hardness assumption of the integer factorization problem (IFP) [1] is one of the most important cryptographic primitives for modern information security. Based thereon, the well-known RSA cryptosystem [2] as well as its variants [3] are assumed to still be secure and widely used today. In fact, our confidence in this comes from the classical computational complexity for solving IFP. To factor a larger integer N, the current fastest classical algorithm is the number field sieve (NFS) method that has sub-exponential complexity with respect to the bit-length of N, expressed by
Even so, our confidence is losing due to the quick development of quantum computation. Theoretically, Shor’s quantum algorithm can factor
Interestingly, the methods of solving IFP by using quantum computers have new developments besides Shor’s algorithm. In 2001, Farhi et al. [9] introduced the quantum adiabatic theorem for the first time, and realized the factorization of
In this work, we would like to report an interesting observation regarding the performance of quantum annealing algorithm (QAA for short) for integer factorization. In the above-mentioned experiments, improvements on the multiplication table are employed to reduce the required qubits. However, in our experiments based on D-Wave platform, we found that the multiplier filling degree (named T-factor) in the QAA algorithm has an observable effect on the performance of the annealing algorithm. In the classical algorithm, the larger the difference between the two multipliers is, the easier the integer is to factorize. However, in the quantum annealing factorization experiment, we conclude that the bigger the difference between the bit-lengths of the two multipliers
The structure of this paper is as follows. In Section 2, the background required for this article is presented. The integer factorization and simulated annealing algorithm are briefly introduced, and the advantage of QAA is introduced. In Section 3, the evaluation criteria of algorithm performance are first determined. After the traversal annealing experiment, the processed data are also presented. In Section 4, we propose the concept of T-factor and explain why T-factor affects algorithm performance. In Section 5, through the experimental data, we summarize the indicative role of T-factor in actual integer factorization, the deficiency of T-factor is also discussed.
2.1 Classical Simulated Annealing
The idea of simulated annealing was introduced into combinatorial optimization algorithm by Kirkpatrick et al. [19] in 1983, it is a stochastic optimization algorithm based on Monte-Carlo iterative solving strategy. The actual operation flow of simulated annealing algorithm is as follows.
Set the initial temperature
2.2 Quantum Annealing and D-Wave
Quantum annealing is a generic name of quantum algorithms that use quantum-mechanical fluctuations to search for the solution to an optimization problem [20]. The traditional simulated annealing algorithm uses thermodynamics to make the system cross the potential barrier. Quantum annealing algorithm uses quantum tunneling effect to achieve this goal. As in the traditional simulated annealing algorithm with slow cooling, we first set the quantum fluctuation strength to a large value to find the global structure of the solution space. After that we gradually reduce the strength of the fluctuations, hoping to recover the original system in the lowest energy state. Quantum annealing algorithm is a general algorithm, which can be applied to any combinatorial optimization problem.
The evolution of quantum system can be described by the time-varying Schrodinger equation [21]
and
In the D-Wave quantum annealing platform, the gates in the multiplier are converted into a mapping of qubits and couplers. As shown in Fig. 1, the full adder is converted to a yellow pentagonal star, the half adder to a blue square, and the AND gate to a pink triangle. When we fix the output to the integer we need to factorize, the energy ground state of the entire quantum circuit system is determined. The potential energy
Figure 1: (a) Shows the transformation of AND gate into quantum circuit state; (b) is the circuit diagram of the classical multiplier; (c) shows the transformation of gate circuit into quantum circuit; (d) shows the quantum circuit diagram after the conversion is completed (Image from the official D-Wave website)
Quantum tunneling effect: In quantum mechanics, we have
where
Figure 2: Compared with the conventional simulated annealing algorithm, the quantum annealing algorithm can use the quantum tunneling effect directly to ignore the potential energy barriers to the optimal solution
3 Research Methods of Quantum Annealing
3.1 Hamiltonian Modeling of the Integer Factorization Problem
We use the quantum annealed integer factorization algorithm provided by D-Wave platform to carry out experiments. The objective function is
set
First, the time-varying Hamiltonian of a quantum system is
where the duration T defines the time scale over which the function runs and controls the rate of change of the Hamiltonian over time.
The Ising model [24] is thus established.
Here we further refine the Ising model as shown in Eq. (8). As shown in Fig. 1d, we connect the integer to be decomposed and the set multiplier into the optimized quantum circuit after conversion. The qubits form the local domain
•
•
3.2 Relationship between Annealing Times and Algorithm Execution Time
The integer factorization procedure of the D-Wave quantum annealing platform allows us to set different numbers of inner loops in the code, which we collectively refer to here as the number of annealing runs. In the annealing algorithm, the number of annealing runs has a linear relationship with the time that the program runs, as shown in Fig. 3.
Figure 3: There is a linear relationship between annealing time and number of annealing runs we can artificially limit the number of annealing runs in order to obtain the best solution performance
Since the number of annealing runs is controllable, the complexity of factorization of an integer will be determined by the number of annealing runs times in this paper. In addition, the annealing algorithm is a random search algorithm [26], and the annealing times can not be measured accurately. Generally,
3.3 Effective Filling of the Multiplier Factor
In the quantum annealing algorithm, we factor integers by defining objective function as
However, this leads to a problem, such as
Definition of the T-factor: Let
We plot the T-factor vs. the annealing times required for the decomposition by the experimental results of traversal decomposition for integers up to 5000, which are obtained by multiplying two prime numbers, as shown in Fig. 4.
Figure 4: The relationship between the T-factor and the annealing times when the decomposition integer is within 5000
As shown in Fig. 4, the larger the T-factor, the easier the integer to be factored, and the less number of annealing runs required. We suspect that the reason for this phenomenon may be related to the objective function
The result of traversal factorization for suitable integers up to 4096 is shown in Fig. 5, and the effect of the T-factor on the number of anneals required to factorize the integers is shown in Fig. 6.
Figure 5: The relationship between the T-factor and the number of annealing runs of factored integers
Figure 6: The T-factor affects the annealing times Scatter plot (The factorized integer is within 5000)
In the whole annealing process, the number of annealing runs does not simply increase with the increase of the integer but shows a trend of fluctuation. This situation is contrary to the experience summarized in the number theory factorization integer algorithm. Consider the effect of T-factor on factored integers. In Fig. 4, the higher the T-factor, the fewer the number of annealing runs required for integer factorization. The lower the T-factor, the more number of annealing runs required to factor the integer. Figs. 5 and 6 confirm the effect of the T-factor in Section 3.3 on the performance of factored integers.
4.1 The Constraint of the Target Function on the Field
We use MATLAB to show the objective function
Figure 7: Multipliers with different number of digits factor 15 and 115
In Fig. 7, there is an obvious region
Figure 8: 5-bit multiplier factorizes 115
Mapping the factorization results to the two-dimensional plane, can be seen in Fig. 8a that in the part where both multiplier factors are small, the annealing results are relatively sparse, the larger the multiplier factor, the more and more intensive the annealing results. This indicates that in the execution process of the annealing algorithm, the probability of the output is greater in the region with a large T-factor.
There is a lot of sample size so there is a lot of duplication, the occurrence frequency of the output point needs to be added into the analysis process. Therefore, the frequency of the output result is also counted, as shown in Fig. 8b. The Z-axis represents the frequency of the point. As can be seen from Figs. 8a and 8b, not only the solution in the region with small T-factor is sparse, but also its frequency is small, indicating that the quantum annealing algorithm does prefer the direction with large T-factor.
4.2 Supplement Experiment and Data
We continue to factor integers under different T-factor to verify our conjecture. Table 1 is obtained by sorting the data. Since the multiplication factor of integers is known in our experiment, we change the definition of T-factor a little here, as shown in Eq. (10).
When the T-factor is 1, that is, the multiplier factor can completely fill the multiplier, the number of annealing runs required for integer factorization is very small, within 100 times. When the T-factor is slightly smaller, the number of annealing runs times needed to factor the integers increases exponentially. This result is consistent with our previous conjecture.
In particular, we have factored two larger integers for reference. For the factorization of 3599 and 3233, it can be better seen that the influence of T-factor on integer factorization is far greater than that of the size of the integer itself.
Meanwhile, as mentioned above, within the same search range, the larger the integer is, the easier it is to factor. In Fig. 9, the 6-bit multiplier is used to factor 1517, 1927, 2491 and 3599, respectively. Among them, the number of annealing runs factorization 1517 is 1500, factorization 1927 is 1000, factorization 2491 is 500, factorization 3599 is 200.
Figure 9: The 6-bit multiplier splits large integers
According to Fig. 9, within the same search range, the larger the integer, the smaller the region of potential energy valley, and the fewer the annealing times required for factorization.
It can be concluded that when using quantum annealing to solve the integer factorization problem, the closer the multiplier factors are to each other, the easier it is to factor the integer. According to Eq. (8), if we can judge the range of multiplier factors, then we can greatly reduce the number of quantum annealing required for integer factorization. On this basis, when the number of multipliers and T-factor are the same, the larger the integer is, the easier the factorization will be, which can explain the fluctuation phenomenon caused by traversal factorization at the beginning of this paper.
Experiments show that the performance of the whole algorithm is affected by setting the bit of the multiplier when using quantum simulated annealing for integer factorization. Experiments show that the integer is easy to be factored when the multiplier is well filled, that is, the highest bit can also be used. If the multiplier is not fully filled, that is, the binary bits of the multiplication factor are less than or much less than the number of the multiplier, the corresponding integer will be difficult to be factored. We attribute this phenomenon to the effect of quantum tunneling in the annealing algorithm. Low potential energy points are densely distributed around the function
In the current integer factorization methods, the traditional number theory factorization method limits the large integer to
At the same time, the multiplier factor in integer decomposition is equivalent without any restriction. However, in the experimental results, the output frequencies of the results of these two factors are different. Due to the limited experiments, we can do on the cloud platform, this asymmetry cannot be further explained.
In industry, the annealing process is still the result of the empirical nature of the experiment produced. Furthermore, the indicative significance of the existence of T-factor is far greater than the theoretical value behind it. In future quantum annealing factorization, the padding of the multiplier can be used to roughly predict the number of annealing runs times needed to factor the integer, so as to further reduce the use of qubits.
Furthermore, we consider that the number of annealing runs fluctuates regularly with the increase of integers during ergodic annealing. We can further expand the scope of traversal to obtain a more accurate and wider range of function images. Based on this data, we can take the Fourier transform and predict the range of annealing times needed to factor a range of integers. This is very indicative. When the actual number of annealing runs operations is much larger than this value, we can manually adjust the number of multiplier bits to change the search space to factor the integer more efficiently.
Through reasonable speculation on the experimental results, we think that the annealing times of the traversal annealing image will fluctuate with the increase of the integer, the smaller the integer is, the smaller the period of its fluctuation, the larger the integer is, the larger the period of its fluctuation, and the overall trend of the whole fluctuation function image has a rising trend proportional to the integer size. Therefore, the practical efficiency of quantum annealing for integer factorization needs further consideration.
Acknowledgement: We would like to thank Professor Chao Wang for his encouragements and valuable suggestions on conducting this research.
Funding Statement: This research was funded by the National Natural Science Foundation of China (NSFC) (Grant No. 61972050), and the Open Foundation of State Key Laboratory of Networking and Switching Technology (Beijing University of Posts and Telecommunications) (SKLNST-2020-2-16).
Author Contributions: The author Zhiqi Liu was mainly responsible for the research conception and design of the paper, as well as data collection and processing; Author Xingyu Yan was responsible for the analysis and interpretation of the results; Author Ping Pan helped with further experimental data; Authors Licheng Wang and Shihui Zheng improved the idea structure of the manuscript and the overall article. All authors reviewed the results and approved the final version of the manuscript.
Availability of Data and Materials: Data openly available in a public repository. The data that support the findings of this study are openly available in Github at https://github.com/Leosirius2597/D-Wave-integer-factorization.
Conflicts of Interest: The authors declare that they have no conflicts of interest to report regarding the present study.
References
1. P. L. Montgomery, “A survey of modern integer factorization algorithms,” CWI Quarterly, vol. 7, no. 4, pp. 337–366, 1994. [Google Scholar]
2. R. L. Rivest, A. Shamir and L. Adleman, “A method for obtaining digital signatures and public-key cryptosystems,” Communications of the ACM, vol. 21, no. 2, pp. 120–126, 1978. [Google Scholar]
3. M. Bellare and P. Rogaway, “Optimal asymmetric encryption,” in Advances in Cryptology EUROCRYPT’ 94: Workshop on the Theory and Application of Cryptographic Techniques Perugia, Italy, Springer; pp. 92–111, 1995. [Google Scholar]
4. F. Boudot, P. Gaudry, A. Guillevic, N. Heninger, E. Thomé et al., “Comparing the difficulty of factorization and discrete logarithm: A 240-digit experiment,” in Advances in Cryptology–CRYPTO 2020: 40th Annual Int. Cryptology Conf., Santa Barbara, CA, USA, Springer, pp. 62–91, 2020. [Google Scholar]
5. T. Kleinjung, K. Aoki, J. Franke, A. K. Lenstra, E. Thomé et al., “Factorization of a 768-bit rsa modulus,” in Crypto, Springer, vol. 6223, pp. 333–350, 2010. [Google Scholar]
6. H. Riel, “Quantum computing technology,” in 2021 IEEE Int. Electron Devices Meeting (IEDM), IEEE, pp. 1–3, 2021. [Google Scholar]
7. M. Roetteler, M. Naehrig, K. M. Svore and K. Lauter, “Quantum resource estimates for computing elliptic curve discrete logarithms,” in Int. Conf. on the Theory and Application of Cryptology and Information Security, Springer, pp. 241–270, 2017. [Google Scholar]
8. M. Amico, Z. H. Saleem and M. Kumph, “Experimental study of Shor’s factoring algorithm using the IBM Q experience,” Physical Review A, vol. 100, no. 1, pp. 012305, 2019. [Google Scholar]
9. E. Farhi, J. Goldstone, S. Gutmann, J. Lapan, A. Lundgren et al., “A quantum adiabatic evolution algorithm applied to random instances of an NP-complete problem,” Science, vol. 292, no. 5516, pp. 472–475, 2001. [Google Scholar] [PubMed]
10. S. Jiang, K. A. Britt, A. J. McCaskey, T. S. Humble and S. Kais, “Quantum annealing for prime factorization,” Scientific Reports, vol. 8, no. 1, pp. 1–9, 2018. [Google Scholar]
11. A. Das and B. K. Chakrabarti, “Colloquium: Quantum annealing and analog quantum computation,” Reviews of Modern Physics, vol. 80, no. 3, pp. 1061, 2008. [Google Scholar]
12. W. Peng, B. Wang, F. Hu, Y. Wang, X. Fang et al., “Factoring larger integers with fewer qubits via quantum annealing with optimized parameters,” Science China Physics, Mechanics & Astronomy, vol. 62, no. 6, pp. 1–8, 2019. [Google Scholar]
13. B. Wang, F. Hu, H. Yao and C. Wang, “Prime factorization algorithm based on parameter optimization of Ising model,” Scientific Reports, vol. 10, no. 1, pp. 1–10, 2020. [Google Scholar]
14. S. W. Shin, G. Smith, J. A. Smolin and U. Vazirani, “How “quantum” is the d-wave machine?” arXiv preprint arXiv:1401.7087, 2014. [Google Scholar]
15. D. Saida, M. Hidaka, K. Imafuku and Y. Yamanashi, “Factorization by quantum annealing using superconducting flux qubits implementing a multiplier Hamiltonian,” Scientific Reports, vol. 12, no. 1, pp. 1–8, 2022. [Google Scholar]
16. K. Bharti, A. Cervera-Lierta, T. H. Kyaw, T. Haug, S. Alperin-Lea et al., “Noisy intermediate-scale quantum (NISQ) algorithms,” arXiv preprint arXiv:2101.08448, 2021. [Google Scholar]
17. J. Preskill, “Quantum computing in the nisq era and beyond,” Quantum, vol. 2, pp. 79, 2018. [Google Scholar]
18. B. Yan, Z. Tan, S. Wei, H. Jiang, W. Wang et al., “Factoring integers with sublinear resources on a superconducting quantum processor,” 2022. https://doi.org/10.48550/ARXIV.2212.12372 [Google Scholar] [CrossRef]
19. S. Kirkpatrick, C. D. Gelatt Jr and M. P. Vecchi, “Optimization by simulated annealing,” Science, vol. 220, no. 4598, pp. 671–680, 1983. [Google Scholar] [PubMed]
20. S. Morita and H. Nishimori, “Mathematical foundation of quantum annealing,” Journal of Mathematical Physics, vol. 49, no. 12, pp. 125210, 2008. [Google Scholar]
21. J. H. Shirley, “Solution of the schrödinger equation with a Hamiltonian periodic in time,” Physical Review, vol. 138, no. 4B, pp. 979, 1965. [Google Scholar]
22. M. W. Johnson, M. H. Amin, S. Gildert, T. Lanting, F. Hamze et al., “Quantum annealing with manufactured spins,” Nature, vol. 473, no. 7346, pp. 194–198, 2011. [Google Scholar] [PubMed]
23. H. P. Robertson, “The uncertainty principle,” Physical Review, vol. 34, no. 1, pp. 163, 1929. [Google Scholar]
24. B. M. McCoy and T. T. Wu, The Two-Dimensional Ising Model, Cambridge, MA, USA: Harvard University Press, pp. 31–34, 1973. [Google Scholar]
25. Z. Deng, K. Gao and M. Feng, “Generation of N-qubit W states with rf SQUID qubits by adiabatic passage,” Physical Review A, vol. 74, no. 6, pp. 064303, 2006. [Google Scholar]
26. D. Bertsimas and J. Tsitsiklis, “Simulated annealing,” Statistical Science, vol. 8, no. 1, pp. 10–15, 1993. [Google Scholar]
Cite This Article
![cc](https://www.techscience.com/static/images/cc.jpg?t=20230215)
This work is licensed under a Creative Commons Attribution 4.0 International License , which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.