Researchers at the Massachusetts Institute of Technology (MIT) have recently advanced cryptography by developing a more efficient quantum algorithm. This new approach focuses on creating a smaller, noise-tolerant quantum factoring circuit, which is essential for cryptographic applications.
Study: Toward a code-breaking quantum computer. Image Credit: Harsamadu/Shutterstock.com
Cracking Complex Cryptography
Service providers, including messaging apps and email clients, rely heavily on the RSA encryption scheme to securely transmit messages over the Internet. Developed in the 1970s by MIT researchers, RSA encryption is based on the principle that factoring a 2,048-bit integer within a reasonable time frame is exceedingly difficult for classical computers.
However, complex cryptographic systems like RSA, which are virtually unbreakable by classical computers, could be swiftly compromised by quantum computers using Shor’s algorithm, introduced by Peter Shor in 1994. Despite substantial advancements in quantum computing over the past three decades, a practical quantum computer capable of efficiently executing Shor’s algorithm has yet to be realized.
For example, running Shor’s algorithm would require approximately 20 million qubits, while the largest quantum computers today have around 1,100 qubits. Various research efforts are underway to tackle this challenge, including refining Shor’s algorithm to work on smaller quantum circuits with fewer gates and developing larger, more capable quantum computers.
Recent Developments
In the past year, computer scientist Oded Regev from New York University proposed a major theoretical advancement in quantum computing. Quantum computers perform computations using quantum circuits, which are sequences of operations called quantum gates that manipulate qubits.
Regev's innovation specifically addresses the challenge of quantum noise, which arises from the use of numerous quantum gates. Shor’s original quantum circuit requires a number of gates proportional to the square of the integer being factored, necessitating millions of gates for a 2,048-bit integer. In contrast, Regev’s proposed circuit significantly reduces the number of quantum gates, thereby mitigating the noise problem.
However, this improvement comes with its own challenge: Regev’s circuit requires a larger number of qubits to ensure adequate memory. These additional qubits are prone to decay over time, presenting a new obstacle in the quest to build more efficient and reliable quantum computers.
The Proposed Solution
Although Regev’s proposed algorithm can run faster, the circuit will require more memory. Based on these results, researchers from MIT recently proposed a novel approach combining the memory efficiency of Shor’s algorithm with the speed of Regev’s algorithm.
Unlike previous methods, this new algorithm performs computations involving large numbers by running the quantum circuit multiple times to compute powers.
Computing these large powers on a quantum computer presents challenges, as quantum operations are reversible, while squaring a number is not. To address this, the MIT researchers used Fibonacci numbers for exponentiation, which only require simple, reversible multiplications instead of squaring. This approach drastically reduces the quantum memory needed to compute any exponent, requiring only two quantum memory units.
Additionally, the researchers tackled the issue of error correction, a significant hurdle for quantum computing. While Regev’s and Shor’s circuits need perfectly accurate quantum gates, real quantum computers cannot guarantee error-free operations. To address this, the MIT team developed a method that filters out incorrect or corrupt results, processing only the correct ones. This technique makes the algorithm more reliable and suitable for practical use.
By overcoming two major limitations of previous quantum factoring algorithms—memory inefficiency and error correction—the MIT researchers have significantly advanced the field. Their work brings quantum factoring closer to practical implementation and could lead to the development of new encryption schemes that are resilient against quantum computing threats.
In summary, this research not only demonstrates the feasibility of quantum factoring but also accelerates its practical deployment. Future efforts will focus on further optimizing the algorithm and applying it to practical quantum circuits for testing.
Journal Reference
Zewe, A. (2024) Toward a code-breaking quantum computer [Online] Available at https://news.mit.edu/2024/toward-code-breaking-quantum-computer-0823 (Accessed on 02 September 2024)
Disclaimer: The views expressed here are those of the author expressed in their private capacity and do not necessarily represent the views of AZoM.com Limited T/A AZoNetwork the owner and operator of this website. This disclaimer forms part of the Terms and conditions of use of this website.