Quantum machine learning with large data sets

Today I came across this interesting paper by Aram Harrow, which presents a lucid discussion and possible solution to one of the big problems with quantum machine learning: how to obtain useful quantum speedups when dealing with big data sets that are slow to feed into and read out of the quantum processor.

The main point is that real world classical data sets are likely to lack special structure to enable them to be efficiently encoded into quantum states (a prerequisite for quantum algorithms with a proven speedup). Input and output of large data sets will thus overwhelm any possible near-term quantum advantage. Therefore, an essential step of any practical quantum machine learning algorithm will be to first preprocess the data to obtain a smaller but representative subset.

How then can the quantum computer help us? We should look for quantum speed ups in searching the space of machine learning models used to describe the reduced data set. Most machine learning models have some form of structure. That is, they can be specified in terms of relatively simple functions such as matrix multiplications or minimizing quadratic loss functions. The quantum computer can exploit this structure to place the available models in a quantum superposition and then achieve a speedup using rigorously-proven algorithms, such as Grover search to find the best model.

However, Grover search is impractical to run on near-term devices, which are largely limited to variational quantum algorithms which lack proven speedups. This paper has tested how well classical data preprocessing works in combination with the quantum approximate optimization algorithm (QAOA), focusing on k-means clustering. In the small scale examples considered, QAOA did not work well with the reduced data set. The authors conjecture that the poor performance may either be limitation of QAOA (requiring the exploration of other NISQ-friendly algorithms), or due to the rather small sizes of the reduced data sets (up to 20 points are used to summarize the full sets containing thousands of points). 

It will be interesting to explore these ideas further.