Main Content

Quantum Computing Now Has a Powerful Search Tool

Back in 1996, a computer scientist called Lov Grover at Bell Labs in New Jersey unveiled an unusual algorithm for searching through a database. Searching algorithms are among the most important in computer science. They make possible mundane tasks such as hunting through phones books but also more exotic tasks such as breaking cryptographic codes. This kind of algorithm is ubiquitous in computer science. So any way of speeding up the task is hugely significant. A standard search takes a period of time that is roughly proportional to the number of elements in the search. That’s because, in the worst-case scenario, the algorithm has to search through all the elements to find just one. But Grover’s algorithm is different. The time it takes is proportional to the square root of the number of elements. Computer scientists call this a quadratic speed-up. And in a world where speed increases of a few fractions of a percent are hugely valuable, a quadratic speed-up is a towering achievement.”

Link to article