In 1994 mathematician Peter Shor figured out how to make quantum computers do things that ordinary classical computers cannot. This work shows that, in principle, a quantum-rule-based machine can efficiently factor large numbers into prime factors—a very difficult task for classical computers, and prime factorization of large numbers is today’s largest Part of the basis of Internet security systems. Optimism followed. At the time, researchers thought maybe we could invent quantum algorithms that could solve a variety of different problems. But it didn’t go well. “It’s a little disappointing,” says Ryan O’Donnell of Carnegie Mellon University. “People say, ‘This is awesome, I’m sure we’re going to find all kinds of other amazing algorithms.’ No.” Scientists Only finding a single, narrow class of problems in a set of criteria called NP can speed up significantly, meaning they have efficient verifiable solutions – such as factorization. This has been the case for nearly three decades. In April, researchers created an entirely new problem that quantum computers should be able tosolve faster (and exponentially faster) than classical computers. It involves computing the input of a complex mathematical process based only on the messy output. Whether this issue is stand-alone or the first of many others remains to be determined.
This article is reprinted from: https://www.solidot.org/story?sid=72102
This site is for inclusion only, and the copyright belongs to the original author.