Communications of the ACM
Quantum Algorithms Conquer a New Kind of Problem
A result published in April expands the territory where quantum computers are known to triumph.
Credit: Kristina Armitage/Quanta Magazine
In 1994, a mathematician figured out how to make a quantum computer do something that no ordinary classical computer could. The work revealed that, in principle, a machine based on the rules of quantum mechanics could efficiently break a large number into its prime factors — a task so difficult for a classical computer that it forms the basis for much of today's internet security.
A surge of optimism followed. Perhaps, researchers thought, we'll be able to invent quantum algorithms that can solve a huge range of different problems.
But progress stalled. "It's been a bit of a bummer trajectory," said Ryan O'Donnell of Carnegie Mellon University. "People were like, 'This is amazing, I'm sure we're going to get all sorts of other amazing algorithms.' Nope." Scientists discovered dramatic speedups only for a single, narrow class of problems from within a standard set called NP, meaning they had efficiently verifiable solutions — such as factoring.
That was the case for nearly three decades. Then in April, researchers invented a fundamentally new kind of problem that a quantum computer should be able to solve exponentially faster than a classical one. It involves calculating the inputs to a complicated mathematical process, based solely on its jumbled outputs. Whether the problem stands alone or is the first in a new frontier of many others has yet to be determined.
From Quanta Magazine
View Full Article
No entries found