Quantum Search Algorithm Is Here

It’s only waiting for the quantum computer to run it.

Robot - Algorithm

The world is full of questions and problems. So everyone is always looking for answers and solutions. This perpetual cycle is what makes search algorithms so important. The better the formula for solving a problem is, the faster you’ll be able to find what it is you’re looking for.

In the ordinary (or classical) world, computers do their thing (including standard searches) using bits that can represent either 0 or 1. But in the quantum world, computers use quantum bits (qubits for short) that can represent 0, or 1, or 0 and 1 at the same time through what is known as superpositioning.

This superposition of states is what gives quantum computing its extraordinary speed. While in this state, an algorithm can simultaneously search both 0 and 1, which means however big a list of search elements is, the algorithm will be able to do its search more quickly.

Typically, the time it takes to do a standard search is said to be proportional to the number of search elements because in its worst case, the algorithm will have to go through all the elements before it finds exactly what it’s looking for.

But with the algorithm designed over two decades ago by computer scientist Lov Grover, the speed of search became proportional not to the number of elements, but to the square root of the number of elements. It’s referred to as a quadratic speed-up and it’s considered a revolutionary feat because of its impact. And it was made possible by using the concepts of quantum mechanics.

Because Grover’s algorithm is a quantum algorithm, it automatically follows that it can only be executed by a quantum computer. And while it only took two years to demonstrate the feasibility of executing Grover’s algorithm on a quantum computer (the earliest one ever built), not much could be done because it only worked using a few qubits. In other words, scaling it up to handle larger and more complex computations was proving to be a challenge.

It was like that in the beginning, and 20 years later, the challenge remained the same. Until a few days ago when researchers from the University of Maryland led by Caroline Figgatt made a startling claim: for the first time ever, they were able to successfully execute Grover’s algorithm on a quantum computer that was scalable.

The team did it by suspending a string of five ytterbium ions in an electromagnetic field. Each ion acted like a magnet that can be oriented up or down by using a laser to turn it from one state to another, or into two states at once. They also used the ions’ repulsive forces to enable the qubits to interact with one another.

Flipping the ions’ state is what they used to store data. Letting the ions interact is what they used to process data. And Grover’s algorithm is what they used to do the quantum computation and show that it does make searching considerably faster. Specifically, their three-qubit quantum computer could do a search faster than a classic eight-bit computer.

Figgatt’s team has taken a big first step. And it’s heating up the race to build the first functional scalable quantum computer even more. Because aside from the obvious financial benefits that will be gained, there’s also the matter of helping the world solve its most complex problems through quantum computing and possibly the most powerful search algorithm to date.

The team’s work has been published in the Quantum Physics journal under the title “Complete 3-Qubit Grover Search on a Programmable Quantum Computer”.

Be the first to comment

Leave a Reply

Your email address will not be published.