在这项工作中，我们提出了一种改进的ML算法来预测基态属性。我们考虑一个 m 维向量 x ∈ [−1， 1]m参数化 n 量子比特间隙几何局部哈密顿量，给定为

 

$$H（x）=\mathop{\sum}\limits_{j}{h}_{j}（{\overrightarrow{x}}_{j}），$$ (1)

其中 x 是常量维向量 \（{\overrightarrow{x}}_{1}，\ldots，{\overrightarrow{x}}_{L}\） 参数化少体交互 \（{h}_{j}（{\overrightarrow{x}}_{j}）\） 的串联。设 ρ（x） 是 H（x） 的基态，O 是几何局部可观测量的总和 ∥O∥ ∞≤ 1.我们假设 n 量子比特系统的几何形状是已知的，但我们不知道 \（{h}_{j}（{\overrightarrow{x}}_{j}）\） 是如何参数化的，也不知道可观察的 O 是什么。目标是从经典数据集中学习一个近似基态属性\（{{{{{{{\rm{Tr}}}}}}}}（O\rho （x））\）的函数h（x），*

 

$$\left（{x}_{\ell }，{y}_{\ell }\right），\quad \forall \ell=1，\ldots，N，$$ (2)

其中 \（{y}_{\ell }\，\approx\， {{{{{{{\rm{Tr}}}}}}}}（O\rho （{x}_{\ell }））\） 记录 x 的基态属性ℓ∈ [−1， 1]m从任意未知分布 \（{{{{{{{\mathcal{D}}}}}}}}\） 中采样。这里，\（{y}_{\ell }\，\approx \，{{{{{{{\rm{Tr}}}}}}}}（O\rho （{x}_{\ell }））\） 表示 yℓ最多ε有加法误差。如果 \（{y}_{\ell }\，=\，{{{{{{{\rm{Tr}}}}}}}}（O\rho （{x}_{\ell }））\），则严格保证得到改善。

 

这部作品中考虑的设置与36，但我们假设 n 量子比特系统的几何形状是已知的，这对于克服 N = n 的样本复杂性下限是必要的 Ω（1/ε)给定于36.这里，f（x） = Ω（g（x）） 表示 f（x） 是 g（x） 的渐近下界，直至恒定因子。人们可以将这种设置与使用绝热量子计算寻找基态的设置进行比较37、38、39、40、41、42、43、44 .为了找到 H（x） 的基态性质 \（{{{{{{{\rm{Tr}}}}}}}}（O\rho （x））\），这类量子算法需要基态 ρ0另一个哈密顿量 H0存储在量子存储器中，明确了解连接 H 的间隙路径0和 H（x），以及对 O 的明确描述。相比之下，这里我们关注的ML算法是完全经典的，无法访问量子态数据，并且不了解哈密顿量H（x），可观测O或H（x）与其他哈密顿量之间的间隙路径。

 

所提出的ML算法使用非线性特征图x↦φ（x），并在映射中内置几何感应偏差。在高层次上，高维向量 φ（x） 包含 m 维向量 x 中每个几何局部坐标子集的非线性函数。在这里，向量 x 坐标上的几何形状是使用 n 量子比特系统的几何形状定义的。ML 算法通过训练 l 来学习函数 h（x） = w ⋅ φ（x）**1-正则化回归 （LASSO）45,46,47在特征空间中。ML算法的概述如图所示。1. 我们证明给定 ε = Θ（1），这里，符号 f（x） = Θ（g（x）） 表示 \（f（x）={{{{{{{\mathcal{O}}}}}}}}（g（x））\） 和 f（x） = Ω（g（x）） 都成立。因此，f（x） 在恒定因子下渐近等于 g（x）。改进后的 ML 算法可以使用

 

$$N={{{{{{{\mathcal{O}}}}}}}}\left（\log \left（n\right）\right），$$ (3)

要学习平均预测误差最多为 ε 的函数 h（x），*

 

$$\mathop{{\mathbb{E}}}\limits_{x \sim {{{{{{{\mathcal{D}}}}}}}}}{\left\vert {h}^{*}（x）-{{{{{{{\rm{Tr}}}}}}}}（O\rho （x））\right\vert }^{2}\le \epsilon，$$ (4)

成功概率高。

 

图1：所提出的机器学习算法概述。

图1

给定一个向量 x ∈ [−1， 1]m该算法参数化了量子多体哈密顿量 H（x），该算法使用几何结构创建一个高维向量 \（\phi （x）\in {{\mathbb{R}}}^{{m}_{\phi }}\）。然后，ML 算法使用 m 预测哈密顿量 H（x） 的基态 ρ（x） 的属性或表示φ-维向量 φ（x）。

 

全尺寸图像

所提出的 ML 算法的样本复杂度 \（N={{{{{{{\mathcal{O}}}}}}}}\left（\log \left（n\right）\right）\） 比以前最著名的经典 ML 算法中 \（N={{{{{{{\mathcal{O}}}}}}}}（{n}^{c}）\） 的样本复杂度有了显著提高36，其中 c 是一个非常大的常数。改进的ML算法和ML算法的计算时间36是 \（{{{{{{{\mathcal{O}}}}}}}}（nN）\）。因此，对数样本复杂度 N 立即意味着近乎线性的计算时间。除了降低样本复杂性和计算时间外，所提出的 ML 算法适用于 x 上的任何分布，而以前已知的最好的算法36仅适用于 [−1， 1] 上的均匀分布m.此外，当我们考虑使用预测误差ε进行缩放时，最著名的经典 ML 算法36 has a sample complexity of \(N={n}^{{{{{{{{\mathcal{O}}}}}}}}(1/\epsilon )}\), which is exponential in 1/ϵ. In contrast, the improved ML algorithm has a sample complexity of \(N=\log (n){2}^{{{{{{{{\rm{polylog}}}}}}}}(1/\epsilon )}\), which is quasi-polynomial in 1/ϵ.

 

我们还讨论了所提出的ML算法在经典阴影表示上训练时预测基态表示的推广48,49,50,51,52.在此设置中，所提出的 ML 算法在样本和时间复杂度方面与36用于预测基态表示。

 

结果

改进的 ML 算法的核心组件是内置于我们的特征映射 \（x\in {[-1,1]}^{m}\mapsto \phi （x）\in {{\mathbb{R}}}^{{m}_{\phi }}\） 中。为了描述ML算法，我们首先需要提出一些与这种几何结构相关的定义。

 

几何感应偏置的定义

我们考虑在 d 维空间中排列在位置或站点的 n 个量子比特，例如，自旋链 （d = 1）、方形晶格 （d = 2） 或立方晶格 （d = 3）。这种几何结构的特征是任意两个量子比特 i 和 \（{i}^{{\prime} }\） 之间的距离 \（{d}_{{{{{{{{\rm{qubit}}}}}}}}}（i，{i}^{{\prime} }）\）。 使用距离 d量子比特在量子比特之间，我们可以定义局部可观察对象的几何形状。给定任意两个可观察量 O一个、OB在 n-qubit 系统上，我们定义距离 dOBS的(O一个、OB） 作为量子比特之间的最小距离，即 O一个和 OB遵行。我们还说，如果一个可观察对象在距离度量 d 下仅对附近的量子比特进行非平凡的作用，那么它就具有几何局部性量子比特.然后我们定义 S（地理）作为所有几何局部泡利可观察量的集合，即属于集合 {I， X， Y， Z 的几何局部可观察量}⊗n.S 的大小（地理）是 \（{{{{{{{\mathcal{O}}}}}}}}（n）\），在量子比特总数中是线性的。

 

有了这些基本定义，我们现在再定义一些几何对象。第一个对象是 m 维向量 x 中接近几何局部泡利可观察 P 的坐标集。这是正式给出的，

 

$${I}_{P}\triangleq \left\{c\in \{1，\ldots，m\}：{d}_{{{{{{{{\rm{obs}}}}}}}}}（{h}_{j（c）}，P）\le {\delta }_{1}\right\}，$$ (5)

其中 hj（c)是 n 量子比特哈密顿量 H（x） 中的少体相互作用项，其参数 \（{\overrightarrow{x}}_{j（c）}\） 包括变量 xc∈ [ − 1， 1] 和 δ1是稍后确定的可高效计算的超参数。每个变量 xc在 m 维向量中，x 正好对应于一个交互项 \（{h}_{j（c）}={h}_{j（c）}（{\overrightarrow{x}}_{j（c）}）\），其中参数向量 \（{\overrightarrow{x}}_{j（c）}\） 包含变量 xc.直觉上，我P是对函数 \（{{{{{{{\rm{Tr}}}}}}}}（P\rho （x））\） 影响最大的坐标集。

 

第二个几何对象是空间 [−1， 1] 上的离散晶格m与每个子集 I 相关联P的坐标。对于任何几何局部泡利可观测 P ∈ S（地理），我们定义 XP包含所有对 I 之外的坐标取值为 0 的向量 xP并为 I 内部的坐标取一组离散值P.从形式上讲，这是由下式给出的

 

$${X}_{P}\triangleq \left.\left\{\begin{array}{l}x\in {[-1,1]}^{m}：\，{{\mbox{if}}}\，\，c \， \notin \， {I}_{P}，\，\，{x}_{c}\，=\，0\quad \hfill \\ \，{{\mbox{if}}}\，\，c\in {I}_{P}，\，\，{x}_{c}\in \left\{0，\pm {\delta }_{2}，\pm 2{\delta }_{2}，\ldots，\pm 1\right\}\quad \end{array}\right.\right\}，$$ (6)

