Complexity Bounds on Some Fundamental Computational Problems for Quantum Branching Programs
Complexity Bounds on Some Fundamental Computational Problems for Quantum Branching Programs
dc.contributor.advisor | Karpinski, Marek | |
dc.contributor.author | Khasianov, Airat | |
dc.date.accessioned | 2020-04-08T00:20:39Z | |
dc.date.available | 2020-04-08T00:20:39Z | |
dc.date.issued | 2005 | |
dc.identifier.uri | https://hdl.handle.net/20.500.11811/2297 | |
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. | |
dc.language.iso | eng | |
dc.rights | In Copyright | |
dc.rights.uri | http://rightsstatements.org/vocab/InC/1.0/ | |
dc.subject | Komplexität | |
dc.subject | Quantenrechner | |
dc.subject | OBDD | |
dc.subject | Hidden-Subgroup-Problem | |
dc.subject | Untere Schränke | |
dc.subject | Obere Schränke | |
dc.subject | Branching programs | |
dc.subject | Quantum computing | |
dc.subject | Complexity | |
dc.subject | Lower bounds | |
dc.subject | Upper bounds | |
dc.subject.ddc | 004 Informatik | |
dc.title | Complexity Bounds on Some Fundamental Computational Problems for Quantum Branching Programs | |
dc.type | Dissertation oder Habilitation | |
dc.publisher.name | Universitäts- und Landesbibliothek Bonn | |
dc.publisher.location | Bonn | |
dc.rights.accessRights | openAccess | |
dc.identifier.urn | https://nbn-resolving.org/urn:nbn:de:hbz:5N-05696 | |
ulbbn.pubtype | Erstveröffentlichung | |
ulbbnediss.affiliation.name | Rheinische Friedrich-Wilhelms-Universität Bonn | |
ulbbnediss.affiliation.location | Bonn | |
ulbbnediss.thesis.level | Dissertation | |
ulbbnediss.dissID | 569 | |
ulbbnediss.date.accepted | 14.07.2005 | |
ulbbnediss.institute | Mathematisch-Naturwissenschaftliche Fakultät : Fachgruppe Informatik / Institut für Informatik | |
ulbbnediss.fakultaet | Mathematisch-Naturwissenschaftliche Fakultät | |
dc.contributor.coReferee | Ablayev, Farid |
Files in this item
This item appears in the following Collection(s)
-
E-Dissertationen (4070)