A new type of computation that goes beyond Turing’s model might exist. Richard Feynman, a Nobel Prize-winning American physicist, proposed the concept of computation based on quantum mechanics in 1982.
American applied mathematician Peter Shor proposed a quantum algorithm to factor integers in polynomial time in 1995. According to mathematicians, this cannot be resolved by polynomial-time algorithms within Turing’s framework. Finding a smaller integer greater than 1 that can divide an integer is known as factoring. For instance, the number 688,826,081 can be divided by the smaller number 25,253 because it equals 25,253 x 27,277.
The computational difficulty of factoring large integers is the foundation of a significant algorithm known as the RSA algorithm, which is widely used in securing network communications. Shor’s finding indicates that, should it materialize, quantum computing will alter the cybersecurity landscape.
Is it possible to create a full-fledged quantum computer that can factor integers and tackle other issues? Some scientists think it’s possible. Many teams of researchers are working to create one, and some have already constructed small-scale quantum computers.
Nevertheless, like all novel technologies invented before, issues with quantum computation are almost certain to arise that would impose new limits.
Jie Wang is a professor of computer science at UMass Lowell.
