Quantum Search on Molecular Graphs and Word-representable Line Graphs

Simple item page
dc.contributor.advisorAkbar, Mohammad
dc.contributor.advisorKesden, Michael
dc.contributor.committeeMemberDragovic, Vladimir
dc.contributor.committeeMemberRamakrishna, Viswanath
dc.contributor.committeeMemberDabkowski, Mieczyslaw
dc.creatorAkrobotu, Prosper Delanyo
dc.date.accessioned2023-02-21T19:14:11Z
dc.date.available2023-02-21T19:14:11Z
dc.date.created2021-12
dc.date.issued2021-12-01T06:00:00.000Z
dc.date.submittedDecember 2021
dc.date.updated2023-02-21T19:14:12Z
dc.description.abstractThe work presented in this thesis broadly falls under two quantum search procedures: quantum search using a continuous-time quantum walk and quantum search using adiabatic quantum evolution. The searches are conducted on three different graphs: the molecular graph of graphene, the molecular graph of alkane, and on the line graphs of (non-)word-representable graphs. For the latter, a classical solver was also used to resolve a long-standing question. Quantum search using a continuous-time quantum walk was implemented for a marked node on the molecular graph of graphene, the hexagonal lattice. It was established that including second-nearest-neighbor coupling does not have a significant impact on the search time but does seem to improve the probability of success. This builds on the work of Foulger, Gnutzmann, and Tanner on quantum search on graphene who considered only the nearest-neighbor interactions. Quantum search using adiabatic quantum computation was implemented for (a) searching for isomers of alkanes, (b) searching for the most influential node in a network, and (c) for the decision problem of word-representable line graphs. Quadratic unconstrained binary optimization (QUBO) formulations were proposed for these problems to be embedded and solved on both quantum annealing and gate-based quantum computers such as D-Wave quantum annealers and IBM quantum computers. The dynamics of the search is described by a quantum system evolving under a slowly varying Hamiltonian. Based on the adiabatic theorem, the search evolves from the ground state of an initial Hamiltonian H0 to the ground state of a problem Hamiltonian HP . The primary objective in each case was to construct an efficient HP for the search problem. Using the QUBO results from the D-Wave 2000Q and IBM Q QASM simulators, we were able to verify and search for all isomers of alkanes with at most 9 carbon atoms and for the most influential node of undirected networks using eigenvector centrality. Finally, our formulation of the decision problem of word-representable graphs showed that the line graphs of non-word-representable graphs are not always non-word-representable. This answers a 10- year-old open problem.
dc.format.mimetypeapplication/pdf
dc.identifier.uri
dc.identifier.urihttps://hdl.handle.net/10735.1/9583
dc.language.isoen
dc.subjectMathematics
dc.subjectPhysics, Condensed Matter
dc.subjectComputer Science
dc.titleQuantum Search on Molecular Graphs and Word-representable Line Graphs
dc.typeThesis
dc.type.materialtext
thesis.degree.collegeSchool of Natural Sciences and Mathematics
thesis.degree.departmentMathematics
thesis.degree.grantorThe University of Texas at Dallas
thesis.degree.namePHD

Files

Collections

UTD Theses and Dissertations