Synopsis: The quantum shortcut to a solution

A quantum algorithm that uses the solution to a set of linear equations provides an exponential speedup by comparison with classical alternatives.
Synopsis figure

Considering the volume of research on quantum computing, there are surprisingly few quantum algorithms that are known to perform faster than their classical counterparts—the most famous example being Shor’s algorithm for factoring a large number.

Writing in Physical Review Letters, Aram Harrow at the University of Bristol, UK, and Avinatan Hassidim and Seth Lloyd at MIT in the US propose a quantum algorithm for solving a set of linear equations that, within some constraints, is exponentially faster that any classical algorithm. The algorithm could potentially have widespread applicability in fields as varied as biostatistics, ecology, and engineering, all of which rely heavily on solving linear equations.

Strictly speaking, the algorithm of Harrow et al. does not find the solution to the linear equations, but some function of the solution, such as a comparison between two stable states that evolve according to different processes. Though many real-world systems may not fall into the limited set of conditions the authors consider, this proposal provides another example to help us understand why quantum algorithms work better than classical ones. – Jessica Thomas


More Announcements »

Subject Areas

Quantum Information

Previous Synopsis

Strongly Correlated Materials

Theory tackles strong interactions

Read More »

Related Articles

Viewpoint: Hiding a Quantum Cache in Diamonds
Quantum Information

Viewpoint: Hiding a Quantum Cache in Diamonds

Entanglement purification, a vital enabler for practical quantum networks, has been shown to be feasible with secluded nuclear memories in diamond. Read More »

Viewpoint: Classical Simulation of Quantum Systems?

Viewpoint: Classical Simulation of Quantum Systems?

Richard Feynman suggested that it takes a quantum computer to simulate large quantum systems, but a new study shows that a classical computer can work when the system has loss and noise. Read More »

Focus: <i>Landmarks</i>—Correcting Quantum Computer Errors
Quantum Physics

Focus: Landmarks—Correcting Quantum Computer Errors

In the mid-1990s, researchers proposed methods to preserve the integrity of quantum bits—techniques that may become the key to practical quantum computing on a large scale. Read More »

More Articles