Skip to main page content
U.S. flag

An official website of the United States government

Dot gov

The .gov means it’s official.
Federal government websites often end in .gov or .mil. Before sharing sensitive information, make sure you’re on a federal government site.

Https

The site is secure.
The https:// ensures that you are connecting to the official website and that any information you provide is encrypted and transmitted securely.

Access keys NCBI Homepage MyNCBI Homepage Main Content Main Navigation
. 2024 Feb 12;14(1):3518.
doi: 10.1038/s41598-024-53708-7.

Effective prime factorization via quantum annealing by modular locally-structured embedding

Jingwen Ding  1 , Giuseppe Spallitta  1 , Roberto Sebastiani  2
Affiliations

Effective prime factorization via quantum annealing by modular locally-structured embedding

Jingwen Ding et al. Sci Rep. .

Abstract

This paper investigates novel techniques to solve prime factorization by quantum annealing (QA). First, we present a very-compact modular encoding of a multiplier circuit into the architecture of current D-Wave QA devices. The key contribution is a compact encoding of a controlled full-adder into an 8-qubit module in the Pegasus topology, which we synthesized using Optimization Modulo Theories. This allows us to encode up to a 21 × 12-bit multiplier (and a 22 × 8-bit one) into the Pegasus 5760-qubit topology of current annealers. To the best of our knowledge, these are the largest factorization problems ever encoded into a quantum annealer. Second, we investigated the problem of actually solving encoded PF problems by running an extensive experimental evaluation on a D-Wave Advantage 4.1 quantum annealer. In the experiments we introduced different approaches to initialize the multiplier qubits and adopted several performance enhancement techniques. Overall, 8,219,999 = 32,749 × 251 was the highest prime product we were able to factorize within the limits of our QPU resources. To the best of our knowledge, this is the largest number which was ever factorized by means of a quantum annealer; also, this is the largest number which was ever factorized by means of any quantum device without relying on external search or preprocessing procedures run on classical computers.

PubMed Disclaimer

Conflict of interest statement

The authors declare no competing interests.

Figures

Figure 1
Figure 1
Information about the D-Wave Pegasus systems. In Fig. 1a, s stands for the normalized anneal fraction time..
Figure 2
Figure 2
Details about the modularity of shift-and-add multipliers.
Figure 3
Figure 3
Modular encoding of binary multipliers on the D-Wave Pegasus topology.
Figure 4
Figure 4
CFA structure for the four versions of multipliers.
See this image and copyright information in PMC

References

    1. Lenstra, A. K., Lenstra Jr, H. W., Manasse, M. S. & Pollard, J. M. The number field sieve. in Proceedings of the Twenty-Second Annual ACM Symposium on Theory of Computing, 564–572 (1990).
    1. Boudot, F. et al. Comparing the difficulty of factorization and discrete logarithm: a 240-digit experiment. in Advances in Cryptology–CRYPTO 2020: 40th Annual International Cryptology Conference, CRYPTO 2020, Santa Barbara, CA, USA, August 17–21, 2020, Proceedings, Part II 40, 62–91 (Springer, 2020).
    1. Rivest RL, Shamir A, Adleman L. A method for obtaining digital signatures and public-key cryptosystems. Commun. ACM. 1978;21:120–126. doi: 10.1145/359340.359342. - DOI
    1. Shor, P. Algorithms for quantum computation: Discrete logarithms and factoring. in Proceedings 35th Annual Symposium on Foundations of Computer Science, 124–134, 10.1109/SFCS.1994.365700 (1994).
    1. Vandersypen LMK, et al. Experimental realization of Shor’s quantum factoring algorithm using nuclear magnetic resonance. Nature. 2001;414:883–887. doi: 10.1038/414883a. - DOI - PubMed