In 1994, Peter Shor created one of the first practical uses for a quantum computer: hacking the internet. Shor, an applied mathematician at the Massachusetts Institute of Technology (MIT), showed how a quantum computer could be exponentially faster than a classical computer at finding the prime number factors of large numbers. Those primes are used as the secret keys that secure most of the encrypted information sent over the internet.
For 30 years, Shor’s algorithm has endured as an example of the promise of quantum computers—although the devices are not yet big or reliable enough to implement it for large numbers. But now, a computer scientist has revealed a new quantum algorithm that might be better than Shor’s. In a preprint first posted to the arXiv server on 12 August, Oded Regev of New York University proposes a scheme that could greatly reduce the number of gates, or logical steps, needed to factor very large numbers. In principle, it could enable a smaller quantum computer to ferret out the secret encryption keys or a bigger machine to decode them faster. “Is this actually going to have any effect?” Regev asks. “My feeling is that yes, it might have a chance.”
To read more, click here.