Potential and limitations of random Fourier features for dequantizing quantum machine learning
This work addresses the challenge of assessing quantum advantage in machine learning for researchers in quantum computing, though it is incremental as it builds on existing dequantization methods.
The paper tackled the problem of dequantizing variational quantum machine learning for regression using random Fourier features, establishing conditions for efficient dequantization and identifying structures necessary for potential quantum advantage.
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.