Недавно эта проблема обсуждались лидерами в этой области на одной из конференций, обсуждение опубликовано вот здесь:
https://arxiv.org/abs/2506.19232

Эдвард Фархи (Farhi) высказал мнение, что такая "бедная" ситуация с квантовыми алгоритмами связана с тем, что среди исследователей здесь утвердился стандарт, что сложность, эффективность квантового алгоритма надо непременно строго математически оценить и сравнить с наилучшим классическим алгоритмом. Он считает, что такое негласное требование сдерживает развитие квантовых алгоритмов. В качестве аргумента он привёл то, что полно классических алгоритмов, о которых мы не имеем математически строгих результатов и даже особо не понимаем, почему они работают, но они работают. Характерный пример - алгоритмы машинного обучения, другой пример - алгоритмы оптимизации через так называемую "имитацию отжига". От себя могу добавить и знаменитый симплекс-метод решения задач линейного программирования (класс оптимизационных задач). Формально он имеет экспоненциальную сложность, но в реальности работает хорошо в практических ситуациях. Поэтому, считает Фархи, и квантовые алгоритмы надо просто изобретать и экспериментировать с ними, особенно когда всё-таки появится полноценный квантовый компьютер для этого.

Ещё один из участников обсуждения добавил, что, если мы быстрее изобрели полезный алгоритм именно для квантового компьютера и это позволило, например, найти новое лекарство, то так ли важно, существует ли в теории аналогичный классический алгоритм или нет.

Скотт Ааронсон (Aaronson) оппонировал этому подходу, тоже, как и я в этом канале недавно, напомнив о сказке "Каша из топора" (или в западном варианте - "Stone soup" - "Каменный суп":)). Он говорит, что в той гипотетической ситуации будущего, когда мы открыли именно квантовый полезный алгоритм, если бы мы потратили столько же времени на поиск классического алгоритма, то, может, открыли бы и его. То есть слово "квантовый" как бы завораживает, вдохновляет на поиск, вот как топор в той каше, но на самом деле всё то же самое может существовать и без этого "топора". Поэтому он считает, что просто предлагать квантовые алгоритмы, не сравнивая их с существующими и с теоретически возможными классическими, - это неправильно, это вводит в заблуждение, мы можем так увлечься "кашами из топора".

Ещё тут часто высказывают аргумент, что и на заре обычных наших классических компьютеров никто, конечно, не подозревал, как они изменят всё наше общество, тоже думали, что они нужны в единичных экземплярах только для очень специфических задач (среди которых, кстати, и тогда был взлом шифров: вспомним про "Энигму"). Поэтому и квантовый компьютер надо сначала создать, а применения потом найдём.

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

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