КФУ. Карточка публикации. Very Narrow Quantum OBDDs and Width Hierarchies for Classical OBDDs

КАЗАНСКИЙ
ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ

RUS

- EN
- 中文
- ES

VERY NARROW QUANTUM OBDDS AND WIDTH HIERARCHIES FOR CLASSICAL OBDDS

Форма представления

Статьи в зарубежных журналах и сборниках

Год публикации

2014

Язык

русский

Авторы, сотрудники КФУ

Аблаев Фарид Мансурович, автор

Гайнутдинова Аида Фаритовна, автор

Хадиев Камиль Равилевич, автор

Библиографическое описание на языке оригинала

Farid Ablayev, Aida Gainutdinova, Kamil Khadiev, Abuzer Yakaryılmaz, «Very Narrow Quantum OBDDs and Width Hierarchies for Classical OBDDs«, LNCS vol. 8614 pp. 53-64, 2014

Аннотация

In the paper we investigate a model for computing of Boolean functions ? Ordered Binary Decision Diagrams (OBDDs), which is a restricted version of Branching Programs. We present several results on the comparative complexity for several variants of OBDD models. We present some results on the comparative complexity of classical and quantum OBDDs. We consider a partial function depending on a parameter k such that for any k > 0 this function is computed by an exact quantum OBDD of width 2, but any classical OBDD (deterministic or stable bounded-error probabilistic) needs width 2 k + 1. We consider quantum and classical nondeterminism. We show that quantum nondeterminism can be more efficient than classical nondeterminism. In particular, an explicit function is presented which is computed by a quantum nondeterministic OBDD with constant width, but any classical nondeterministic OBDD for this function needs non-constant width. We also present new hierarchies on widths of determ. & nonde

Ключевые слова

quantum computation, OBDD, nondeterminism

Название журнала

Lecture Notes in Computer Science

URL

http://link.springer.com/chapter/10.1007/978-3-319-09704-6_6

Пожалуйста, используйте этот идентификатор, чтобы цитировать или ссылаться на эту карточку

https://repository.kpfu.ru/?p_id=84826

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

Поле DC	Значение	Язык
dc.contributor.author	Аблаев Фарид Мансурович	ru_RU
dc.contributor.author	Гайнутдинова Аида Фаритовна	ru_RU
dc.contributor.author	Хадиев Камиль Равилевич	ru_RU
dc.date.accessioned	2014-01-01T00:00:00Z	ru_RU
dc.date.available	2014-01-01T00:00:00Z	ru_RU
dc.date.issued	2014	ru_RU
dc.identifier.citation	Farid Ablayev, Aida Gainutdinova, Kamil Khadiev, Abuzer Yakaryılmaz, «Very Narrow Quantum OBDDs and Width Hierarchies for Classical OBDDs«, LNCS vol. 8614 pp. 53-64, 2014	ru_RU
dc.identifier.uri	https://repository.kpfu.ru/?p_id=84826	ru_RU
dc.description.abstract	Lecture Notes in Computer Science	ru_RU
dc.description.abstract	In the paper we investigate a model for computing of Boolean functions ? Ordered Binary Decision Diagrams (OBDDs), which is a restricted version of Branching Programs. We present several results on the comparative complexity for several variants of OBDD models. We present some results on the comparative complexity of classical and quantum OBDDs. We consider a partial function depending on a parameter k such that for any k > 0 this function is computed by an exact quantum OBDD of width 2, but any classical OBDD (deterministic or stable bounded-error probabilistic) needs width 2 k + 1. We consider quantum and classical nondeterminism. We show that quantum nondeterminism can be more efficient than classical nondeterminism. In particular, an explicit function is presented which is computed by a quantum nondeterministic OBDD with constant width, but any classical nondeterministic OBDD for this function needs non-constant width. We also present new hierarchies on widths of determ. & nonde	ru_RU
dc.language.iso	ru	ru_RU
dc.subject	quantum computation	ru_RU
dc.subject	OBDD	ru_RU
dc.subject	nondeterminism	ru_RU
dc.title	Very Narrow Quantum OBDDs and Width Hierarchies for Classical OBDDs	ru_RU
dc.type	Статьи в зарубежных журналах и сборниках	ru_RU