Relations between quantum walks, open quantum walks, and lifted walks: the cycle graph

Simon Apers 1 Alain Sarlette 2
2 QUANTIC - QUANTum Information Circuits
ENS Paris - École normale supérieure - Paris, Inria Paris-Rocquencourt, UPMC - Université Pierre et Marie Curie - Paris 6, MINES ParisTech - École nationale supérieure des mines de Paris, CNRS - Centre National de la Recherche Scientifique : UMR8551
Abstract : The convergence time of a random walk on a graph towards its stationary distribution is an important indication of the efficiency of random algorithms based on it. Quantum random walks have been shown to allow quadratically accelerated convergence for large graphs, at least in some cases. The famous Grover search algorithm has been shown to actually fit this framework in an abstracted setting. Yet also with classical dynamics, simple mechanisms have been proposed which allow to quadratically accelerate the convergence with respect to a standard random walk. Some basic principles have been conjectured to cause this acceleration, basically transforming a diffusion-like behavior into a more transport-like behavior, but with remaining trail. We have worked out the equivalence of all these accelerating settings for the simplest example: the cycle graph. Quantum coherences turn out to play no major role and a classical feedback structure can be identified.
Type de document :
Communication dans un congrès
YQIS/IQFA workshop, Nov 2015, Paris Saclay, France
Liste complète des métadonnées

Littérature citée [5 références]  Voir  Masquer  Télécharger
Contributeur : Alain Sarlette <>
Soumis le : mardi 29 décembre 2015 - 13:41:57
Dernière modification le : mardi 24 avril 2018 - 17:20:15


  • HAL Id : hal-01248806, version 1



Simon Apers, Alain Sarlette. Relations between quantum walks, open quantum walks, and lifted walks: the cycle graph. YQIS/IQFA workshop, Nov 2015, Paris Saclay, France. 〈hal-01248806〉



Consultations de la notice


Téléchargements de fichiers