Solving Mathematical Problems in Quantum Regime
Loading...
Links to Files
Permanent Link
Collections
Author/Creator
Author/Creator ORCID
Date
2016-01-01
Type of Work
Department
Computer Science and Electrical Engineering
Program
Computer Science
Citation of Original Publication
Rights
This item may be protected under Title 17 of the U.S. Copyright Law. It is made available by UMBC for non-commercial research and education. For permission to publish or reproduce, please see http://aok.lib.umbc.edu/specoll/repro.php or contact Special Collections at speccoll(at)umbc.edu
Distribution Rights granted to UMBC by the author.
Distribution Rights granted to UMBC by the author.
Abstract
In this dissertations, I investigate a number of algorithmic approaches in the quantum computational regime to solve mathematical problems. My problems of interest are the graph isomorphism and the graph automorphism problems, and the complexity of memory recall of Hopfield network. I show that the hidden subgroup algorithm, quantum Fourier sampling, always fails, to construct the automorphism group for the class of the cycle graphs. I have discussed what we may infer for a few non-trivial classes of graphs from this result. This raises the question, I have discussed in this dissertations, whether the hidden subgroup algorithm is the best approach for these kinds of problems. I have given a correctness proof of the Hen-Young quantum adiabatic algorithm for graph isomorphism for cycle graphs. To the best of my knowledge this result is the first of its kind. I also report a proof-of-concept implementation of a quantum annealing algorithm for the graph isomorphism problem on a commercial quantum annealing device. This is also, to the best of my knowledge, the first of its kind. I have also discussed the worst-case for the algorithm. Finally, I have shown that quantum annealing helps us achieve exponential capacity for Hopfield networks.