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

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

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

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

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

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

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

Иллюстрация к статье: Яндекс.Картинки
Самые свежие новости медицины в нашей группе на Одноклассниках

Оставить комментарий

Вы можете использовать HTML тэги: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>