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.
Grover’s trick was to employ the strange but powerful ideas behind quantum mechanics. In the classical world, bits are just 0s and 1s. But in the quantum world, a single quantum bit, or qubit, can be a 0 and 1 at the same time. Physicists say the qubit is in a superposition of states.
The superposition is the key. In this state, an algorithm can search both the 0 and the 1 at the same instant. Because it can search more than one element at the same time, a quantum algorithm can search through a list much more quickly than an algorithm limited by the plodding pace of classical physics.
Quantum algorithms must be implemented by a quantum computer, and in 1996, when Grover did his work, these were little more than a distant dream. But the breakthrough came quickly. Physicists demonstrated the first primitive quantum computer in 1998 and showed how it could execute Grover’s algorithm in the same year.
But this particular form of quantum computing was extremely limited. It worked on a few qubits but no more and, even in principle, could never be scaled up to larger computations. This problem of building and demonstrating scalable quantum computers has plagued the discipline ever since.
Now, some 20 years later, physicists are beginning to build quantum computers that have the potential to scale and so are capable of more powerful computations. And today, Caroline Figgatt and pals from the University of Maryland say they have executed Grover’s algorithm on a scalable quantum computer for the first time.
To read more, click here.