Optimal Algorithmic Complexity of Inference in Quantum Kernel Methods¶

会议: NeurIPS 2026
arXiv: 2604.15214
OpenReview: https://openreview.net/forum?id=dMzQUanLcb
领域: 物理/科学计算
关键词: 量子核方法, 量子振幅估计, 查询复杂度, 门复杂度, 早期容错量子计算

一句话总结¶

本文系统研究了量子核方法在推断阶段的算法复杂度，通过构建单可观测量编码与量子振幅估计，消除了查询复杂度中对训练样本数的依赖，达到理论最优的 $\mathcal{O}(\|\alpha\|_1/\varepsilon)$。

研究背景与动机¶

量子核方法作为实现有监督量子机器学习（QML）量子优势的核心候选框架，通过量子特征映射 $x \mapsto \rho(x)$ 将经典输入映射到高维希尔伯特空间中，构造出非经典计算难以模拟的内积核函数 $k(x, x') = \mathrm{Tr}\{\rho(x)\rho(x')\}$。在完成参数训练后，部署模型对新样本进行推断需要计算带权核和 $f_\alpha(x) = \sum_{i=1}^N \alpha_i k(x, x_i)$。然而，传统核推断方案通常采用采样方式逐项估计各个训练样本 $x_i$ 与查询样本 $x$ 的核值，导致推断成本随着训练集规模 $N$ 线性甚至超线性增长。这一开销不仅在样本规模扩大时带来难以承受的量子算力负担，更使量子核方法在实际落地时面临严重的效率瓶颈。

现存的核心矛盾在于两方面评估模式的粗粒度选择：在估计各个独立期望值时，传统的散粒采样（Shot-based Sampling）受限于中心极限定理，收敛速度仅为标准统计率 $\mathcal{O}(\varepsilon^{-2})$；而在整合训练集全部核值的加权和时，惯用的“逐项列表求和”（List-and-Sum）策略迫使量子线路必须对每一个样本点分别进行重复执行与测量，完全割裂了量子叠加态直接编码全局线性组合的独特潜力。即使部分工作尝试利用量子相位估计或替代模型，也因依赖 QRAM、特定的特征映射假设或未优化的门开销，缺乏对推断复杂度极限的严格界定与硬件可行性指导。

为了彻底突破这一推断瓶颈，本文从量子查询复杂度与门复杂度的第一性原理出发，系统解耦并形式化了核推断的两个独立改进维度：单个期望值的估计算法（经典采样 vs. 量子振幅估计）以及加权和的逼近机制（逐项累加 vs. 单可观测量全局编码）。核心 idea：将整个核推断的加权求和统一编码为单可观测量在叠加态下的期望值，并结合量子振幅估计实现无 $N$ 依赖且精度二次加速的 $\mathcal{O}(\|\alpha\|_1/\varepsilon)$ 最优查询算法，同时在有限门深与硬件约束下给出兼顾总门数的实用策略选择。

方法详解¶

整体框架¶

量子核推断的目标是对于给定待测样本 $x$ 与训练参数 $\alpha \in \mathbb{R}^N$，将加权和 $f_\alpha(x) = \sum_{i=1}^N \alpha_i k(x, x_i)$ 估计到加性误差 $\varepsilon$ 以内。本文将整个算法设计空间解构为两个正交轴：在纵向轴上决定加权和的处理机制（逐项求和 List-and-Sum 与单可观测量全局编码 All-at-Once），在横向轴上选择测量估计技术（采样估计 Sampling 与量子振幅估计 QAE）。本文提出的核心架构通过无 QRAM 的受控线路构建出训练集酉算子 $O^\dagger(S)$，将参数系数振幅编码为态 $|\alpha\rangle$，从而将目标函数转化为单个量子可观测量 $\mathcal{M}(\alpha, S)$ 的期望值，最终通过统一的振幅编码酉算子 $V$ 调用 QAE 完成高精度推断。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["输入查询样本 x<br/>与训练参数 alpha"] --> B["系数态与训练集酉算子编码<br/>W(alpha) 与 O(S) 准备叠加态"]
    B --> C["单可观测量全局统一编码<br/>将全和转化为单可观测量期望值 M(alpha, S)"]
    C --> D["双路振幅分离与量子振幅估计<br/>将 f+ 与 f- 编码至辅助比特并运行 QAE"]
    D --> E["输出高精度推断值 f_alpha(x)<br/>达到查询最优界 O(||alpha||_1 / eps)"]

