BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Quantum pattern matching fast on average - Ashley Montanaro (Unive
 rsity of Bristol)
DTSTART:20141113T141500Z
DTEND:20141113T151500Z
UID:TALK54915@talks.cam.ac.uk
CONTACT:William Matthews
DESCRIPTION:The d-dimensional pattern matching problem is to find an occur
 rence of a pattern of length m*...*m within a text of length n*...*n. This
  task models various problems in text and image processing\, among other a
 pplication areas. In this talk I will describe a quantum algorithm which a
 chieves a super-polynomial speedup over any classical algorithm for the pa
 ttern matching problem\, on average-case inputs. That is\, for most input 
 patterns and texts\, the algorithm is super-polynomially faster than the b
 est possible classical algorithm. The algorithm is based on a quantum subr
 outine which is a variant of algorithms proposed by Kuperberg for the dihe
 dral hidden subgroup problem.
LOCATION:MR4\,  Centre for Mathematical Sciences\, Wilberforce Road\, Camb
 ridge
END:VEVENT
END:VCALENDAR