К вопросу о сложности классического моделирования квантовых ветвящихся программ

В статье рассматриваются синтаксические квантовые ветвящиеся программы (СКВП), вычисляющие булевы функции с большой надежностью. Представляется техника классического детерминированного моделирования СКВП, дается оценка сложности такого моделирования. На примере функции $\mathrm{MOD}_m$ показывается, что оценка сложности детерминированного моделирования близка к оптимальной. Предлагаемая техника классического моделирования СКВП дает другое (конструктивное) доказательство включения класса функций, вычислимых СКВП константной ширины в класс сложности $NC^1$.