Form of presentation | Articles in international journals and collections |
Year of publication | 2017 |
Язык | английский |
|
Khadiev Kamil Ravilevich, author
Khadieva Aliya Ikhsanovna, author
|
|
Knop Aleksandr , author
|
Bibliographic description in the original language |
Kamil Khadiev, Aliya Khadiev, Alexander Knop, Exponential Separation between Quantum and Classical Ordered Binary Decision Diagrams, Reordering Method and Hierarchies, In Electronic Colloquium on Computational Complexity, TR17-176, PP. 1-15 , 2017 |
Annotation |
n this paper, we study quantum OBDD model, it is a restricted version of read-once quantum branching programs, with respect to «width« complexity. It is known that the maximal gap between deterministic and quantum complexities is exponential. But there are few examples of functions with such a gap. We present a method (called «reordering«), which allows us to transform a Boolean function f into a Boolean function f, such that if for f we have some gap
between quantum and deterministic OBDD complexities for the natural order over the variables of f, then for any order we have almost the same gap for the function f. Using this transformation, we construct a total function REQ such that the deterministic OBDD complexity of it is at least 2(nlogn) , and the quantum OBDD complexity of it is at most O(n2). It is the biggest known gap for explicit functions not representable by OBDDs of a linear width. We also prove the quantum OBDD width hierarchy for complexity classes of Boolean functions. |
Keywords |
branching programs, hierarchy theorems, OBDD, quantum computing, quantum vs classical |
The name of the journal |
Electronic Colloquium on Computational Complexity
|
URL |
https://eccc.weizmann.ac.il/report/2017/176/ |
Please use this ID to quote from or refer to the card |
https://repository.kpfu.ru/eng/?p_id=168984&p_lang=2 |
Full metadata record ![](https://shelly.kpfu.ru/pdf/picture/arrow_black_right.gif) |
Field DC |
Value |
Language |
dc.contributor.author |
Khadiev Kamil Ravilevich |
ru_RU |
dc.contributor.author |
Khadieva Aliya Ikhsanovna |
ru_RU |
dc.contributor.author |
Knop Aleksandr |
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 |
Kamil Khadiev, Aliya Khadiev, Alexander Knop, Exponential Separation between Quantum and Classical Ordered Binary Decision Diagrams, Reordering Method and Hierarchies, In Electronic Colloquium on Computational Complexity, TR17-176, PP. 1-15 , 2017 |
ru_RU |
dc.identifier.uri |
https://repository.kpfu.ru/eng/?p_id=168984&p_lang=2 |
ru_RU |
dc.description.abstract |
Electronic Colloquium on Computational Complexity |
ru_RU |
dc.description.abstract |
n this paper, we study quantum OBDD model, it is a restricted version of read-once quantum branching programs, with respect to «width« complexity. It is known that the maximal gap between deterministic and quantum complexities is exponential. But there are few examples of functions with such a gap. We present a method (called «reordering«), which allows us to transform a Boolean function f into a Boolean function f, such that if for f we have some gap
between quantum and deterministic OBDD complexities for the natural order over the variables of f, then for any order we have almost the same gap for the function f. Using this transformation, we construct a total function REQ such that the deterministic OBDD complexity of it is at least 2(nlogn) , and the quantum OBDD complexity of it is at most O(n2). It is the biggest known gap for explicit functions not representable by OBDDs of a linear width. We also prove the quantum OBDD width hierarchy for complexity classes of Boolean functions. |
ru_RU |
dc.language.iso |
ru |
ru_RU |
dc.subject |
branching programs |
ru_RU |
dc.subject |
hierarchy theorems |
ru_RU |
dc.subject |
OBDD |
ru_RU |
dc.subject |
quantum computing |
ru_RU |
dc.subject |
quantum vs classical |
ru_RU |
dc.title |
Exponential Separation between Quantum and Classical Ordered Binary Decision Diagrams, Reordering Method and Hierarchies |
ru_RU |
dc.type |
Articles in international journals and collections |
ru_RU |
|