Hitting time of quantum walks with perturbation

    Authors

    C. F. Chiang;G. Gomez

    Comments

    Authors: contact us about adding a copy of your work at STARS@ucf.edu

    Abbreviated Journal Title

    Quantum Inf. Process.

    Keywords

    Markov chain; Quantum walk; Hitting time; Matrix perturbation; Random; walk; Delayed perturbed quantum hitting time; Delayed perturbed hitting; time; MARKOV-CHAIN; ALGORITHMS; PERMANENT; MATRIX; BOUNDS; Physics, Multidisciplinary; Physics, Mathematical

    Abstract

    The hitting time is the required minimum time for a Markov chain-based walk (classical or quantum) to reach a target state in the state space. We investigate the effect of the perturbation on the hitting time of a quantum walk. We obtain an upper bound for the perturbed quantum walk hitting time by applying Szegedy's work and the perturbation bounds with Weyl's perturbation theorem on classical matrix. Based on the definition of quantum hitting time given in MNRS algorithm, we further compute the delayed perturbed hitting time and delayed perturbed quantum hitting time (DPQHT). We show that the upper bound for DPQHT is bounded from above by the difference between the square root of the upper bound for a perturbed random walk and the square root of the lower bound for a random walk.

    Journal Title

    Quantum Information Processing

    Volume

    12

    Issue/Number

    1

    Publication Date

    1-1-2013

    Document Type

    Article

    Language

    English

    First Page

    217

    Last Page

    228

    WOS Identifier

    WOS:000312665200015

    ISSN

    1570-0755

    Share

    COinS