Seminario del 2023

2023
24 maggio
Gianna M. Del Corso, Dipartimento di Informatica, Università di Pisa
Seminario di analisi numerica
The hitting time of a random walk on a graph is the expected number of steps required to reach a marked node starting from a given node or a given distribution. Hitting time finds a crucial application in search problems, where it tells us how many steps are needed to detect a marked node. In a quantum framework, random walks are replaced by quantum walks, which exhibit peculiar properties. In particular, quantum walks typically tend to diffuse faster on a graph than classical random walks. One way in which this remark can be made more precise is through the definition of a quantum notion of hitting time. We focus in this talk on quantum hitting time for discrete-time quantum walks. Usually, quantum hitting time is defined in terms of the stationary distribution associated with the given graph, while the classical hitting time can be defined in terms of a generic distribution. We generalize the notion of quantum hitting time in terms of a generic distribution emphasizing analogies and differences with the case where the stationary distribution is used. We provide conditions for the quadratic speedup of quantum hitting time over the classical counterpart and we report the results of numerical experiments on several examples of graphs both directed and undirected and for several different distributions. (joint work with Paola Boito).

indietro