“Searching large, unordered databases for a desired item is a time-consuming task for classical computers, but quantum computers are expected to perform these searches much more quickly. Previous research has shown that Grover’s search algorithm, proposed in 1996, is an optimal quantum search algorithm, meaning no other quantum algorithm can search faster. However, implementing Grover’s algorithm on a quantum system has been challenging.
Now in a new study, researchers have implemented Grover’s algorithm with trapped atomic ions. The algorithm uses three qubits, which corresponds to a database of 8 (23) items. When used to search the database for one or two items, the Grover algorithm’s success probabilities were—as expected—significantly higher than the best theoretical success probabilities for classical computers.
The researchers, Caroline Figgatt et al., at the University of Maryland and the National Science Foundation, have published a paper on their results in a recent issue of Nature Communications.
“This work is the first implementation of a 3-qubit Grover search algorithm in a scalable quantum computing system,” Figgatt told Phys.org. “Additionally, this is the first implementation of the algorithm using Boolean oracles, which can be directly compared with a classical search.”
The classical approach to searching a database is straightforward. Basically, the algorithm randomly guesses an item, or “solution.” So, for example, for a single search iteration on a database of 8 items, a classical algorithm makes one random query and, if that fails, it makes a second random guess—in total, guessing 2 out of 8 items, resulting in a 25% success rate.
Grover’s algorithm, on the other hand, first initializes the system in a quantum superposition of all 8 states, and then uses a quantum function called an oracle to mark the correct solution. As a result of these quantum strategies, for a single search iteration on an 8-item database, the theoretical success rate increases to 78%. With a higher success rate comes faster search times, as fewer queries are needed on average to arrive at the correct answer.
In the implementation of Grover’s algorithm reported here, the success rate was lower than the theoretical value—roughly 39% or 44%, depending on the oracle used—but still markedly higher than the classical success rate.
The researchers also tested Grover’s algorithm on databases that have two correct solutions, in which case the theoretical success rates are 47% and 100% for classical and quantum computers, respectively. The implementation demonstrated here achieved success rates of 68% and 75% for the two oracle types—again, better than the highest theoretical value for classical computers.
The researchers expect that, in the future, this implementation of Grover’s algorithm can be scaled up to larger databases. As the size of the database increases, the quantum advantage over classical computers grows even larger, which is where future applications will benefit.
“Moving forward, we plan to continue developing systems with improved control over more qubits,” Figgatt said.”