| Форма представления | Статьи в зарубежных журналах и сборниках |
| Год публикации | 2017 |
| Язык | английский |
|
Хадиев Камиль Равилевич, автор
Хадиева Алия Ихсановна, автор
|
| Библиографическое описание на языке оригинала |
Khadiev K, Khadieva A., Reordering method and hierarchies for quantum and classical ordered binary decision diagrams//Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). - 2017. - Vol.10304 LNCS, Is.. - P.162-175. |
| Аннотация |
We consider Quantum OBDD model. It is restricted version
of read-once Quantum Branching Programs, with respect to “width”
complexity. It is known that maximal complexity gap between deterministic
and quantum model is exponential. But there are few examples of
such functions. We present method (called “reordering”), which allows
to build Boolean function
g from Boolean Function
f, such that if for
f we have gap between quantum and deterministic OBDD complexity
for natural order of variables, then we have almost the same gap for
function
g, but for any order. Using it we construct the total function
REQ which deterministic OBDD complexity is 2
Ω
(n/ log
n
)
and present
quantum OBDD of width
O
(
n
2
). It is bigger gap for explicit function
that was known before for OBDD of width more than linear. Using this
result we prove the width hierarchy for complexity classes of Boolean
functions for quantum OBDDs.
Additionally, we prove the width hierarchy for complexity classes of
Boolean functio |
| Ключевые слова |
quantum computing, quantum OBDD, OBDD, Branching
programs, quantum vs classical, quantum models, hierarchy, computational
complexity, probabilistic OBDD
|
| Название журнала |
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
|
| URL |
https://www.scopus.com/inward/record.uri?eid=2-s2.0-85019185740&doi=10.1007%2f978-3-319-58747-9_16&partnerID=40&md5=86fc66d329acc6e65a20047c2d6bdf41 |
| Пожалуйста, используйте этот идентификатор, чтобы цитировать или ссылаться на эту карточку |
https://repository.kpfu.ru/?p_id=159921 |
Полная запись метаданных  |
| Поле DC |
Значение |
Язык |
| dc.contributor.author |
Хадиев Камиль Равилевич |
ru_RU |
| dc.contributor.author |
Хадиева Алия Ихсановна |
ru_RU |
| dc.date.accessioned |
2017-01-01T00:00:00Z |
ru_RU |
| dc.date.available |
2017-01-01T00:00:00Z |
ru_RU |
| dc.date.issued |
2017 |
ru_RU |
| dc.identifier.citation |
Khadiev K, Khadieva A., Reordering method and hierarchies for quantum and classical ordered binary decision diagrams//Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). - 2017. - Vol.10304 LNCS, Is.. - P.162-175. |
ru_RU |
| dc.identifier.uri |
https://repository.kpfu.ru/?p_id=159921 |
ru_RU |
| dc.description.abstract |
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
ru_RU |
| dc.description.abstract |
We consider Quantum OBDD model. It is restricted version
of read-once Quantum Branching Programs, with respect to “width”
complexity. It is known that maximal complexity gap between deterministic
and quantum model is exponential. But there are few examples of
such functions. We present method (called “reordering”), which allows
to build Boolean function
g from Boolean Function
f, such that if for
f we have gap between quantum and deterministic OBDD complexity
for natural order of variables, then we have almost the same gap for
function
g, but for any order. Using it we construct the total function
REQ which deterministic OBDD complexity is 2
Ω
(n/ log
n
)
and present
quantum OBDD of width
O
(
n
2
). It is bigger gap for explicit function
that was known before for OBDD of width more than linear. Using this
result we prove the width hierarchy for complexity classes of Boolean
functions for quantum OBDDs.
Additionally, we prove the width hierarchy for complexity classes of
Boolean functio |
ru_RU |
| dc.language.iso |
ru |
ru_RU |
| dc.subject |
quantum computing |
ru_RU |
| dc.subject |
quantum OBDD |
ru_RU |
| dc.subject |
OBDD |
ru_RU |
| dc.subject |
Branching
programs |
ru_RU |
| dc.subject |
quantum vs classical |
ru_RU |
| dc.subject |
quantum models |
ru_RU |
| dc.subject |
hierarchy |
ru_RU |
| dc.subject |
computational
complexity |
ru_RU |
| dc.subject |
probabilistic OBDD
|
ru_RU |
| dc.title |
Reordering method and hierarchies for quantum and classical ordered binary decision diagrams |
ru_RU |
| dc.type |
Статьи в зарубежных журналах и сборниках |
ru_RU |
|
EN 
中文 
ES 
Карта сайта
