• Login
    View Item 
    •   etd@IISc
    • Division of Physical and Mathematical Sciences
    • Centre for High Energy Physics (CHEP)
    • View Item
    •   etd@IISc
    • Division of Physical and Mathematical Sciences
    • Centre for High Energy Physics (CHEP)
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    Quantum walks and spatial search on regular graph

    View/Open
    Thesis full text (1.250Mb)
    Author
    Abhijith, J
    Metadata
    Show full item record
    Abstract
    Random walks and algorithms based upon them are used widely to explore large state spaces that arise while studying physical systems. In this thesis, we will discuss some quantum generalizations of such algorithms and study their complexity. In the first part of this talk, we will discuss quantum search in the presence of spatial constraints. One of the main results in this thesis is an efficient search algorithm that can find multiple marked elements under spatial constraints imposed by regular graphs. Next, we will focus attention on two-dimensional square lattices. Building on our earlier algorithmic framework, we will show that optimal quantum search is possible on the square lattice by only mildly violating the locality constraints imposed by the graph. This investigation leads to a general prescription for dealing with the graph powering operation in the quantum walk framework. After this, we will move on to discussing mixing times of quantum walks. We will show that a fully decohered quantum walk mixes asymptotically at the same rate as its classical counterpart only if its degree is a constant function of its size. We will also present some numerical evidence showing that faster mixing is possible using a weakly decohered quantum walk, if the decoherence probability is tuned in relation to the spectral gap of the graph. Finally, we will also discuss the implementation of quantum walks and spatial search on IBM's quantum computing platform.
    URI
    https://etd.iisc.ac.in/handle/2005/5602
    Collections
    • Centre for High Energy Physics (CHEP) [64]

    etd@IISc is a joint service of SERC & J R D Tata Memorial (JRDTML) Library || Powered by DSpace software || DuraSpace
    Contact Us | Send Feedback | Thesis Templates
    Theme by 
    Atmire NV
     

     

    Browse

    All of etd@IIScCommunities & CollectionsTitlesAuthorsAdvisorsSubjectsBy Thesis Submission DateThis CollectionTitlesAuthorsAdvisorsSubjectsBy Thesis Submission Date

    My Account

    LoginRegister

    etd@IISc is a joint service of SERC & J R D Tata Memorial (JRDTML) Library || Powered by DSpace software || DuraSpace
    Contact Us | Send Feedback | Thesis Templates
    Theme by 
    Atmire NV