Reproduce “Advantage of Quantum Machine Learning from General Computational Advantages” on OpenResearch

About this paper

Hayata Yamasaki, Natsuto Isogai, Mio Murao

This paper rigorously constructs a general class of supervised learning problems where quantum computers offer a provable speedup over any classical counterpart. The work defines "quantumly advantageous functions" as a new basis for quantum machine learning advantages, moving beyond prior reliance on Shor's algorithm.

Key insights

• The quantum advantage in machine learning can stem from the computational hardness of the feature map itself, not solely from the dimensionality of the feature space.
• A broader family of supervised learning tasks with provable quantum advantage can be constructed using 'quantumly advantageous functions' as feature maps, which are efficiently computable by quantum algorithms but not classically.
• Proof techniques based on finite field vector spaces offer a generalizable method for demonstrating classical hardness, moving beyond specific cryptographic assumptions tied to Shor's algorithm.

Summary by alphaXiv.