Эта публикация цитируется в
14 статьях
Сравнительная сложность квантовых и классических OBDD для всюду определенных и частичных функций
А. Ф. Гайнутдинова Кафедра теоретической кибернетики, Казанский (Приволжский) федеральный университет, ул. Кремлевская, д. 18, г. Казань, 420008, Россия
Аннотация:
Рассматривается известная модель для вычисления булевых функций – упорядоченные ветвящиеся диаграммы решений (OBDD – Ordered Binary Decision Diagrams). Исследуется сравнительная сложность по ширине квантовых, классических детерминированных и вероятностных, а также недетерминированных (классических и квантовых) OBDD. Известно, что для всюду определенных функций квантовые OBDD, вычисляющие с ограниченной ошибкой, могут быть экспоненциально эффективнее детерминированных и вероятностных OBDD. В работе показывается, что такие квантовые OBDD также могут быть экспоненциально эффективнее недетерминированных OBDD, как классических, так и квантовых. Также в работе показывается, что при вычислении частичных функций разрыв в сложности может быть усилен. Для частичной функции, зависящей от параметра
$k$, квантовая OBDD, вычисляющая без ошибки, имеет ширину два. Детерминированная OBDD и стабильная вероятностная OBDD, вычисляющая с ограниченной ошибкой, для данной функции имеют ширину, экспоненциально зависящую от параметра
$k$.
Ключевые слова:
упорядоченные ветвящиеся диаграммы решений, частичные функции, квантовые вычисления, недетерминированные OBDD, вероятностные OBDD, детерминированные OBDD, сложность.
УДК:
519.7 Поступила: 26.03.2014