MilestoneTheory & algorithmsConfirmed

Ewin Tang removes an exponential quantum speedup for recommendation systems

Jul 10, 2018

Ewin Tang develops a classical recommendation algorithm that removes the enormous speed advantage claimed for a quantum approach. The comparison gives both algorithms similar ways to access the data, showing how much the apparent quantum gain depended on that access.

Why it matters

The result shows why proposed quantum advantages must be compared with classical algorithms given comparable access to data.

Ewin Tang · UT Austin

See it on the timeline

Related

• Harrow, Hassidim and Lloyd publish a quantum algorithm for solving linear equations (Nov 19, 2008)