On the expressivity of embedding quantum kernels

• DOI: 10.48550/arxiv.2309.14419
• Publication Date: 2023-01-01
• Authors: Elies Gil-Fuster; Jens Eisert; Vedran Dunjko
• Keywords: Kernel (algebra)

One of the most natural connections between quantum and classical machine learning has been established in context kernel methods. Kernel methods rely on kernels, which are inner products feature vectors living large spaces. Quantum kernels typically evaluated by explicitly constructing states then taking their product, here called embedding kernels. Since usually without using explicitly, we wonder how expressive are. In this work, raise fundamental question: can all be expressed as product states? Our first result is positive: Invoking computational universality, find that for any function there always exists a corresponding map an kernel. The more operational reading question concerned with efficient constructions, however. second part, formalize universality For shift-invariant use technique random Fourier features to show they universal within broad class allow variant sampling. We extend new so-called composition also contains projected introduced recent works. After proving both identify directions towards new, exotic, unexplored families, it still remains open whether correspond