Recent theoretical results in quantum machine learning have demonstrated a
general trade-off between the expressive power of quantum neural networks
(QNNs) and their trainability; as a corollary of these results, practical
exponential separations in expressive power over classical machine learning
models are believed to be infeasible as such QNNs take a time to train that is
exponential in the model size. We here circumvent these negative results by
constructing a hierarchy of efficiently trainable QNNs that exhibit
unconditionally provable, polynomial memory separations of arbitrary constant
degree over classical neural networks in performing a classical sequence
modeling task. Furthermore, each unit cell of the introduced class of QNNs is
computationally efficient, implementable in constant time on a quantum device.
The classical networks we prove a separation over include well-known examples
such as recurrent neural networks and Transformers. We show that quantum
contextuality is the source of the expressivity separation, suggesting that
other classical sequence learning problems with long-time correlations may be a
regime where practical advantages in quantum machine learning may exist.

最近的量子机器学习的理论结果表明了量子神经网络（QNNs）的表达能力和可训练性之间的一般性权衡；作为这些结果的推论，实际中在表达能力上超过经典机器学习模型的指数级差异被认为是不可行的，因为这样的 QNNs 训练所需的时间与模型大小的指数成正比。我们通过构建一种层次化的可高效训练的 QNNs，成功地绕过了这些负面结果，其在经典序列建模任务中展示了无条件可证的多项式内存分离性能，而且所引入的 QNNs 的每个单元均在量子设备上能够以恒定的时间进行计算。我们证明了这种分离性能在经典神经网络类型中成立，包括循环神经网络和 Transformer 等众所周知的网络。我们展示了量子背景的特殊性是导致表达能力分离的根源，这表明在具有长时间相关性的其他经典序列学习问题中，量子机器学习可能存在实际上的优势。

可训练量子机器学习中的任意多项式分离

Arbitrary Polynomial Separations in Trainable Quantum Machine Learning

Ambiguities in natural language give rise to probability distributions over
interpretations. The distributions are often over multiple ambiguous words at a
time; a multiplicity which makes them a suitable topic for sheaf-theoretic
models of quantum contextuality. Previous research showed that different
quantitative measures of contextuality correlate well with Psycholinguistic
research on lexical ambiguities. In this work, we focus on coreference
ambiguities and investigate the Winograd Schema Challenge (WSC), a test
proposed by Levesque in 2011 to evaluate the intelligence of machines. The WSC
consists of a collection of multiple-choice questions that require
disambiguating pronouns in sentences structured according to the Winograd
schema, in a way that makes it difficult for machines to determine the correct
referents but remains intuitive for human comprehension. In this study, we
propose an approach that analogously models the Winograd schema as an
experiment in quantum physics. However, we argue that the original Winograd
Schema is inherently too simplistic to facilitate contextuality. We introduce a
novel mechanism for generalising the schema, rendering it analogous to a
Bell-CHSH measurement scenario. We report an instance of this generalised
schema, complemented by the human judgements we gathered via a crowdsourcing
platform. The resulting model violates the Bell-CHSH inequality by 0.192, thus
exhibiting contextuality in a coreference resolution setting.

我们提出了一种新颖的方法，将 Winograd 模式广义化，从而使其类似于 Bell-CHSH 测量方案，并通过人们在众包平台上收集的人类判断报告了一个这种广义模式的实例。所得模型违反了 Bell-CHSH 不等式 0.192，从而在指代消解设置中展示出了上下文相干性。