Potential and limitations of random Fourier features for dequantizing
  quantum machine learning
Ryan Sweke Erik Recio Sofiene Jerbi Elies Gil-Fuster Bryce Fuller Jens Eisert Johannes Jakob Meyer
Quantum machine learning is arguably one of the most explored applications of
near-term quantum devices. Much focus has been put on notions of variational
quantum machine learning where parameterized quantum circuits (PQCs) are used
as learning models. These PQC models have a rich structure which suggests that
they might be amenable to efficient dequantization via random Fourier features
(RFF). In this work, we establish necessary and sufficient conditions under
which RFF does indeed provide an efficient dequantization of variational
quantum machine learning for regression. We build on these insights to make
concrete suggestions for PQC architecture design, and to identify structures
which are necessary for a regression problem to admit a potential quantum
advantage via PQC based optimization.