BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY: Quantum Fast-Forwarding: Markov Chains and Graph Property Testing
  - Simon Apers\, INRIA
DTSTART:20190221T141500Z
DTEND:20190221T151500Z
UID:TALK119593@talks.cam.ac.uk
CONTACT:Johannes Bausch
DESCRIPTION:I will introduce a new tool for quantum algorithms called quan
 tum fast-forwarding (QFF). The tool uses quantum walks as a means to quadr
 atically fast-forward a reversible Markov chain. In a number of quantum wa
 lk steps that scales as the square root of the classical runtime\, and inv
 ersely proportional to the 2-norm of the classical distribution\, it retri
 eves a quantum superposition that encodes the classical distribution. This
  shows that quantum walks can accelerate the transient dynamics of Markov 
 chains\, thereby complementing the line of results that proves the acceler
 ation of their limit behavior.\n\nThis tool leads to speedups on random wa
 lk algorithms in a very natural way. Specifically I will consider random w
 alk algorithms for testing the graph expansion and clusterability\, and sh
 ow that QFF allows to quadratically improve the dependency of the classica
 l property testers on the random walk runtime\; Moreover\, this new quantu
 m algorithm exponentially improves the space complexity of the classical t
 ester to logarithmic. As a subroutine of independent interest\, I use QFF 
 to determine whether a given pair of nodes lies in the same cluster or in 
 separate clusters. This solves a robust version of s-t connectivity\, rele
 vant in a learning context for classifying objects among a set of examples
 .
LOCATION:MR4\, Centre for Mathematical Sciences\, Wilberforce Road\, Cambr
 idge
END:VEVENT
END:VCALENDAR