Title

Hitting time of quantum walks with perturbation

Authors

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