MilestoneTheory & algorithmsConfirmed

Raz and Tal show a quantum edge over a broad class of classical methods

May 31, 2018

Ran Raz and Avishay Tal design a black-box problem: algorithms can query a hidden function but cannot inspect its inner workings. In this setting, a quantum algorithm solves the problem efficiently, while a broad class of classical methods cannot, even with powerful extra aids.

Why it matters

The result shows that quantum algorithms can outperform more than ordinary classical computation in a precisely defined setting, strengthening the theoretical case for quantum computing.

Ran Raz · Avishay Tal · Princeton · Stanford

See it on the timeline

Related

• Daniel Simon finds an exponential quantum speedup that inspires Shor (Nov 1994)