Complexity Bounds on Some Fundamental Computational Problems for Quantum Branching Programs
Complexity Bounds on Some Fundamental Computational Problems for Quantum Branching Programs
View/Type of Scholarly Publication
DissertationDate of Exam
14.07.2005Date of Publication
2005Advisor
Karpinski, MarekCo-Referee
Ablayev, FaridMetadata
Show full item record
Citable Links 
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.
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.
Subjects
Komplexität, Quantenrechner, OBDD, Hidden-Subgroup-Problem, Untere Schränke, Obere Schränke, Branching programs, Quantum computing, Complexity, Lower bounds, Upper bounds
Classification (DDC)
004 InformatikKhasianov, Airat: Complexity Bounds on Some Fundamental Computational Problems for Quantum Branching Programs. - Bonn, 2005. - Dissertation, Rheinische Friedrich-Wilhelms-Universität Bonn.
Online-Ausgabe in bonndoc: https://nbn-resolving.org/urn:nbn:de:hbz:5N-05696
Online-Ausgabe in bonndoc: https://nbn-resolving.org/urn:nbn:de:hbz:5N-05696
@phdthesis{handle:20.500.11811/2297,
urn: https://nbn-resolving.org/urn:nbn:de:hbz:5N-05696,
author = {{Airat Khasianov}},
title = {Complexity Bounds on Some Fundamental Computational Problems for Quantum Branching Programs},
school = {Rheinische Friedrich-Wilhelms-Universität Bonn},
year = 2005,
note = {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.},
url = {https://hdl.handle.net/20.500.11811/2297}
}
urn: https://nbn-resolving.org/urn:nbn:de:hbz:5N-05696,
author = {{Airat Khasianov}},
title = {Complexity Bounds on Some Fundamental Computational Problems for Quantum Branching Programs},
school = {Rheinische Friedrich-Wilhelms-Universität Bonn},
year = 2005,
note = {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.},
url = {https://hdl.handle.net/20.500.11811/2297}
}
The following license files are associated with this item:
