Classical random walks vs Quantum walks : an empirical comparison of the mixing time on finite abelian groups

Details

Supervisors

Delvenne, Jean-Charles

Faculty

Faculté des sciences

Degree label

Master [120] en sciences mathématiques, à finalité didactique

Abstract

The need for random walks with fast mixing to the stationary distribution in randomised algorithms leads us to considerating ways of improving those random walks. In this master thesis, we explore two approaches to reduce the mixing time : lifted random walks and discrete-time classical walks. The objective is to compare the classical and quantum random walk models by simulating the walks on Cayley graphs of finite abelian groups and by analysing the results.