КФУ. Карточка публикации. Complexity Bounds on Some Fundamental Computational Problems for Quantum Branching Programs

КАЗАНСКИЙ
ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ

RUS

- EN
- 中文
- ES

COMPLEXITY BOUNDS ON SOME FUNDAMENTAL COMPUTATIONAL PROBLEMS FOR QUANTUM BRANCHING PROGRAMS

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

Зарубежные монографии

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

2005

Язык

английский

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

Хасьянов Айрат Фаридович, автор

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

Airat Khasianov, Complexity Bounds on Some Fundamental Computational Problems for Quantum Branching Programs //University of Bonn PhD Thesis Electronic Publications,http://hss.ulb.uni-bonn.de/2005/0569/0569.htm (Bonn 2005)

Аннотация

We study quantum computational complexity of several problems connected to the Hidden Subgroup Problem. This problem drew substantial attention when a polynomial time quantum algorithm for it was found. The algorithm generalized the quantum algorithms for factoring integers and finding discrete logarithms. We consider the the problems in the context of quantum ordered read-once decision diagrams. Our presentation starts with some fundamental functions related to the Hidden Subgroup Problem. These functions include Equality, Periodicity and simplified "Simon". We show linear upper and lower bounds on the width of quantum OBDD representations of these functions. In the second part of the research we show upper and lower bounds for the Hidden Subgroup Test.

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

computer science, branching programs, quantum computing, complexity theory

URL

http://hss.ulb.uni-bonn.de/2005/0569/0569.htm

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

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

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

Поле DC	Значение	Язык
dc.contributor.author	Хасьянов Айрат Фаридович	ru_RU
dc.date.accessioned	2005-01-01T00:00:00Z	ru_RU
dc.date.available	2005-01-01T00:00:00Z	ru_RU
dc.date.issued	2005	ru_RU
dc.identifier.citation	Airat Khasianov, Complexity Bounds on Some Fundamental Computational Problems for Quantum Branching Programs //University of Bonn PhD Thesis Electronic Publications,http://hss.ulb.uni-bonn.de/2005/0569/0569.htm (Bonn 2005)	ru_RU
dc.identifier.uri	https://repository.kpfu.ru/?p_id=154656	ru_RU
dc.description.abstract	We study quantum computational complexity of several problems connected to the Hidden Subgroup Problem. This problem drew substantial attention when a polynomial time quantum algorithm for it was found. The algorithm generalized the quantum algorithms for factoring integers and finding discrete logarithms. We consider the the problems in the context of quantum ordered read-once decision diagrams. Our presentation starts with some fundamental functions related to the Hidden Subgroup Problem. These functions include Equality, Periodicity and simplified "Simon". We show linear upper and lower bounds on the width of quantum OBDD representations of these functions. In the second part of the research we show upper and lower bounds for the Hidden Subgroup Test.	ru_RU
dc.language.iso	ru	ru_RU
dc.subject	computer science	ru_RU
dc.subject	branching programs	ru_RU
dc.subject	quantum computing	ru_RU
dc.subject	complexity theory	ru_RU
dc.title	Complexity Bounds on Some Fundamental Computational Problems for Quantum Branching Programs	ru_RU
dc.type	Зарубежные монографии	ru_RU