Квантовые алгоритмы могут находить выход из лабиринтов экспоненциально быстрее, чем классические, за счет забывания путей, по которым они шли. Новый результат предполагает, что компромисс может быть неизбежен.
Представьте, что вы посещаете лабиринт с друзьями. Вы вышли из выхода вскоре после входа и ждёте несколько часов, прежде чем появятся ваши друзья. Естественно, они спрашивают о пути, по которому вы шли — вы ведь можете проследить свои шаги и показать им путь, верно?
Неверно в мире, где правят странные законы квантовой физики. Двадцать лет назад исследователи квантовых вычислений разработали алгоритм, который использовал эти законы для прохождения опредёленного вида математического лабиринта намного быстрее, чем любой алгоритм, работающий на обычном классическом компьютере. Но за это ускорение приходится платить: быстрый квантовый алгоритм находит выход, но понятия не имеет, как он туда попал.
Исследователи давно задавались вопросом, неизбежен ли этот компромисс. Неужели невозможно быстро найти выход, не забыв дорогу?