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

KAZAN
FEDERAL UNIVERSITY

- RUS
- 中文
- ES

СРАВНИТЕЛЬНАЯ СЛОЖНОСТЬ КВАНТОВЫХ И КЛАССИЧЕСКИХ OBDD ДЛЯ ВСЮДУ ОПРЕДЕЛЕННЫХ И ЧАСТИЧНЫХ ФУНКЦИЙ

Form of presentation

Articles in Russian journals and collections

Year of publication

2015

Язык

русский

Authors, employees of KFU

Gaynutdinova Aida Faritovna, author

Bibliographic description in the original language

Gaynutdinova A.F. Sravnitelnaya slozhnost kvantovykh i klassicheskikh OBDD dlya vsyudu opredelennykh i chastichnykh funkciy // Izvestiya vysshikh uchebnykh zavedeniy. Matematika. - 2015. - № 11. - S. 32-43.

Annotation

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

Keywords

Упорядоченные ветвящиеся диаграммы решений, частичные функции, квантовые вычисления, недетерминированные OBDD, вероятностные OBDD, детерминированные OBDD, сложность.

The name of the journal

Известия ВУЗов, Математика

Please use this ID to quote from or refer to the card

https://repository.kpfu.ru/eng/?p_id=123588&p_lang=2

Full metadata record

Field DC	Value	Language
dc.contributor.author	Gaynutdinova Aida Faritovna	ru_RU
dc.date.accessioned	2015-01-01T00:00:00Z	ru_RU
dc.date.available	2015-01-01T00:00:00Z	ru_RU
dc.date.issued	2015	ru_RU
dc.identifier.citation	Гайнутдинова А.Ф. Сравнительная сложность квантовых и классических OBDD для всюду определенных и частичных функций // Известия высших учебных заведений. Математика. - 2015. - № 11. - С. 32-43.	ru_RU
dc.identifier.uri	https://repository.kpfu.ru/eng/?p_id=123588&p_lang=2	ru_RU
dc.description.abstract	Известия ВУЗов, Математика	ru_RU
dc.description.abstract	В работе рассматривается известная модель для вычисления булевых функций -- упорядоченные ветвящиеся диаграммы решений (OBDD -- Ordered Binary Decision Diagrams). Исследуется сравнительная сложность по ширине квантовых, классических детерминированных и вероятностных, а также недетерминированных (классических и квантовых) OBDD. Известно, что для всюду определенных функций квантовые OBDD, вычисляющие с ограниченной ошибкой, могут быть экспоненциально эффективнее детерминированных и вероятностных OBDD. В работе показывается, что такие квантовые OBDD также могут быть экспоненциально эффективнее недетерминированных OBDD, как классических, так и квантовых. Также в работе показывается, что при вычислении частичных функций разрыв в сложности может быть усилен. Для частичной функции, зависящей от параметра $k$, квантовая OBDD, вычисляющая без ошибки, имеет ширину 2. Детерминированная OBDD и стабильная вероятностная OBDD, вычисляющая с ограниченной ошибкой, для данной функции имеют ширину э	ru_RU
dc.language.iso	ru	ru_RU
dc.subject	Упорядоченные ветвящиеся диаграммы решений	ru_RU
dc.subject	частичные функции	ru_RU
dc.subject	квантовые вычисления	ru_RU
dc.subject	недетерминированные OBDD	ru_RU
dc.subject	вероятностные OBDD	ru_RU
dc.subject	детерминированные OBDD	ru_RU
dc.subject	сложность.	ru_RU
dc.title	Сравнительная сложность квантовых и классических OBDD для всюду определенных и частичных функций	ru_RU
dc.type	Articles in Russian journals and collections	ru_RU