关键设计¶

1. 系数态与训练集酉算子编码：摆脱 QRAM 的受控硬件级实现 在构建全局量子可观测量时，最大的工程痛点在于传统算法往往假设昂贵且短期内难以实现的量子随机存取内存（QRAM）。本文提出了基于经典已知训练集 $S=\{(x_i, y_i)\}_{i=1}^N$ 的受控电路编译方案。具体而言，定义系数态制备算符 $W(\alpha)$ 在 $(\lceil \log_2 N \rceil + 1)$ 个量子比特上制备振幅编码态 $|\alpha\rangle = \sum_{i=1}^N \sqrt{p_i} |i\rangle \otimes |s_i\rangle$，其中 $p_i = |\alpha_i| / \|\alpha\|_1$ 为权重归一化概率分布，$s_i = \mathrm{sign}(\alpha_i)$ 为对应符号。同时，设计训练集酉算子： $$O^\dagger(S) \coloneqq \prod_{i=1}^N U^\dagger(x_i)_{\mathrm{data}} \otimes |i\rangle\langle i|_{\mathrm{idx}}$$ 由于训练点 $x_i$ 在训练后完全已知，该算符通过多控制门级联离线编译，无需量子内存介入，仅使用 $N$ 次受控特征映射调用，单个查询的门复杂度严格控制在 $\mathcal{O}(N(G + \log N))$。

2. 单可观测量全局统一编码：将离散核值求和压缩为单次测量 传统逐项求和在样本量大时必须反复执行 $N$ 次独立估计，各点统计误差叠加导致查询数陡增。本文证明了存在有界厄米可观测量 $\mathcal{M}(\alpha, S)$（其算子范数满足 $\|\mathcal{M}(\alpha, S)\|_\infty \le \|\alpha\|_1$），使得其在由输入态演化的量子态 $|\phi(x)\rangle$ 下的单次期望值严格等于目标推断函数： $$\langle \phi(x) | \mathcal{M}(\alpha, S) | \phi(x) \rangle = f_\alpha(x) = \sum_{i=1}^N \alpha_i k(x, x_i)$$ 这一构造的核心优势在于将所有训练样本与测试样本之间的希尔伯特空间重叠完全在量子相干层级内完成干涉求和，从根本上消除了统计查询数对训练样本量 $N$ 的显式依赖。

