MURAL - Maynooth University Research Archive Library



    Quantum searches on highly symmetric graphs


    Reitzner, Daniel and Hillery, Mark and Feldman, Edgar and Buzek, Vladimir (2009) Quantum searches on highly symmetric graphs. Physical Review A, 79 (1). 012323.1-012323.10. ISSN 1050-2947

    [img] Download (463kB)


    Share your research

    Twitter Facebook LinkedIn GooglePlus Email more...



    Add this article to your Mendeley library


    Abstract

    We study scattering quantum walks on highly symmetric graphs and use the walks to solve search problems on these graphs. The particle making the walk resides on the edges of the graph, and at each time step scatters at the vertices. All of the vertices have the same scattering properties except for a subset of special vertices. The object of the search is to find a special vertex. A quantum circuit implementation of these walks is presented in which the set of special vertices is specified by a quantum oracle. We consider the complete graph, a complete bipartite graph, and an M-partite graph. In all cases, the dimension of the Hilbert space in which the time evolution of the walk takes place is small (between three and six), so the walks can be completely analyzed analytically. Such dimensional reduction is due to the fact that these graphs have large automorphism groups. We find the usual quadratic quantum speedups in all cases considered.

    Item Type: Article
    Keywords: Quantum searches; highly symmetric graphs;
    Academic Unit: Faculty of Science and Engineering > Experimental Physics
    Faculty of Science and Engineering > Mathematics and Statistics
    Item ID: 2178
    Depositing User: Prof. Vladimir Buzek
    Date Deposited: 12 Oct 2010 13:47
    Journal or Publication Title: Physical Review A
    Publisher: American Physical Society
    Refereed: Yes
    URI:

    Repository Staff Only(login required)

    View Item Item control page

    Downloads

    Downloads per month over past year