Международная команда исследователей из Казанского федерального университета (КФУ), Квантового центра университета Латвии и университета Парижа создала инновационный алгоритм для квантовых компьютеров, способный эффективно распознавать язык Дика.
Язык Дика представляет собой множество всех корректных скобочных последовательностей, включая пустую, над алфавитом {a, b}. Этот язык, названный в честь выдающегося немецкого алгебраиста Вальтера фон Дика, широко известен в математике и информатике. Распознать язык Дика означает проверить правильность расстановки скобок в тексте. Учёные предложили решать эту задачу с помощью квантовых вычислений. Хотя полноценные квантовые компьютеры пока находятся в стадии разработки, исследователи уверены: создание эффективных алгоритмов станет мощным стимулом для физиков и ускорит появление этих революционных машин, придавая их будущему практический смысл.
От классики к кванту: новый подход к известной задаче
Как поясняет Камиль Хадиев, старший научный сотрудник НИЛ «Квантовые методы обработки данных» ИВМиИТ КФУ, классическое решение задачи распознавания языка Дика существует давно. Однако до 2018 года идея квантового алгоритма для нее не рассматривалась. Переломный момент наступил, когда известный специалист по квантовой информатике Скот Ааронсон и его коллеги опубликовали работу, показавшую феноменальную разницу в скорости: программа на обычном компьютере решала бы задачу год, а квантовый компьютер справился бы за считанные секунды.
Стремительное развитие квантовых решений
Спустя два года международная группа учёных представила алгоритм, решающий задачу Дика примерно за 40 секунд. Тогда же было установлено важное теоретическое ограничение: на квантовом компьютере эту задачу принципиально невозможно решить быстрее, чем за 10 секунд.
Практическая ценность задачи Дика
«Задача Дика служит для проверки корректности программного кода, определяя его соответствие заданным правилам. С одной стороны, она является ключевой подзадачей для синтаксических анализаторов и компиляторов, а с другой – представляет значительный теоретический интерес», – подчеркнул Камиль Хадиев.
