Quantum Search on Molecular Graphs and Word-representable Line Graphs

The 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.