Grover's algorithm, databases and quantum machine learning

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

• Aram Harrow (MIT)
• Friday 17 May 2019, 12:00-13:00
• MR14, Centre for Mathematical Sciences, Wilberforce Road, Cambridge.

If you have a question about this talk, please contact Johannes Bausch.

A cornerstone of quantum computing is Grover’s 1996 paper: “A Fast Quantum Mechanical Algorithm for Database Search”. Since then, Grover’s algorithm and its descendants have been applied to a wide range of tasks but none have involved databases. In this talk, I will describe two ways in which Grover search can be used for tasks involving large classical databases. First, I will describe an example of a task (from high-energy physics) in which the data access costs overheads do not increase the asymptotic run-time. Second, I’ll show how data reduction techniques can be used to reduce the size of the database, improving quantum speedups for clustering and other tasks in optimization and machine learning. While this talk is mostly focused on Grover, many of the same points about input data model apply more generally to the adiabatic algorithm, variational algorithms, and other quantum optimization algorithms.

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
• MR14, Centre for Mathematical Sciences, Wilberforce Road, Cambridge
• bld31

Note that ex-directory lists are not shown.