Квантовый алгоритм поможет распознать язык Дика

Учёными Казанского федерального университета (КФУ), Квантового центра университета Латвии и университета Парижа был разработан алгоритм для квантовых компьютеров, который распознает язык Дика. Научные результаты представлены в  журнале  Leibniz International Proceedings in Informatics – сообщает пресс-служба КФУ.

Язык Дика — множество правильных скобочных структур вместе с пустой структурой над алфавитом {a, b}. Он назван в честь немецкого алгебраиста Вальтера фон Дика и известен среди информатиков и математиков. Решить задачу Дика, или распознать этот язык значит – осуществить проверку правильности расстановки скобок в тексте – поясняет пресс-служба. Учёные предложили решить эту задачу при помощи квантового компьютера. Несмотря на то, что квантовые компьютеры ещё не созданы, учёные уверены в необходимости создания эффективных квантовых алгоритмов, что будет дополнительно стимулировать физиков к скорейшему созданию квантовых компьютеров и сделает их существование более осмысленным.

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

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

«Задача Дика предназначена для проверки кода программы и позволяет выяснить, удовлетворяет ли она правилам или нет. Задача Дика, с одной стороны, является важной подзадачей синтаксических анализаторов и компиляторов, а с другой стороны, интересна с теоретической точки зрения», – рассказал Камиль Хадиев.

Источник: scientificrussia.ru

Комментарии: