Researchers implement 3-qubit Grover search on a quantum computer

January 11, 2018 by Lisa Zyga, feature
grover search
The three stages of the 3-qubit Grover search algorithm: initialization, oracle, and amplification. Credit: C. Figgatt et al. Published in Nature Communications

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 with trapped atomic ions. The algorithm uses three qubits, which corresponds to a 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 .

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 computing system," Figgatt told "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.

Explore further: Quantum computing with molecules for a quicker search of unsorted databases

More information: C. Figgatt et al. "Complete 3-Qubit Grover search on a programmable quantum computer." Nature Communications. DOI: 10.1038/s41467-017-01904-7

Related Stories

Solving systems of linear equations with quantum mechanics

June 9, 2017

(—Physicists have experimentally demonstrated a purely quantum method for solving systems of linear equations that has the potential to work exponentially faster than the best classical methods. The results show ...

Developing quantum algorithms for optimization problems

July 26, 2017

Quantum computers of the future hold promise for solving complex problems more quickly than ordinary computers. For example, they can factor large numbers exponentially faster than classical computers, which would allow them ...

Quantum computer solves problem, without running

February 22, 2006

By combining quantum computation and quantum interrogation, scientists at the University of Illinois at Urbana-Champaign have found an exotic way of determining an answer to an algorithm – without ever running the algorithm.

Recommended for you

Nanoparticle gel controls twisted light with magnetism

January 22, 2018

"Help me, Obi Wan Kenobi. You're my only hope." For many of those around at the release of Star Wars in 1977, that scene was a first introduction to holograms—a real technology that had been around for roughly 15 years.

On the rebound

January 22, 2018

Our bodies have a remarkable ability to heal from broken ankles or dislocated wrists. Now, a new study has shown that some nanoparticles can also "self-heal" after experiencing intense strain, once that strain is removed.


Please sign in to add a comment. Registration is free, and takes less than a minute. Read more

Click here to reset your password.
Sign in to get notified via email when new comments are made.