KFU. Card publication. Exponential Separation between Quantum and Classical Ordered Binary Decision Diagrams, Reordering Method and Hierarchies

- RUS
- 中文
- ES

EXPONENTIAL SEPARATION BETWEEN QUANTUM AND CLASSICAL ORDERED BINARY DECISION DIAGRAMS, REORDERING METHOD AND HIERARCHIES

Form of presentation

Articles in international journals and collections

Year of publication

2017

��

��

Authors, employees of KFU

Khadiev Kamil Ravilevich, author

Khadieva Aliya Ikhsanovna, author

Other authors

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

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