Quantum walks : speed limits on mixing and fast-forwarding classical walks
Simon Apers · Ghent University Academic Bibliography (Ghent University) · 2019
The theme that underlies this thesis is the mutualist relation between classical walks and quantum walks on graphs, the latter being a promising algorithmic component of future quantum computers.We study both sides of this coin.On the one side we prove how classical walks can simulate quantum walks.This allows the use of folklore bounds on the behavior of classical walks to study speed limits on quantum walks, a question which had long evaded progress.On the other side, we prove how quantum walks can be used to speed up the behavior of a large class of classical walks.This leads to a new quantum algorithm which we call quantum walk fast-forwarding.We show that this algorithm allows to naturally speed up classical walk algorithms for search and property testing on graphs.The work is theoretical and mathematical, and supposed to be relevant for quantum computers that should some day exist.I feel proud of this work, and am indebted to many people.Foremost I must thank my supervisor Alain Sarlette, you have been the best supervisor I could wish for, if only for learning me that no-go proofs are traffic diversions rather than dead ends.