| Form of presentation | Articles in international journals and collections |
| Year of publication | 2017 |
| Язык | английский |
|
Khadiev Kamil Ravilevich, author
Khadieva Aliya Ikhsanovna, author
|
| Bibliographic description in the original language |
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. |
| Annotation |
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 |
| Keywords |
quantum computing, quantum OBDD, OBDD, Branching
programs, quantum vs classical, quantum models, hierarchy, computational
complexity, probabilistic OBDD
|
| The name of the journal |
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 |
| Please use this ID to quote from or refer to the card |
https://repository.kpfu.ru/eng/?p_id=159921&p_lang=2 |
Full metadata record  |
| Field DC |
Value |
Language |
| dc.contributor.author |
Khadiev Kamil Ravilevich |
ru_RU |
| dc.contributor.author |
Khadieva Aliya Ikhsanovna |
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/eng/?p_id=159921&p_lang=2 |
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 |
Articles in international journals and collections |
ru_RU |
|
RUS 
中文 
ES 
Sitemap
