NeurIPS 2020

Learning with Optimized Random Features: Exponential Speedup by Quantum Machine Learning without Sparsity and Low-Rank Assumptions

Meta Review

The paper gives an O(input dimension) quantum ML algorithm for kernel methods with random Fourier features, without requiring sparsity or low-rank assumptions. This is a much improved resubmission from a different venue, and is able to avoid relying on quantum RAM. The fact that it relies on only standard input and does not rely on assumptions on the data are very nice. Some of the reviewers were not as convinced looking at the classical techniques (RFF), but after discussion they ultimately agreed that this is a significant contribution to Quantum ML. However there are a few clarity issues that will need to be addressed in the final version.