Liberatum.ru

Исследовательская группа в составе Михаэля Бен-Ора (Michael Ben Or), Авинатана Хассидима (Avinatan Hassidim) и Харана Пилпела (Haran Pilpel) предложили новую модель интерактивной системы доказательств.

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

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

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

Несмотря на кажущуюся слабость предложенной схемы, по словам авторов, с ее помощью за 2 раунда коммуникации между двумя доказывающими и одним проверяющим распознается любой язык, принадлежащий к классу NEXP (языков, распознаваемых недетерминированной машиной Тьюринга за экспоненциальное время).