Quantum Shield Implements Regev Algorithms – A Boost for Quantum Computing and Cybersecurity
At the AIR Institute, we are developing Quantum Shield, a project focused on post-quantum security and quantum machine learning for cybersecurity in smart manufacturing environments within Industry 4.0. This initiative is aligned with the RIS3 strategy of Castilla y León, and is funded by the Business Competitiveness Institute of the Regional Government of Castilla y León (ICE) and the European Regional Development Fund (ERDF).
One of the project's objectives is to analyse the challenges and opportunities that quantum computing may present for cybersecurity in intelligent production systems within the industrial sector. It also aims to increase the efficiency and security of industrial processes involving smart production systems, in order to ensure the long-term sustainability of the Industry 4.0 model.
Regev’s Quantum Factoring Algorithm
Within Quantum Shield, Regev’s quantum factoring algorithm has been successfully implemented, transitioning from its theoretical framework to a functional implementation in quantum computing. One of the key advantages of Regev’s algorithm over Shor’s lies in its lower quantum gate complexity. While Shor’s algorithm requires O(n²) quantum gates—where n is the bit length of the number to be factored—Regev’s approach reduces this to O(n3/2). This reduction in gate complexity means that Regev’s algorithm is less susceptible to noise and decoherence, which typically occur in quantum systems, especially when working with large numbers. Although Regev’s algorithm does not yet outperform Shor’s for small integers—where Shor’s remains faster due to its simpler quantum circuit—it is expected to become more efficient as the size of the number increases.
For very large integers, the reduced quantum gate complexity of Regev’s algorithm makes it a more viable option, particularly in terms of maintaining quantum coherence. However, the classical post-processing step—especially lattice reduction using algorithms such as LLL—remains computationally intensive and represents a bottleneck in the overall efficiency of the algorithm. Despite this, our implementation aims to demonstrate whether Regev’s algorithm, when fully optimised, offers a significant efficiency advantage for larger numbers compared to Shor’s.
The main challenge of our project has been to take the complex theoretical description of Regev’s algorithm and effectively implement it on a quantum platform. The process began with the design of a quantum circuit that follows Regev’s approach. We started by initialising the quantum registers using the Grover-Rudolph algorithm. We then applied modular exponentiation gates, followed by a Quantum Fourier Transform (QFT) to extract the period of the modular function, which is essential for the factoring of the integer.
In this regard, our project marks a key step in demonstrating the viability of Regev’s quantum factoring algorithm. By successfully moving from theory to practice, we have showcased a promising alternative to Shor’s algorithm, one that leverages reduced gate complexity for more efficient quantum computing. As quantum hardware continues to improve, the efficiency and feasibility of Regev’s algorithm are likely to surpass those of Shor’s for larger integers, making it a significant area for future research and development in cybersecurity.