КФУ. Карточка публикации. Exponential Separation between Quantum and Classical Ordered Binary Decision Diagrams, Reordering Method and Hierarchies

RUS

- EN
- 中文
- ES

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

Форма представления

Статьи в зарубежных журналах и сборниках

Год публикации

2017

Язык

английский

Авторы, сотрудники КФУ

Хадиев Камиль Равилевич, автор

Хадиева Алия Ихсановна, автор

Другие авторы

Кноп Александр , автор

Библиографическое описание на языке оригинала

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

Аннотация

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.

Ключевые слова

branching programs, hierarchy theorems, OBDD, quantum computing, quantum vs classical

Название журнала

Electronic Colloquium on Computational Complexity

URL

https://eccc.weizmann.ac.il/report/2017/176/

Пожалуйста, используйте этот идентификатор, чтобы цитировать или ссылаться на эту карточку

https://repository.kpfu.ru/?p_id=168984

Полная запись метаданных

Поле DC	Значение	Язык
dc.contributor.author	Хадиев Камиль Равилевич	ru_RU
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	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/?p_id=168984	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	Статьи в зарубежных журналах и сборниках	ru_RU