Synopsis: Quantum Search Gets an Update

A well-known quantum search method, called Grover’s algorithm, has been modified to handle a wider variety of search problems.

Compared to classical database searches, quantum-based algorithms can potentially work much faster. They can also provide some speedup to the solution of hard math problems, like inverting one-way functions. The catch is that standard quantum search methods require a precise number of iterations, otherwise they miss their target. Researchers have found a way to avoid this problem with a quantum search that always gets closer to the solution after every iteration.

Imagine you are looking for “Smith” in an unsorted phone directory. Classically, the time it takes to perform this task goes as the size of the list divided by the number of times Smith appears. Quantum search methods, such as Grover’s algorithm, can presumably do the job in the square root of the classical time. However, you have to select the right number of iterations, which requires knowing beforehand how many Smiths there are in the list.

Theodore Yoder and his colleagues at the Massachusetts Institute of Technology, Cambridge, devised a method that achieves quantum time savings even when the number of targets is unknown. Like previous methods, each entry in the list is represented by a quantum state with a particular amplitude and phase. Through phase rotations and interference effects, the amplitude of the target “Smith” state increases—making it more likely to be measured than non-“Smith” states. The difficulty with Grover’s algorithm is that the target amplitude reaches a maximum and then starts to decrease when the program runs too long. The new algorithm overcomes this by introducing variable phase rotations (rather than fixed 180° rotations) that always amplify the target probability, so that the search keeps getting closer and closer to the solution. The researchers note that their quantum software, which takes inspiration from frequency filters in electronics, can also be used for quantum error correction.

This research is published in Physical Review Letters.

– Michael Schirber


More Features »


More Announcements »

Subject Areas

Quantum InformationQuantum Physics

Previous Synopsis


Unraveling the Vortex

Read More »

Next Synopsis

Related Articles

Synopsis: Interrupting Flow in a 2D Topological Insulator
Topological Insulators

Synopsis: Interrupting Flow in a 2D Topological Insulator

Theorists predict that backscattering of electrons by nonmagnetic impurities can disrupt current flow in a 2D topological insulator, in agreement with experiments. Read More »

Viewpoint: Alkaline Atoms Held with Optical Tweezers
Quantum Information

Viewpoint: Alkaline Atoms Held with Optical Tweezers

Three separate groups demonstrate the trapping of two-electron atoms in arrays of optical tweezers, opening up new opportunities for quantum simulation and many-body studies. Read More »

Synopsis: A Possible Quantum Computing Boost 
Quantum Information

Synopsis: A Possible Quantum Computing Boost 

A hybrid quantum-classical computing algorithm could solve a basic computer science problem faster than a classical computer. Read More »

More Articles