Ph.D. Dissertation Defense
Computer Science and Electrical Engineering

Solving Mathematical Problems in Quantum Regime

Omar Shehab

2:00pm Thursday, 7 July 2016, ITE 325b

In this dissertation, I investigate a number of algorithmic approaches in quantum computational regime to solve mathematical problems. My problems of interest are the graph isomorphism and 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, which I have discussed in this dissertation, 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.

Committee: Drs. Samuel J Lomonaco Jr. (Chair), Milton Halem, Yanhua Shih, William Gasarch and John Dorband