Quantum Algorithms Conquer a New Kind of Problem

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. "It's been a bit of a bummer trajectory," said Ryan O'Donnell of Carnegie Mellon University.