Skip to Content
Computing

Quantum Computing Now Has a Powerful Search Tool

Quantum search algorithms could change the face of computing now that physicists have shown how to execute them on a scalable device.
Grover's algorithm

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.

The work demonstrates the rapid speed-up of quantum computations and paves the way for more ambitious work with the algorithm that could start cracking real-world challenges such as code breaking.

The quantum computer that Figgatt and co work with consists of a string of five ytterbium ions suspended in an electromagnetic field. Each ion is like a tiny magnet that can be oriented up or down and flipped from one state to the other with a laser. In this way, each ion can store information: a 1 for spin up and a 0 for spin down, for example. And because they are quantum objects, the ions can exist in a superposition of these states.

The ions also interact with each other via the repulsive forces associated with their positive charge. This interaction allows one qubit to interact with another qubit to process information. This is the essence of quantum computation. The order of steps in this computation is the quantum algorithm, in this case Grover’s algorithm.

Figgatt and co use their system to create a three-qubit quantum computer that can store up to eight items in a database. They then perform Grover’s algorithm to show that is possible to find an item significantly faster, on average, than a classical computer which would require at least eight bits. “We report results for a complete three-qubit Grover search algorithm using the scalable quantum computing technology of trapped atomic ions, with better-than-classical performance,” say Figgatt and co.

That’s interesting work with significant potential. “This paves the way for more extensive use of the Grover search algorithm in solving larger problems on quantum computers, including using the circuit as a subroutine for other quantum algorithms,” say the team.

But the work also provides an interesting glimpse into the race to build powerful quantum computers. The winner of this race is likely to reap huge financial rewards, but nobody is quite sure which technology is best.

This world has been thrown into confusion by a Canadian startup called D-Wave Systems which has sold seemingly powerful quantum computers to companies such as Google and Lockheed Martin. These computers operate with 1,000 qubits, far more than any other technology.

But many theorists say D-Wave’s claims are overblown and that its machines cannot produce anywhere near the kind of computational power that other quantum computers should be capable of.

That’s why many groups are trying to commercialize other quantum technologies that differ dramatically in the way they store and process quantum information. These variously rely on photons, electrons, atoms, ions, and molecules to do their quantum bidding.

Of these techniques, one of the oldest and best developed is ion trap quantum computing, and the University of Maryland group is a world leader in this area. Indeed, the group’s leader, Chris Monroe, has a startup called IonQ that aims to commercialize this technology.

So the demonstration of a scalable quantum computer that can implement Grover’s algorithm, albeit with only three qubits, can be seen as a statement of intent.

In 1998, after the first implementation of Grover’s algorithm, there was a range of opinion about how long it would take physicists to make the next step scalable computers. A number of startups duly formed and collapsed based on optimistic forecasts. But, at that time, 20 years was at the pessimistic end of the spectrum of predictions. The fact that it has taken this long puts into perspective the difficulty of the task.

Controlling the universe on the quantum scale is hard. An interesting question now for technologists and venture capitalists is whether the rate of technological progress can be significantly accelerated.

Ref: arxiv.org/abs/1703.10535: Complete 3-Qubit Grover Search on a Programmable Quantum Computer

Deep Dive

Computing

Linux hack concept
Linux hack concept

The US military wants to understand the most important software on Earth

Open-source code runs on every computer on the planet—and keeps America’s critical infrastructure going. DARPA is worried about how well it can be trusted

Close up of worker inspecting chip in a clean room
Close up of worker inspecting chip in a clean room

Corruption is sending shock waves through China’s chipmaking industry

The arrests of several top semiconductor fund executives could force the government to rethink how it invests in the sector.

inflection point post-NSO concept
inflection point post-NSO concept

The hacking industry faces the end of an era

But even if NSO Group is no more, there are plenty of rivals who will rush in to take its place. And the same old problems haven’t gone away.

The Western Union Building, 60 Hudson Street, c. 1931.
The Western Union Building, 60 Hudson Street, c. 1931.

Energy-hungry data centers are quietly moving into cities

Companies are pushing more server farms into the hearts of population centers.

Stay connected

Illustration by Rose WongIllustration by Rose Wong

Get the latest updates from
MIT Technology Review

Discover special offers, top stories, upcoming events, and more.

Thank you for submitting your email!

Explore more newsletters

It looks like something went wrong.

We’re having trouble saving your preferences. Try refreshing this page and updating them one more time. If you continue to get this message, reach out to us at customer-service@technologyreview.com with a list of newsletters you’d like to receive.