其中δ2是一个可有效计算的超参数，稍后将确定。X的定义P旨在枚举子集 I 中坐标的所有足够不同的向量P⊆ {1， ...， m}.

 

现在给定一个几何局部泡利可观察 P 和一个离散晶格 X 中的向量 xP⊆ [−1， 1]m，第三个对象是一个集合 Tx，P[−1， 1] 中的向量m对于 I 中的坐标，接近 xP.这被正式定义为，

 

$${T}_{x，P}\triangleq \left\{{x}^{{\prime} }\in {[-1,1]}^{m}：-\frac{{\delta }_{2}}{2} \， < \， {x}_{c}-{x}_{c}^{{\prime} }\le \frac{{\delta }_{2}}{2}，\forall c\in {I}_{P}\right\}.$$ (7)

设置 Tx，P定义为靠近向量 x 的加厚仿射子空间，用于 I 中的坐标P.如果向量 \（{x}^{{\prime} }\） 在 T 中x，P，则 \（{x}^{{\prime} }\） 对于 I 中的所有坐标都接近 xP，但对于 I 之外的坐标，\（{x}^{{\prime} }\） 可能与 x 相距甚远P.这些定义的示例在补充图中给出。1 和 2.

 

特征映射和 ML 模型

现在，我们可以通过将 m 维向量 x 转换为 m 来定义特征图φ φ维向量 φ（x） 使用加厚的仿射子空间 \（{T}_{{x}^{{\prime} }，P}\） 用于每个几何局部泡利可观测 P ∈ S（地理）和离散晶格 X 中的每个向量 \（{x}^{{\prime} }\）P.向量 φ（x） 的维数由 \（{m}_{\phi }={\sum }_{P\in {S}^{{{{{{{{\rm{（geo）}}}}}}}}}}|{X}_{P}|\）。向量 φ（x） 的每个坐标由 \（{x}^{{\prime} }\in {X}_{P}\） 和 P ∈ S 索引（地理）跟

 

$$\phi {（x）}_{{x}^{{\prime} }，P}\triangleq {\mathbb{1}}\left[x\in {T}_{{x}^{{\prime} }，P}\right]，$$ (8)

这是检查 x 是否属于加厚仿射子空间的指示函数。回想一下，这意味着 m 的每个坐标φ-维向量 φ（x） 检查 x 是否接近离散晶格 X 上的点 \（{x}^{{\prime} }\） P对于子集 IP接近几何局部泡利可观测 P 的坐标。

 

我们考虑的经典 ML 模型是一个 l1-φ（x） 空间上的正则化回归 （LASSO）。更准确地说，给定一个有效可计算的超参数 B > 0，经典的 ML 模型找到一个 mφ-维向量 w 来自以下优化问题，*

 

$$\mathop{\min }\limits_{\begin{array}{c}{{{{{{{\bf{w}}}}}}}}\in {{\mathbb{R}}}^{{m}_{\phi }}\\ \parallel {{{{{{{\bf{w}}}}}}}}{\parallel }_{1}\le B\end{array}}\，\frac{1}{N}\mathop{\sum }\limits_{\ell=1}^{N}{\left\vert {{{{{{{\bf{w}}}}}}}}\cdot \phi （{x}_{\ell }）-{y}_{\ell }\right\vert }^{2}，$$ (9)

其中\（{\{（{x}_{\ell }，{y}_{\ell }）\}}_{\ell=1}^{N}\） 是训练数据。这里，xℓ∈ [−1， 1]m是一个 m 维向量，用于参数化哈密顿量 H（x） 和 yℓ近似 \（{{{{{{{\rm{Tr}}}}}}}}（O\rho （{x}_{\ell }））\）。学习函数由 h（x） = w ⋅ φ（x） 给出。优化不必完全求解。我们只需要找到一个函数值比最小函数值大 \（{{{{{{{\mathcal{O}}}}}}}}（\epsilon ）\） 的 w。有大量的文献***53、54、55、56、57、58、59改进上述优化问题的计算时间。最著名的经典算法58具有以 m 为单位的线性计算时间缩放φ/ε2高达一个对数因子，而最知名的量子算法59具有以 \（\sqrt{{m}_{\phi }}/{\epsilon }^{2}\） 为单位线性缩放的计算时间，直至一个对数因子。

 

严谨的保障

上面给出的经典 ML 算法产生了以下示例和计算复杂性。该定理大大改进了以下结果36，这需要 \（N={n}^{{{{{{{{\mathcal{O}}}}}}}}（1/\epsilon ）}\）。证明思路在“方法”一节中给出，详细的证明在补充部分1、2、3中给出。使用本文中提出的证明技术，可以证明样本复杂度 \（N=\log （n/\delta ）{2}^{{{{{{{{\rm{polylog}}}}}}}}（1/\epsilon ）}\） 也适用于任何少体可观察量之和 O = ∑jOj带∑j∥Oj∥∞≤1、即使运算符{Oj} 不是几何局部的。

 

