ArXiv: [https://arxiv.org/abs/2204.02063](https://arxiv.org/abs/2204.02063 "https://arxiv.org/abs/2204.02063") [[Scott Aaronson]] [writes](https://scottaaronson.blog/?p=6362): > Last week, Takashi Yamakawa and Mark Zhandry posted a preprint to the arXiv, [“Verifiable Quantum Advantage without Structure,”](https://arxiv.org/abs/2204.02063) that represents some of the most exciting progress in quantum complexity theory in years. I wish I’d thought of it. tl;dr they show that relative to a random oracle (!), there’s an NP search problem that quantum computers can solve exponentially faster than classical ones. And yet this is 100% consistent with the Aaronson-Ambainis Conjecture!