Équipe de Recherche en Physique de l'Information Quantique


Year = {2012},
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.},
author = {C.-F. Chiang and G. Gomez},
title = {Hitting time of quantum walks with perturbation},
journal = {Quantum Information Processing},
volume = {Feb. 9},
pages = {1},
local-url = {CG12a.pdf}}