定理 1

（样本和计算复杂性）。给定 \（n，\，\delta \， > \， 0，\，\frac{1}{e} \， > \，\epsilon \， > \， 0\） 和一个训练数据集 \（{\{{x}_{\ell }，{y}_{\ell }\}}_{\ell=1}^{N}\） 的大小

 

$$N=\log （n/\delta ）{2}^{{{{{{{{\rm{polylog}}}}}}}}（1/\epsilon ）}，$$ (10)

其中 xℓ从未知分布 \（{{{{{{{\mathcal{D}}}}}}}}\） 和 \（|{y}_{\ell }-{{{{{{{\rm{Tr}}}}}}}}（O\rho （{x}_{\ell }））|\le \epsilon\） 表示任何特征值介于 −1 和 1 之间的可观察 O，可以写成几何局部可观察量的总和。通过正确选择可高效计算的超参数δ1、δ2和 B，则学习函数 h（x） = w ⋅ φ（x） 满足**

 

$$\mathop{{\mathbb{E}}}\limits_{x \sim {{{{{{{\mathcal{D}}}}}}}}}{\left\vert {h}^{*}（x）-{{{{{{{\rm{Tr}}}}}}}}（O\rho （x））\right\vert }^{2}\le \epsilon$$ (11)

概率至少为 1 − δ。经典ML模型的训练和预测时间以\（{{{{{{{\mathcal{O}}}}}}}}（nN）=n\log （n/\delta ）{2}^{{{{{{{{\rm{polylog}}}}}}}}（1/\epsilon ）}\）为界。

 

输出 yℓ在训练中，可以通过多次测量同一可观察 O 的 \（{{{{{{{\rm{Tr}}}}}}}}（O\rho （{x}_{\ell }））\） 并对结果进行平均来获得数据。或者，我们可以使用经典的影子形式主义48,49,50,51,52,60对 ρ（x 进行随机泡利测量ℓ） 来预测 \（{{{{{{{\rm{Tr}}}}}}}}（O\rho （{x}_{\ell }））\） 对于广泛的可观察对象 O。我们还可以结合定理 1 和经典的影子形式主义，使用我们的 ML 算法来预测基态表示，如以下推论所示。这允许人们预测大量可观察 O 的基态属性 \（{{{{{{{\rm{Tr}}}}}}}}（O\rho （x））\），而不仅仅是单个可观察对象。我们在补充部分 3B 中提出了推论 1 的证明。

 

推论 1

给定 \（n，\，\delta\， > \， 0，\，\frac{1}{e} \， > \， \epsilon \， > \， 0\） 和一个训练数据集 \（{\{{x}_{\ell }，{\sigma }_{T}（\rho （{x}_{\ell }））\}}_{\ell=1}^{N}\） 的大小

 

$$N=\log （n/\delta ）{2}^{{{{{{{{\rm{polylog}}}}}}}}（1/\epsilon ）}，$$ (12)

其中 xℓ从未知分布 \（{{{{{{{\mathcal{D}}}}}}}}\） 和 σ 中采样T(ρ（xℓ）） 是基态 ρ（x 的经典阴影表示ℓ） 使用 T 随机泡利测量。对于\（T=\tilde{{{{{{{{\mathcal{O}}}}}}}}}（\log （n）/{\epsilon }^{2}）\），则所提出的ML算法可以学习基态表示\（{\hat{\rho }}_{N，T}（x）\）实现

 

$$\mathop{{\mathbb{E}}}\limits_{x \sim {{{{{{{\mathcal{D}}}}}}}}}|{{{{{{{\rm{Tr}}}}}}}}（O{\hat{\rho }}_{N，T}（x））-{{{{{{{\rm{Tr}}}}}}}}（O\rho （x））{| }^{2}\le \epsilon$$ (13)

对于任何特征值介于 −1 和 1 之间的可观察 O，可以写成概率至少为 1 − δ的几何局部可观察量之和。

 

我们还可以证明，对于无法从数据中学习的非 ML 算法来说，估计参数化哈密顿量 \（H（x）={\sum }_{j}{h}_{j}（{\overrightarrow{x}}_{j}）\） 类的基态属性问题对于无法从数据中学习的非 ML 算法来说是困难的，假设人们普遍认为 NP 完全问题不能在随机多项式时间内求解。这是所研究数据计算能力的体现61.命题 1 的证明36构造一个参数化哈密顿量 H（x），该量属于本文中考虑的参数化哈密顿量家族，因此建立了以下内容。