KFU. Card publication. Complexity Bounds on Some Fundamental Computational Problems for Quantum Branching Programs

KAZAN
FEDERAL UNIVERSITY

- RUS
- 中文
- ES

COMPLEXITY BOUNDS ON SOME FUNDAMENTAL COMPUTATIONAL PROBLEMS FOR QUANTUM BRANCHING PROGRAMS

Form of presentation

International monographs

Year of publication

2005

��

��

Authors, employees of KFU

Khasyanov Ayrat Faridovich, author

Bibliographic description in the original language

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)

Annotation

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.

Keywords

computer science, branching programs, quantum computing, complexity theory

URL

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

Please use this ID to quote from or refer to the card

https://repository.kpfu.ru/eng/?p_id=154656&p_lang=2

Full metadata record

Field DC	Value	Language
dc.contributor.author	Khasyanov Ayrat Faridovich	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/eng/?p_id=154656&p_lang=2	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	International monographs	ru_RU