Ученые записки Казанского университета. Серия Физико-математические науки
К вопросу о сложности классического моделирования квантовых ветвящихся программ
Аблаев Фарид Мансурович
Abstract
В статье рассматриваются синтаксические квантовые ветвящиеся\nпрограммы (СКВП), вычисляющие булевы функции с большой\nнадежностью. Представляется техника классического\nдетерминированного моделирования СКВП, дается оценка сложности\nтакого моделирования. На примере функции MOD\nпоказывается, что оценка сложности детерминированного\nмоделирования близка к оптимальной. Предлагаемая техника\nклассического моделирования СКВП дает другое (конструктивное)\nдоказательство включения класса функций, вычислимых СКВП\nконстантной ширины в класс сложности NC.