Все знают алгоритм Гровера для поиска в неупорядоченной базе данных. На бумаге он выглядит шикарно – квадратичный выигрыш во времени по сравнению с классическими методами. Но вот в чем вопрос: насколько это реально применимо на практике с теми квантовыми компьютерами которые у нас есть сейчас или будут в ближайшем будущем?

Мне кажется, мы слишком часто слышим о гипотетических ускорениях, забывая про реальные ограничения: размер регистров, количество кубитов, декогеренция, сложность инициализации и измерения. Да, для некоторых специфических задач это может быть прорыв. Но для большинства повседневных поисков, думаю, классические алгоритмы останутся вне конкуренции еще очень долго. Ну и теория информации тут тоже играет свою роль, конечно.

А вы как думаете? Стоит ли алгоритм Гровера всей той шумихи, или это больше академический интерес?