Could there be a new form of computation beyond Turing’s framework? In 1982, the American physicist Richard Feynman, winner of the Nobel Prize, proposed the idea of a calculation based on quantum mechanics.
In 1995, Peter Shor, an American applied mathematician, presented a quantum algorithm for factoring integers in polynomial time. Mathematicians believe this is unsolvable by polynomial-time algorithms in the Turing framework. Factoring an integer means finding a smallest integer greater than 1 that can divide the integer. For example, the integer 688,826,081 is divisible by a smaller integer 25,253, because 688,826,081 = 25,253 x 27,277.
A major algorithm called the RSA algorithm, widely used in securing network communications, is based on the computational difficulty of factoring large integers. Shor’s result suggests that quantum computing, if it were to become a reality, would change the cybersecurity landscape.
Can a full-fledged quantum computer be built to factor integers and solve other problems? Some scientists believe that may be the case. Several groups of scientists around the world are working to build one, and some have already built small-scale quantum computers.
Nevertheless, like all new technologies invented before, it is almost certain that problems with quantum computing will arise that would impose new limits.
Jie Wang is a professor of computer science at UMass Lowell.
This article is republished from The conversation under Creative Commons license. You can find the original article here.