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

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