Квантовые алгоритмы давно обещают революцию в вычислениях, но на практике большинство из них пока проигрывают классическим в стабильности, надежности и масштабируемости. Настоящих примеров, когда квантовый подход показывает ощутимое преимущество, все еще очень мало. Тем ярче выглядит новая разработка от команды Google — алгоритм DQI (decoded quantum interferometry). Его уже называют потенциальным прорывом. Открытие пока не удалось воспроизвести на классических вычислительных системах, несмотря на попытки сразу нескольких независимых научных групп. Даже один из самых известных скептиков в области квантовых технологий, профессор Гила Калаи, признал значимость нового подхода и назвал его «настоящим поводом для научного праздника». Работа с описанием алгоритма размещена на сервере препринтов arXiv.
Основная идея DQI строится на использовании интерференции, то есть наложения квантовых волн. Каждое возможное решение задачи в такой системе представляется как волна, и чем лучше решение, тем выше «амплитуда», то есть вероятность его обнаружения в финальном измерении. Однако усилить нужную волну — это еще полдела. Главная трудность заключалась в том, как выбрать ее из множества слабых и хаотичных сигналов. Чтобы справиться с этой задачей, ученые обратились к техникам из теории кодирования — области, которая занимается тем, как передавать и восстанавливать информацию, даже если она повреждена шумами или искажениями.
Оказалось, что проблема поиска оптимального решения очень похожа на задачу расшифровки зашумленного сообщения. Это и стало ключевым поворотом: алгоритм фактически «декодирует» пространство решений, выявляя те, что дают наилучший результат. Такой подход позволил объединить квантовую интерферометрию с методами, которые десятилетиями применялись в телекоммуникациях и криптографии. Получилась редкая комбинация фундаментальной физики и инженерной практики.
Что интересно, идея не появилась в результате целенаправленного поиска оптимизационного метода. Исследователь Стивен Джордан, один из авторов DQI, начал с теоретических размышлений о том, как использовать волновую природу квантовых частиц. Вместе с коллегой Ноа Шатти он проверял различные подходы и сначала не получил ощутимых результатов — классические алгоритмы снова и снова оказывались лучше. Все изменилось, когда они решили попробовать старую технику коррекции ошибок, предложенную еще в 1960-х годах. Неожиданно она показала стабильный и убедительный квантовый выигрыш.
Сейчас DQI существует только как математическая модель. На практике проверить его пока невозможно — существующие квантовые компьютеры недостаточно мощны, чтобы реализовать алгоритм в полной мере. Однако по мнению самих разработчиков и приглашенных экспертов, его потенциальная применимость охватывает широкий спектр задач: от построения маршрутов доставки до шифрования и восстановления поврежденных данных. Везде, где нужно быстро найти оптимальный вариант среди огромного числа возможных, DQI может дать преимущество.
Важно и то, что даже если в будущем будет найден классический аналог, сама структура DQI уже вдохновляет исследователей — как в квантовой, так и в классической области. По словам Эвин Танг, известной своими работами по поиску классических аналогов квантовых решений, статья о DQI достаточно убедительна, чтобы привлечь внимание целого сообщества. «Посмотрите повнимательнее на эту задачу — она того стоит», — сказала она.
Для всех, кто следит за развитием квантовых вычислений, это важный момент. Подобные случаи, когда квантовая теория получает конкретное математическое и практическое подтверждение превосходства над классическим подходом, крайне редки. И хотя впереди еще много работы, сам факт появления алгоритма, который нельзя быстро «деквантовать», уже делает DQI вехой в истории квантовых технологий.
На этом фоне особенно интересно смотрится свежая работа, где исследователи пошли другим путем — не замедлением, а расширением возможностей измерения. Вместо долгого «прослушивания» кванта они добавляют вспомогательные кубиты, чтобы быстрее уловить нужную информацию — подробнее об этом можно прочитать в следующем материале.
