Сравнительная сложность квантовых и классических OBDD для всюду определенных и частичных функций

Рассматривается известная модель для вычисления булевых функций – упорядоченные ветвящиеся диаграммы решений (OBDD – Ordered Binary Decision Diagrams). Исследуется сравнительная сложность по ширине квантовых, классических детерминированных и вероятностных, а также недетерминированных (классических и квантовых) OBDD. Известно, что для всюду определенных функций квантовые OBDD, вычисляющие с ограниченной ошибкой, могут быть экспоненциально эффективнее детерминированных и вероятностных OBDD. В работе показывается, что такие квантовые OBDD также могут быть экспоненциально эффективнее недетерминированных OBDD, как классических, так и квантовых. Также в работе показывается, что при вычислении частичных функций разрыв в сложности может быть усилен. Для частичной функции, зависящей от параметра $k$, квантовая OBDD, вычисляющая без ошибки, имеет ширину два. Детерминированная OBDD и стабильная вероятностная OBDD, вычисляющая с ограниченной ошибкой, для данной функции имеют ширину, экспоненциально зависящую от параметра $k$.