From Singularity Hub, October 2:
One of the most well-established and disruptive uses for a future quantum computer is the ability to crack encryption. A new algorithm could significantly lower the barrier to achieving this.
Despite all the hype around quantum computing, there are still significant question marks around what quantum computers will actually be useful for. There are hopes they could accelerate everything from optimization processes to machine learning, but how much easier and faster they’ll be remains unclear in many cases.
One thing is pretty certain though: A sufficiently powerful quantum computer could render our leading cryptographic schemes worthless. While the mathematical puzzles underpinning them are virtually unsolvable by classical computers, they would be entirely tractable for a large enough quantum computer. That’s a problem because these schemes secure most of our information online.
The saving grace has been that today’s quantum processors are a long way from the kind of scale required. But according to a report in Science, New York University computer scientist Oded Regev has discovered a new algorithm that could reduce the number of qubits required substantially.
The approach essentially reworks one of the most successful quantum algorithms to date. In 1994, Peter Shor at MIT devised a way to work out which prime numbers need to be multiplied together to give a particular number—a problem known as prime factoring.
For large numbers, this is an incredibly difficult problem that quickly becomes intractable on conventional computers, which is why it was used as the basis for the popular RSA encryption scheme....
....MUCH MORE
