Spectral graph theory with applications to quantum adiabatic optimization

Simple item page
dc.contributor.advisorJordan, Stephen Pen_US
dc.contributor.advisorChilds, Andrewen_US
dc.contributor.authorBaume, Michael Jarreten_US
dc.contributor.departmentPhysicsen_US
dc.contributor.publisherDigital Repository at the University of Marylanden_US
dc.contributor.publisherUniversity of Maryland (College Park, Md.)en_US
dc.date.accessioned2016-06-22T06:15:10Z
dc.date.available2016-06-22T06:15:10Z
dc.date.issued2016en_US
dc.description.abstractIn this dissertation I draw a connection between quantum adiabatic optimization, spectral graph theory, heat-diffusion, and sub-stochastic processes through the operators that govern these processes and their associated spectra. In particular, we study Hamiltonians which have recently become known as ``stoquastic'' or, equivalently, the generators of sub-stochastic processes. The operators corresponding to these Hamiltonians are of interest in all of the settings mentioned above. I predominantly explore the connection between the spectral gap of an operator, or the difference between the two lowest energies of that operator, and certain equilibrium behavior. In the context of adiabatic optimization, this corresponds to the likelihood of solving the optimization problem of interest. I will provide an instance of an optimization problem that is easy to solve classically, but leaves open the possibility to being difficult adiabatically. Aside from this concrete example, the work in this dissertation is predominantly mathematical and we focus on bounding the spectral gap. Our primary tool for doing this is spectral graph theory, which provides the most natural approach to this task by simply considering Dirichlet eigenvalues of subgraphs of host graphs. I will derive tight bounds for the gap of one-dimensional, hypercube, and general convex subgraphs. The techniques used will also adapt methods recently used by Andrews and Clutterbuck to prove the long-standing ``Fundamental Gap Conjecture''.en_US
dc.identifierhttps://doi.org/10.13016/M2JB6B
dc.identifier.urihttp://hdl.handle.net/1903/18388
dc.language.isoenen_US
dc.subject.pqcontrolledPhysicsen_US
dc.subject.pqcontrolledMathematicsen_US
dc.subject.pqcontrolledComputer scienceen_US
dc.subject.pquncontrolledadiabatic optimizationen_US
dc.subject.pquncontrolledeigenvaluesen_US
dc.subject.pquncontrolledhamiltonianen_US
dc.subject.pquncontrolledspectral graph theoryen_US
dc.titleSpectral graph theory with applications to quantum adiabatic optimizationen_US
dc.typeDissertationen_US

Files

Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
Baume_umd_0117E_17143.pdf
Size:
473.25 KB
Format:
Adobe Portable Document Format
Download

Collections

UMD Theses and Dissertations
Physics Theses and Dissertations