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.
Complete list of metadatas

Cited literature [5 references]  Display  Hide  Download

https://hal.inria.fr/hal-01248806
Contributor : Alain Sarlette <>
Submitted on : Tuesday, December 29, 2015 - 1:41:57 PM
Last modification on : Tuesday, May 14, 2019 - 10:15:07 AM

Identifiers

  • HAL Id : hal-01248806, version 1

Citation

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⟩

Share

Metrics

Record views

340

Files downloads

53