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

  Browse A-Z

Log in

Googledetails Microsoftdetails

🔐 Log In

Information on

Subscribing to talksdetails Finding a talkdetails Adding a talkdetails Disseminating talksdetails Help and Documentationdetails

ℹī¸ Information

Quantum pattern matching fast on average

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.

This talk is included in these lists:

Note that ex-directory lists are not shown.

Other lists

MR 11, Centre for Mathematical Sciences & Zoom (contact organiser for the zoom link) in person & via zoom Webinar & FW11, Computer Laboratory, William Gates Building.

Other talks

Shape modes of CP^1 vortices TBC Title TBC Spectral theory for Dirac operators with singular potentials Claudia Ribeiro Almeida, Group Leader, Babraham Institute Online Causal Inference Seminar
 

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