MilestoneTheory & algorithmsConfirmed

Yamakawa and Zhandry show verifiable quantum advantage without structure

Apr 5, 2022

Takashi Yamakawa and Mark Zhandry show that, relative to a random oracle, some NP search problems are solvable by quantum computers but not by classical ones. Unlike Shor's or Simon's algorithms, the problem needs no special hidden structure, and answers can be checked classically.

Why it matters

It challenged the belief that exponential quantum speedups need highly structured problems, a central question about which tasks quantum computers can do better.

Takashi Yamakawa · Mark Zhandry

See it on the timeline

Related

• Daniel Simon finds an exponential quantum speedup that inspires Shor (Nov 1994)
• Aaronson and Ambainis find a near-maximal quantum advantage in queries (Nov 21, 2014)