Разработанный учеными алгоритм впервые демонстрирует убедительное квантовое преимущество.
Квантовые алгоритмы долгое время считались многообещающими, но на практике их преимущество над классическими методами редко оказывалось неоспоримым. Каждый раз, когда появлялось сообщение о прорыве, классические алгоритмы вскоре догоняли квантовые решения. Однако новый алгоритм, предложенный исследователями из Google Quantum AI, может стать исключением.
Исследователи представили Decoded Quantum Interferometry (DQI) — квантовый алгоритм, который, по их утверждению, решает задачи оптимизации быстрее всех известных классических методов. Пока что никто не смог доказать обратное. В центре внимания алгоритма — поиск наилучшего решения среди множества вариантов, что особенно актуально для таких областей, как кодирование данных и криптография. Задача, которую он решает, напоминает нахождение математической функции, проходящей через заданные точки, но с ограничением на сложность этой функции. Подобные проблемы встречаются в самых разных сферах, где требуется точность при передаче информации.
Работа над алгоритмом началась не с поиска конкретной задачи, а с изучения фундаментальных свойств квантовых вычислений. Один из авторов исследования, Стивен Джордан, обратил внимание на то, что квантовая физика позволяет представлять возможные решения в виде волн, где высота волн соответствует их вероятности. Это привело к идее использования квантового преобразования Фурье, чтобы выявить наилучшие варианты. Однако на пути к практической реализации возникло препятствие: как определить, какая волна действительно несет правильный ответ? Ответ оказался в старых методах кодирования данных. Исследователи обнаружили, что процесс выбора наилучшего решения напоминает процесс исправления ошибок в кодах, используемых для защиты информации при передаче. Это направление хорошо изучено в информатике, и методы, разработанные десятилетия назад, помогли адаптировать новый квантовый алгоритм.
Пока что никто не нашел классического метода, который мог бы конкурировать с DQI. Это делает алгоритм редким случаем, когда квантовое вычисление действительно дает ощутимое преимущество. Хотя технология квантовых компьютеров все еще не достигла уровня, при котором можно было бы полноценно протестировать алгоритм в реальных условиях, интерес к нему уже высок. Эксперты осторожно оценивают открытие, отмечая, что классические алгоритмы часто догоняют квантовые спустя некоторое время. Но даже если это произойдет, разработка DQI может привести к новым идеям как в квантовых, так и в классических вычислениях.
Несмотря на скептицизм, связанный с большинством заявлений о квантовом превосходстве, многие специалисты считают этот алгоритм прорывом. Гил Калаи, известный критик квантовых вычислений, признал, что появление любого нового квантового алгоритма, способного обойти классические методы, — это важное событие. Эвин Танг, известный тем, что разрабатывает классические алгоритмы, способные конкурировать с квантовыми, отметил, что DQI может стать стимулом для поиска новых решений в классическом программировании.
Главный вопрос остается открытым: удастся ли когда-нибудь классическим вычислениям догнать DQI, или же этот алгоритм войдет в историю как одно из первых убедительных доказательств реального квантового превосходства? Пока ответ на него неизвестен, но одно можно сказать точно: квантовая гонка продолжается.