University of Maryland LibrariesDigital Repository at the University of Maryland
    • Войти
    Просмотр элемента 
    •   Главная
    • Theses and Dissertations from UMD
    • UMD Theses and Dissertations
    • Просмотр элемента
    •   Главная
    • Theses and Dissertations from UMD
    • UMD Theses and Dissertations
    • Просмотр элемента
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    Spectral graph theory with applications to quantum adiabatic optimization

    Thumbnail
    Открыть
    Baume_umd_0117E_17143.pdf (473.2Kb)
    No. of downloads: 208

    Дата
    2016
    Автор
    Baume, Michael Jarret
    Advisor
    Jordan, Stephen P
    Childs, Andrew
    DRUM DOI
    https://doi.org/10.13016/M2JB6B
    Metadata
    Показать полную информацию
    Аннотации
    In 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''.
    URI
    http://hdl.handle.net/1903/18388
    Collections
    • Physics Theses and Dissertations
    • UMD Theses and Dissertations

    DRUM is brought to you by the University of Maryland Libraries
    University of Maryland, College Park, MD 20742-7011 (301)314-1328.
    Please send us your comments.
    Web Accessibility
     

     

    Просмотр

    Весь DSpaceСообщества и коллекцииДата публикацииАвторыНазванияТематикаЭта коллекцияДата публикацииАвторыНазванияТематика

    Моя учетная запись

    ВойтиРегистрация
    Pages
    About DRUMAbout Download Statistics

    DRUM is brought to you by the University of Maryland Libraries
    University of Maryland, College Park, MD 20742-7011 (301)314-1328.
    Please send us your comments.
    Web Accessibility