PhD Dissertation Proposal
A quantum approach to the graph isomorphism
and knot classification problems
Omar Shehab
11:30am Monday, 08 December 2014, ITE 346
Simulating physics on a quantum computer can be reduced to solving mathematical problem using quantum mechanics. In this PhD dissertation proposal, I present two important mathematical problems to be investigated using quantum mechanical techniques. In the case of the first problem, the Graph Isomorphism problem, I, with another co-researcher, Kenneth M Zick, are able to present a quantum annealing algorithm with promising result. I am proposing to extend this idea so that we could study the Hamiltonian complexity of graph isomorphism. I propose to transform our previous work, the compact objective function, into a k-local Hamiltonian problem and investigate quantum adiabatic algorithms to solve it. In the case of the second problem, classification of knots, I present a mathematical framework with two restricted problems solved using quantum annealing. The restricted problems are defined for unknots embedded in two dimensional integer lattice. I propose to generalize them to higher dimension and complexity. I present how I envision to continue the rest of the study while writing the dissertation.
Committee: Drs. Samuel J. Lomonaco Jr. (chair), Alan T. Sherman, Yanhua Shih, William Gasarch