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

量子机器学习中的核方法和嵌入量子核函数的计算普适性进行了研究，证明了对于任意核函数总存在对应的量子特征映射和嵌入量子核函数，并且在平移不变核和组合核类中，证明了嵌入量子核函数的计算普适性，同时发现了一些新的量子核函数族的方向，但是否对应于高效的嵌入量子核函数仍然待定。