Казанский (Приволжский) федеральный университет, КФУ
КАЗАНСКИЙ
ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ
 
RSS Ins Вконтакте twitter facebook
СРАВНИТЕЛЬНАЯ СЛОЖНОСТЬ КВАНТОВЫХ И КЛАССИЧЕСКИХ OBDD ДЛЯ ВСЮДУ ОПРЕДЕЛЕННЫХ И ЧАСТИЧНЫХ ФУНКЦИЙ
Форма представленияСтатьи в российских журналах и сборниках
Год публикации2015
Языкрусский
  • Гайнутдинова Аида Фаритовна, автор
  • Библиографическое описание на языке оригинала Гайнутдинова А.Ф. Сравнительная сложность квантовых и классических OBDD для всюду определенных и частичных функций // Известия высших учебных заведений. Математика. - 2015. - № 11. - С. 32-43.
    Аннотация В работе рассматривается известная модель для вычисления булевых функций -- упорядоченные ветвящиеся диаграммы решений (OBDD -- Ordered Binary Decision Diagrams). Исследуется сравнительная сложность по ширине квантовых, классических детерминированных и вероятностных, а также недетерминированных (классических и квантовых) OBDD. Известно, что для всюду определенных функций квантовые OBDD, вычисляющие с ограниченной ошибкой, могут быть экспоненциально эффективнее детерминированных и вероятностных OBDD. В работе показывается, что такие квантовые OBDD также могут быть экспоненциально эффективнее недетерминированных OBDD, как классических, так и квантовых. Также в работе показывается, что при вычислении частичных функций разрыв в сложности может быть усилен. Для частичной функции, зависящей от параметра $k$, квантовая OBDD, вычисляющая без ошибки, имеет ширину 2. Детерминированная OBDD и стабильная вероятностная OBDD, вычисляющая с ограниченной ошибкой, для данной функции имеют ширину э
    Ключевые слова Упорядоченные ветвящиеся диаграммы решений, частичные функции, квантовые вычисления, недетерминированные OBDD, вероятностные OBDD, детерминированные OBDD, сложность.
    Название журнала Известия ВУЗов, Математика
    Пожалуйста, используйте этот идентификатор, чтобы цитировать или ссылаться на эту карточку https://repository.kpfu.ru/?p_id=123588

    Полная запись метаданных