MilestoneTheory & algorithmsConfirmed

Aaronson and Ambainis find a near-maximal quantum advantage in queries

Nov 21, 2014

Scott Aaronson and Andris Ambainis introduce Forrelation: deciding whether one Boolean function is correlated with the Fourier transform of another. A quantum algorithm needs one query; any classical one needs many more, close to the largest gap that is possible in this setting.

Why it matters

It shows how big a quantum advantage can be when algorithms can only query a black box, and Forrelation became the basis for later separations such as Raz and Tal's in 2018.

Scott Aaronson · Andris Ambainis · UT Austin

See it on the timeline

Related

• Raz and Tal show a quantum edge over a broad class of classical methods (May 31, 2018)
• Daniel Simon finds an exponential quantum speedup that inspires Shor (Nov 1994)