Учеными научно-исследовательской лаборатории «Квантовые методы обработки данных» Института вычислительной математики и информационных технологий Казанского федерального университета, Квантового центра Университета Латвии и Университета Парижа был разработан алгоритм для квантовых компьютеров, решающий задачу Дика (распознающий язык Дика).

«Задача Дика предназначена для проверки кода программы и позволяет выяснить, удовлетворяет ли она правилам или нет. Задача Дика, с одной стороны, является важной подзадачей синтаксических анализаторов и компиляторов, а с другой стороны, интересна с теоретической точки зрения, – рассказывает один из участников проекта, старший научный сотрудник НИЛ «Квантовые методы обработки данных» ИВМиИТ КФУ Камиль Хадиев. – Классическое решение задачи известно уже давно, однако о квантовом алгоритме для задачи до 2018 года никто не задумывался. Особое внимание к построению квантового алгоритма для задачи Дика появилось после работы известного ученого в мире квантовой информатики Скота Ааронсона и его соавторов два года назад. Ааронсон показал, в частности, что задачу программа для обычного компьютера решала бы год, а на квантовом компьютере ее можно решить за несколько секунд».

По словам К.Хадиева, международной группой исследователей был предложен алгоритм, который для решения этой задачи тратит примерно 40 секунд, и было сделано уточнение, что быстрее, чем за 10 секунд, задача на квантовом компьютере решаться не сможет. Научные результаты представлены в журнале Leibniz International Proceedings in Informatics.

Камиль Хадиев объяснил, почему ученые создают квантовые алгоритмы, хотя квантового компьютера пока нет: «Созданием квантовых алгоритмов ученые занимаются параллельно с созданием самого квантового компьютера. Появление очередного эффективного алгоритма подстегивает физиков к скорейшему созданию квантовых компьютеров и делает существование квантового компьютера все более осмысленным».