0909 GMT January 19, 2018
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, phys.org wrote.
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.
Figgatt said, "This work is the first implementation of a 3-qubit Grover search algorithm in a scalable quantum computing system.
"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 eight items, a classical algorithm makes one random query and, if that fails, it makes a second random guess — in total, guessing two out of eight items, resulting in a 25 percent success rate.
Grover's algorithm, on the other hand, first initializes the system in a quantum superposition of all eight 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 eight-item database, the theoretical success rate increases to 78 percent. 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 percent or 44 percent, 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 percent and 100 percent for classical and quantum computers, respectively. The implementation demonstrated here achieved success rates of 68 percent and 75 percent 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.
Figgatt said, "Moving forward, we plan to continue developing systems with improved control over more qubits."