变分量子近似谱聚类如何避开核矩阵?

该论文用紧凑量子电路估计拉普拉斯瑞利商,跳过核矩阵构造。

直接答案

论文用三个紧凑的量子电路估计量取代显式核矩阵构造:邻接二次型、度加权二次型和投影惩罚项。三者合起来直接从数据嵌入电路评估归一化拉普拉斯瑞利商,作者认为惩罚项可以用相对较少的测量次数可靠采样。

1篇文献引用

本文由 WisPaper 驱动的搜索和论文分析生成。

三个电路估计量取代一个核矩阵

经典谱聚类先对 M 个训练样本建立相似度矩阵,构造图拉普拉斯,再求解特征问题。论文的出发点是:真正昂贵的对象是矩阵及其特征分解——构造和操作稠密核通常至少需要 O(M^2),精确求解特征问题则需要 O(M^3)。近似方法能降低这一代价,但论文指出它们仍要构造部分核矩阵。

论文提出的替代方案从不组装这个矩阵。一个数据嵌入酉操作制备 M 个经特征映射样本的索引叠加态,一个可训练加权态为每个样本索引赋予权重 alpha_i。随后三个电路分别估计标量:q_a 对应邻接二次型,q_d 对应度加权二次型,q_p 对应投影惩罚项。经典后处理把它们组合成目标函数,因此核只通过电路内部评估的保真度核重叠进入计算。

瑞利商让特征向量搜索保持浅层

目标函数是归一化瑞利商 J(alpha) = (alpha†A alpha - xi alpha†D 1 1†D alpha) / (alpha†D alpha),其中 xi > 0。在可训练权重上最大化它,扮演的是经典谱聚类中特征向量计算所扮演的角色。邻接项奖励与高相似度结构对齐,度项按样本连接度归一化,投影项抑制平凡的全一方向。

正是这一形式使浅层电路设计成为可能。优化器不需要估计单个核元素再对角化,只需要三个二次型的标量估计。论文指出,整体电路深度由数据嵌入过程主导,可训练加权使用参数规模为 O(poly log M) 的硬件高效拟设;方法被描述为不依赖特定拟设。

惩罚项估计所需测量次数不随 M 增长

最具决策相关性的理论结果针对投影惩罚项 q_p。作者用集中不等式分析有限测量次数下的训练期复杂度,结论是惩罚量所需的测量次数与训练数据集规模 M 无关。这一点重要,因为惩罚项是度加权的平方平均,否则看起来会随数据集增大而要求更高精度。

论文的解释是惩罚项估计量在高维希尔伯特空间中集中。作者明确指出,同一集中现象常被视为变分量子算法可训练性的障碍,但在这里它朝相反方向起作用,使惩罚项的采样成本保持相对较小。这是关于惩罚项估计量测量预算的陈述,并不声称整条流程在任何规模下都便宜。

模拟验证优化行为与有限测量行为

实证证据属于概念验证。在标准数据集上,模拟显示欠参数化硬件高效拟设具有可靠的优化行为,即可训练电路的参数少于完全表达性拟设所需的参数。有限测量模拟进一步重现了惩罚项估计量的预测采样行为,支持理论测量分析。

论文还报告,惩罚项估计在 256、512、1024 和 8192 次测量下呈现相似趋势,与其定理一致。这些是模拟结果而非硬件执行结果,作者把整个验证定位为概念验证,而不是量子优势的展示。

测试点靠相位而非矩阵查表打标签

如果推理仍需要核矩阵,那么训练时避开它就不完整。论文为未见点 x-hat 增加了一个打分电路:在 sigma_x 和 sigma_y 基下测量辅助量子比特,估计 q_Hx 和 q_Hy,再通过 arctan2 把它们转换为 [-pi, pi] 内的相位 phi-hat。聚类标签来自对该相位的阈值化或圆形聚类。

打分本身是 s(x-hat, alpha-hat) = sum_i alpha-hat_i kappa(x_i, x-hat),即测试点与训练样本之间的加权相似度。相位表示携带训练权重的复相位,因此标签分配同时使用幅度和相位信息,而不是单一实值分数。

效率主张针对电路而非核的实用性

论文明确表示,它并未确立保真度核本身带来的量子优势。在作者的表述中,该核是否对一般机器学习任务广泛有用仍是开放问题。其贡献是在量子核方法已被选为无监督学习工具的前提下,提供更高效的电路实现。

第二个适用范围条件是特征映射。编码电路按预设固定,这保持了希尔伯特空间中诱导分布几何的一致性,但论文指出,此前没有研究识别出无监督场景下量子编码的有利区间。模拟在标准数据集上进行并被描述为概念验证,因此结果支持的是可行性和采样行为,而不是大规模性能。

惩罚项分析或可迁移到其他变分目标

作者指出一个具体扩展方向:许多组合优化任务被表述为二次无约束二值优化问题,并用目标函数含一个或多个惩罚项的变分电路求解。由于这里的测量分析表明惩罚项估计量无需大测量预算即可采样,同样的推理可能有助于降低这些场景中的查询需求。

这是提出的方向,不是已证明的结果。论文自身已证明的重点更窄:对于使用保真度核的谱聚类,惩罚项是作者能够独立于 M 界定其采样成本的分量,模拟与该界一致。权衡这一方法的读者应把惩罚项测量结果视为论文最强的可迁移主张,而把聚类准确率证据视为早期阶段。

本文引用的文献

1

Variational Quantum Approximated Spectral Clustering

紧凑量子电路直接估计归一化拉普拉斯瑞利商,绕过核矩阵构造;惩罚项估计量的测量次数被证明与训练数据集规模无关。