Quantum pattern matching fast on average

Add to your list(s) Download to your calendar using vCal

• Ashley Montanaro (University of Bristol)
• Thursday 13 November 2014, 14:15-15:15
• MR4, Centre for Mathematical Sciences, Wilberforce Road, Cambridge.

If you have a question about this talk, please contact William Matthews.

The d-dimensional pattern matching problem is to find an occurrence 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 application areas. In this talk I will describe a quantum algorithm which achieves a super-polynomial speedup over any classical algorithm for the pattern matching problem, on average-case inputs. That is, for most input patterns and texts, the algorithm is super-polynomially faster than the best possible classical algorithm. The algorithm is based on a quantum subroutine which is a variant of algorithms proposed by Kuperberg for the dihedral hidden subgroup problem.

This talk is part of the CQIF Seminar series.

This talk is included in these lists:

• All CMS events
• CMS Events
• CQIF Seminar
• DAMTP info aggregator
• Hanchen DaDaDash
• Interested Talks
• MR4, Centre for Mathematical Sciences, Wilberforce Road, Cambridge
• bld31

Note that ex-directory lists are not shown.