QUACK: Quantum Aligned Centroid Kernel

量子计算（QC）似乎显示出在机器学习（ML）中应用的潜力。特别是，量子核方法（QKM）展示了在监督学习任务中使用的有前途的特性。然而，核方法的一个主要缺点是它们与训练样本数量的不利二次缩放。加上目前可用的量子硬件（NISQ设备）的限制，其低量子比特相干时间、少量量子比特和高误差率，QC在工业相关规模的ML中的使用目前是不可能的。作为改进QKM潜在应用的一小步，我们引入QUACK，一种量子核算法，其时间复杂度在训练期间与样本数量呈线性缩放，并且在推理阶段与训练样本数量无关。在训练过程中，仅计算样本和类中心的核条目，即n个样本和c个类的核的最大形状为（n，c）。在训练期间，迭代优化量子核和质心的位置。在推理阶段，对于每个新样本，电路仅针对每个质心进行评估，即c次。我们表明，QUACK算法仍然提供令人满意的结果，并且可以在训练期间以二次缩放的经典核方法类似的水平执行。此外，我们的（模拟）算法能够处理具有784个特征的高维数据集（如MNIST），而不需要任何降维。

解决问题：论文试图解决什么问题，或者验证什么假设？这是否是一个新问题？

关键思路：论文中解决问题的方案关键思路是什么？相比当前这个领域的研究状况，这篇论文的思路有什么新意？

其他亮点：论文提出了QUACK算法，其时间复杂度在训练时随着样本数量线性增长，在推理阶段与训练样本数量无关。该算法能够处理高维数据集，如MNIST，而无需进行降维。实验结果表明，该算法在训练时能够表现出与传统核方法相似的性能。

相关研究：目前在这个领域中，还没有类似QUACK算法的研究。