3. 双路振幅分离与量子振幅估计：在全实数域下实现海森堡极限 由于核方法系数 $\alpha_i$ 包含正负两类权重，直接进行概率测量会导致正负符号抵消产生不可观测性。本文将加权和精确解耦为正项与负项归一化分量： $$f_\pm \coloneqq \frac{1}{\|\alpha\|_1} \sum_{i=1}^N \delta_{s_i, \pm 1} |\alpha_i| k(x, x_i), \quad f_\alpha(x) = \|\alpha\|_1 (f_+ - f_-)$$ 为了能同时对其进行量子振幅估计，设计了紧凑的统一振幅编码酉算符 $V$： $$V |0\rangle = \sqrt{f_+} |\psi_+\rangle |0, 0\rangle + \sqrt{f_-} |\psi_-\rangle |0, 1\rangle + \sqrt{1 - f_+ - f_-} \left( |\psi_{\mathrm{trash}}\rangle |1, 0\rangle + |\psi'_{\mathrm{trash}}\rangle |1, 1\rangle \right)$$ 利用无相位估计的量子振幅估计（QAE）例程，仅需 $n + \lceil \log_2 N \rceil + 3$ 个量子比特，便能以 $\mathcal{O}(\|\alpha\|_1 / \varepsilon)$ 次酉算子调用分别估计 $f_+$ 与 $f_-$，并证明与其匹配的查询下界为 $\Omega(\|\alpha\|_1 / \varepsilon)$，在查询复杂度上达到了理论上的严格最优。

损失函数 / 训练策略¶

虽然本文专注于推断（Inference）阶段的算法复杂度界定，但推断算法的理论开销直接依赖于训练阶段产出的系数向量 $\alpha$ 的范数结构。为了使推断阶段的量子查询复杂度 $\mathcal{O}(\|\alpha\|_1 / \varepsilon)$ 与总门开销达到全局最优，训练优化问题中必须引入促使系数稀疏化或最小化 1-范数的正则化约束： $$\min_{\alpha} \mathcal{L}_{\mathrm{train}}(\alpha) + \lambda \|\alpha\|_1$$ 通过在训练时控制 $\|\alpha\|_1$ 的上界并诱导大量系数置零，推断时的有效样本数 $N$ 可以直接收缩为支撑向量（Support Vectors）的数量，进一步放大全和量子振幅估计算法在实际早期容错硬件上的计算加速优势。

实验关键数据¶

主实验¶

本文通过形式化理论证明与系统复杂度分析，建立了不同策略在核推断任务上的查询复杂度渐近对比。对比基线涵盖传统的逐项固定预算采样、逐项自适应预算采样、单可观测量采样以及结合量子振幅估计的各变体，并给出了匹配的信息论下界。

算法策略 (Strategy)	求和机制 (Summation)	估计技术 (Estimation)	查询复杂度 (Query Complexity)	达到下界 / 最优性 (Optimality)
Naive List-and-Sum	逐项固定预算 (Fixed)	经典采样 (Sampling)	$\mathcal{O}(N^2 \\|\alpha\\|_\infty^2 / \varepsilon^2)$	否 (非最优)
List-and-Sum (Adaptive)	逐项自适应 (Adaptive)	经典采样 (Sampling)	$\mathcal{O}(N \\|\alpha\\|_2^2 / \varepsilon^2)$	否 (标准基线)
All-at-Once (Sampling)	单可观测量 (Single Obs)	经典采样 (Sampling)	$\mathcal{O}(\\|\alpha\\|_1^2 / \varepsilon^2)$	否 (无QAE加速)
List-and-Sum + QAE	逐项自适应 (Adaptive)	量子振幅估计 (QAE)	$\mathcal{O}(N^{1/3} \\|\alpha\\|_{2/3} / \varepsilon)$	否 (含N弱相关)
All-at-Once + QAE (本文)	单可观测量 (Single Obs)	量子振幅估计 (QAE)	$\mathcal{O}(\\|\alpha\\|_1 / \varepsilon)$	严格最优 ($\Omega(\\|\alpha\\|_1 / \varepsilon)$ 匹配)

消融实验¶

在关注物理执行硬件时，查询复杂度并不完全等价于物理量子门的执行开销。本文深入分析了不同策略在单次查询门数（Gate Cost per Query）、量子比特开销（Qubit Overhead）以及总门复杂度（Total Gate Complexity）上的消融与权衡：

算法配置 (Configuration)	辅助比特开销 (Qubits)	单次查询门数 (Gates/Query)	总门复杂度 (Total Gate Cost)	硬件适用场景 (Hardware Regime)
List-and-Sum (Sampling)	$n + 1$	$\mathcal{O}(G)$	$\mathcal{O}(G \cdot N \\|\alpha\\|_2^2 / \varepsilon^2)$	近期 NISQ 硬件 (无相干深度)
All-at-Once (Sampling)	$n + \lceil\log_2 N\rceil + 2$	$\mathcal{O}(N(G + \log N))$	$\mathcal{O}(N(G + \log N) \\|\alpha\\|_1^2 / \varepsilon^2)$	浅深度叠加采样
List-and-Sum + QAE	$n + 2$	$\mathcal{O}(G)$	$\mathcal{O}(G \cdot N^{1/3} \\|\alpha\\|_{2/3} / \varepsilon)$	早期容错硬件总门数最低
All-at-Once + QAE (本文)	$n + \lceil\log_2 N\rceil + 3$	$\mathcal{O}(N(G + \log N))$	$\mathcal{O}(N(G + \log N) \\|\alpha\\|_1 / \varepsilon)$	查询瓶颈型容错架构

关键发现¶

算法的查询最优性与硬件门最优性存在深刻分歧：All-at-Once + QAE 方案成功将查询次数中的 $N$ 消除，降至严格最优的 $\mathcal{O}(\|\alpha\|_1 / \varepsilon)$；但由于每次查询需要遍历受控训练集线路（单次门开销含 $N$），其实际总门开销包含因子 $N \|\alpha\|_1 / \varepsilon$。
在实际硬件受限的早期容错阶段，当特征映射电路 $G$ 占主导而受控编译开销较大时，采用自适应预算分配的“逐项估计 + 量子振幅估计”（List-and-Sum + QAE）策略能够维持更浅的线路深度与更少的辅助量子比特，且取得比 All-at-Once 策略更低的总门数 $\mathcal{O}(G N^{1/3} \|\alpha\|_{2/3} / \varepsilon)$。
相比传统采样方法，量子振幅估计在精度 $\varepsilon$ 上带来了确定的二次量子加速（从 $\varepsilon^{-2}$ 优化至 $\varepsilon^{-1}$），这一特性在需要高精度推断（$\varepsilon \ll 1$）的任务中尤为显著。

亮点与洞察¶

建立统一分类坐标系：本文将分散在不同文献中的核方法推断技巧系统梳理为“求和机制 × 估计方式”二维矩阵，清晰勾勒出量子机器学习推断的算法设计全景。
无 QRAM 的严谨电路映射：打破了过往理论算法常暗中依赖量子随机存取内存（QRAM）的缺陷，通过对训练集编译单可观测量及双路振幅分离电路，实现了纯受控酉算子级联的确定性构造。
硬件感知的全貌权衡：不仅证明了信息论上的查询最优下界，更务实地从总门数和比特数角度对比了各方案，指出了近期与早期容错量子设备上的最佳实现路径。

局限与展望¶

依赖黑盒特征映射：理论分析将特征映射 $U(x)$ 视为通用黑盒酉算子，未能利用特定特征映射（如乘积态编码或对称结构）在电路简化方面的潜在红利。
早期容错硬件的门深门槛：无论是 QAE 还是包含 $N$ 次受控调用的训练集酉算子，均要求相干电路深度随 $1/\varepsilon$ 或 $N$ 增长，对硬件相干时间提出了严峻挑战。
未来方向可探索在保持查询最优性的同时，结合基于随机化编译或压缩感知的方法，进一步压低单次查询中的受控门数量。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 首次从理论上建立量子核方法推断的查询最优性界限并给出严格下界证明。
实验充分度: ⭐⭐⭐⭐☆ 理论推导完备，复杂度分析深入详尽，但缺乏小规模量子云平台的实际噪声模拟数据。
写作质量: ⭐⭐⭐⭐⭐ 概念界定严谨，二维算法矩阵清晰直观，电路示意图与数学符号高度自洽。
价值: ⭐⭐⭐⭐⭐ 为早期容错时代量子机器学习模型的实际推断提供了极具指导意义的复杂度基准与实现指南。

算法配置 (Configuration)	辅助比特开销 (Qubits)	单次查询门数 (Gates/Query)	总门复杂度 (Total Gate Cost)	硬件适用场景 (Hardware Regime)
List-and-Sum (Sampling)	\(n + 1\)	\(\mathcal{O}(G)\)	\(\mathcal{O}(G \cdot N \\|\alpha\\|_2^2 / \varepsilon^2)\)	近期 NISQ 硬件 (无相干深度)
All-at-Once (Sampling)	\(n + \lceil\log_2 N\rceil + 2\)	\(\mathcal{O}(N(G + \log N))\)	\(\mathcal{O}(N(G + \log N) \\|\alpha\\|_1^2 / \varepsilon^2)\)	浅深度叠加采样
List-and-Sum + QAE	\(n + 2\)	\(\mathcal{O}(G)\)	\(\mathcal{O}(G \cdot N^{1/3} \\|\alpha\\|_{2/3} / \varepsilon)\)	早期容错硬件总门数最低
All-at-Once + QAE (本文)	\(n + \lceil\log_2 N\rceil + 3\)	\(\mathcal{O}(N(G + \log N))\)	\(\mathcal{O}(N(G + \log N) \\|\alpha\\|_1 / \varepsilon)\)	查询瓶颈型容错架构