Effective Prime Factorization via Quantum Annealing by Modular Locally-structured Embedding

Abstract This paper investigates novel techniques to solve prime factorizationby quantum annealing (QA).First, we present a very-compact modular encoding of amultiplier circuit into the architecture of current D-Wave QA devices.The key contribution is a compact encoding of a controlled full-adderinto an 8-qubit module in the Pegasus topology, which we synthesizedby means of Optimization Modulo Theories. This allows us to encode upto a 21×12-bit multiplier (and a 22×8-bit one) into the Pegasus5760-qubit topology of current annealers. To the best of ourknowledge, these are the largest factorization problems ever encodedinto a quantum annealer.Second, we investigated the problem of actually solving encodedPF problems by running an extensive experimental evaluation on aD-Wave Advantage 4.1 quantum annealer. In the experiments weintroduced different approaches to initialize the multiplier qubitsand adopted several performance enhancement techniques. Overall,8,219,999=32,749×251 was the highest prime product we were able tofactorize within the limits of our QPU resources. To the best of ourknowledge, this is the largest number which was ever factorized bymeans of a quantum device.