Form of presentation | Articles in international journals and collections |
Year of publication | 2014 |
Язык | русский |
|
Ablaev Farid Mansurovich, author
Gaynutdinova Aida Faritovna, author
Khadiev Kamil Ravilevich, author
|
Bibliographic description in the original language |
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 |
Annotation |
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 |
Keywords |
quantum computation, OBDD, nondeterminism |
The name of the journal |
Lecture Notes in Computer Science
|
URL |
http://link.springer.com/chapter/10.1007/978-3-319-09704-6_6 |
Please use this ID to quote from or refer to the card |
https://repository.kpfu.ru/eng/?p_id=84826&p_lang=2 |
Full metadata record ![](https://shelly.kpfu.ru/pdf/picture/arrow_black_right.gif) |
Field DC |
Value |
Language |
dc.contributor.author |
Ablaev Farid Mansurovich |
ru_RU |
dc.contributor.author |
Gaynutdinova Aida Faritovna |
ru_RU |
dc.contributor.author |
Khadiev Kamil Ravilevich |
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/eng/?p_id=84826&p_lang=2 |
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 |
Articles in international journals and collections |
ru_RU |
|