Skip to Main content Skip to Navigation
New interface
Conference papers

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-PSL - École normale supérieure - Paris, Inria Paris-Rocquencourt, UPMC - Université Pierre et Marie Curie - Paris 6, Mines Paris - PSL (É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.
Complete list of metadata

Cited literature [5 references]  Display  Hide  Download
Contributor : Alain Sarlette Connect in order to contact the contributor
Submitted on : Tuesday, December 29, 2015 - 1:41:57 PM
Last modification on : Wednesday, October 26, 2022 - 2:08:50 PM


  • 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⟩



Record views


Files downloads