University of Cambridge > Talks.cam > CQIF Seminar > Quantum pattern matching fast on average

Quantum pattern matching fast on average

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

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.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.

 

© 2006-2019 Talks.cam, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity