Квантовые алгоритмы: сравнение end-to-end сложности с классическими аналогами

В разделе про алгоритмику курса “Интеллект-стек” очень часто упоминается, что квантовые вычислители поменяют алгоритмическую поляну, и уже применяются во многих практических областях.

Я ничего про квантовые алгоритмы не знаю, но заметил в блоге Скотта Ааронсона ссылку, которая, наверное, будет релеванта интересующимся:

Quantum algorithms: A survey of applications and end-to-end complexities” (октябрь 2023)

Аннотация Ааронсона:

I forgot to link to it when it came out more than a month ago—a lot has happened in the meantime!—but Dalzell et al. put up a phenomenal 337-page survey of quantum algorithms, focusing relentlessly on the crucial question of whether there’s actually an end-to-end speedup over the best known classical algorithm for each given task. In countless situations where I would just scream “no, the hypesters are lying to you, this is BS,” Dalzell et al. take dozens of polite, careful, and highly technical pages to spell out why.