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

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

Ученый КФУ вместе с зарубежными коллегами разработал квантовый алгоритм для распознавания языка Дика

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

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

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

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

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

 

Источник: media.kpfu.ru

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