Abstract

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.