Quantum annealers and the future of prime factorization

Researchers at the University of Trento, Italy, have developed a novel approach for prime factorization via quantum annealing, leveraging a compact modular encoding paradigm and enabling the factorization of large numbers using D-Wave quantum devices.

Prime factorization is the procedure of breaking down a number into its prime components. Every integer greater than one can be uniquely expressed as a product of prime numbers.

In cryptography, prime factorization holds particular importance due to its relevance to the security of encryption algorithms, such as the widely used RSA cryptosystem.

The process of prime factorization becomes challenging because of the nature of prime numbers, and it gets even more complicated as the numbers being factored become bigger, leading to a vast number of possibilities to consider.

The impracticality of efficiently factoring large numbers ensures the integrity of encrypted communication. The robustness of these cryptographic systems relies on the computational complexity of prime factorization, making it a crucial component in safeguarding sensitive information in the digital age.

If someone can efficiently factorize the product of two large prime numbers, they could potentially break the security of cryptographic systems. Understanding and advancing techniques for prime factorization contribute to ensuring the robustness of cryptographic protocols and safeguarding sensitive information in digital communication.

In a new study published in Scientific Reports, researchers led by Prof. Roberto Sebastiani from the University of Trento, Italy, aimed to tackle this process using quantum annealers. The team also consisted of Jingwen Ding and Giuseppe Spallitta, Ph.D. students at the University of Trento.

“As a computer scientist who has spent a whole career developing classical procedures for solving computationally hard logical and optimization problems, I was very intrigued to deal with a technology like quantum annealing based on a computing paradigm far from anything I had encountered before,” Prof. Sebastiani told Tech Xplore.

Quantum annealers

Quantum computers are uniquely suited for prime factorization problems due to their ability to perform parallel computations and exploit quantum phenomena. Specifically, quantum annealers, like those from D-Wave, are designed to tackle optimization problems by searching for optimal solutions among a vast number of possibilities simultaneously.

In the context of prime factorization, where finding the prime factors involves exploring numerous combinations quickly, the inherent parallelism of quantum computing offers a potential advantage.

Quantum annealers leverage quantum phenomena like quantum superposition and quantum tunneling to explore multiple solutions concurrently, making them well-suited for prime factorization problems. This parallel exploration of possibilities can significantly enhance the efficiency of searching for prime factors compared to classical algorithms.

Compact encoding

The research has a two-fold nature. In the first aspect of their work, the researchers achieved a breakthrough by developing a compact modular encoding of a 21×12-bit binary multiplier circuit directly into a single 8-qubit module within the Pegasus topology of D-Wave’s quantum annealers.

Think of the Pegasus topology as a web connecting qubits, determining how data flows.

“The game changer in this work—which came out as a positive surprise to us—was the successful encoding of a controlled full-adder (CFA) sub-circuit into a single 8-qubit module of the Pegasus Quantum Annealer topology,” explained Prof. Sebastiani.

CFA is a quantum sub-circuit that performs 1-bit addition operations under specific control conditions, which the team encoded into a module of the annealer’s topology using Optimization Modulo Theories (OMT), a technology combining logical reasoning and optimization.

Unlike past approaches that overlooked the system’s layout, the team utilized OptiMathSAT, their Optimization Modulo Theories tool, to craft an encoding well aware of the topology. This demonstrated the efficiency of their approach and marked a significant advancement in encoding techniques for quantum annealers.

The modularity of their encoding approach is a game-changer. They demonstrated the capability of encoding into the annealer the factorization of up to the number 8,587,833,345 into the product of two prime numbers, 2,097,151 and 4,095. This marks the largest factorization problem ever encoded into a quantum annealer using their novel method.

“We noticed two key facts. We can decompose an n×m-bit multiplier circuit into a matrix of interconnected CFA sub-circuits, and we can align it with the Pegasus lattice of 8-qubit modules,” explained Prof. Sebastiani.

This allowed the researchers to create a structure that can scale effortlessly with the growth of qubit numbers in future quantum annealer chips.

© 2024 Science X Network