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.

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

关于嵌入量子核的表达能力

On the expressivity of embedding quantum kernels

This article presents a theoretical evaluation of the computational
universality of decoder-only transformer models. We extend the theoretical
literature on transformer models and show that decoder-only transformer
architectures (even with only a single layer and single attention head) are
Turing complete under reasonable assumptions. From the theoretical analysis, we
show sparsity/compressibility of the word embedding to be a necessary condition
for Turing completeness to hold.

本文从理论上评估解码器型 Transformer 模型的计算普适性，证明单层单注意头的解码器型 Transformer 架构在合理假定下是图灵完备的，同时揭示词嵌入的稀疏性 / 可压缩性是图灵完备性持有的必要条件。

关于仅解码变压器语言模型计算能力的研究

On the Computational Power of Decoder-Only Transformer Language Models

A detailed algorithmic explanation is required for how a network of chemical
reactions can generate the sophisticated behavior displayed by living cells.
Though several previous works have shown that reaction networks are
computationally universal and can in principle implement any algorithm, there
is scope for constructions that map well onto biological reality, make
efficient use of the computational potential of the native dynamics of reaction
networks, and make contact with statistical mechanics. We describe a new
reaction network scheme for solving a large class of statistical problems
including the problem of how a cell would infer its environment from
receptor-ligand bindings. Specifically we show how reaction networks can
implement information projection, and consequently a generalized
Expectation-Maximization algorithm, to solve maximum likelihood estimation
problems in partially-observed exponential families on categorical data. Our
scheme can be thought of as an algorithmic interpretation of E. T. Jaynes's
vision of statistical mechanics as statistical inference.

文章提出了一种基于反应网络的算法来解决统计问题，包括推断环境和最大似然估计等方面，可视为 E.T. Jaynes 的统计力学的统计推断的算法解释。