| Форма представления | Статьи в российских журналах и сборниках |
| Год публикации | 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 |
Полная запись метаданных  |
| Поле DC |
Значение |
Язык |
| dc.contributor.author |
Гайнутдинова Аида Фаритовна |
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/?p_id=123588 |
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 |
Статьи в российских журналах и сборниках |
ru_RU |
|
EN 
中文 
ES 
Карта сайта
