Multi-class quantum k-nearest-neighbour classification in a single quantum circuit
本文提出了一种用于多类k-最近邻分类的新颖且可完全实现的量子电路，该电路通过利用叠加态、由受控SWAP门组成的蝴蝶网络以及几何保真度分析，在无需依赖量子随机存取存储器（QRAM）或预言机等假设性原语的情况下，实现了具有明确阐述的操作成本的单次执行精确比较。
原始论文采用 CC BY 4.0 许可（https://creativecommons.org/licenses/by/4.0/）。 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。 阅读完整免责声明
在计算领域，有些问题虽然陈述起来很简单，但当数据量增长时，解决起来却极其困难。其中一个挑战就是寻找最匹配项。想象一位图书管理员必须通过将新请求与书架上的每一本书进行比较，来找到与之最相似的一本书。在经典计算机中，这个过程需要逐一检查每一件物品，随着图书馆规模的扩大，这项任务会变得异常缓慢。这就是“k-最近邻”问题（k-nearest neighbor problem）的核心，它是广泛应用于从医疗诊断到电影推荐等各个领域的根本工具。几十年来，科学家们一直希望量子计算机能够以一种本质上不同的方式处理信息，从而瞬间解决这种搜索问题。然而，以往构建这种量子搜索工具的尝试要么依赖于现实世界中尚不存在的理论捷径，要么局限于只能解决非常简单的二选一问题。
来自康科迪亚大学（Concordia University）的一个研究小组现在展示了一种执行此类搜索的新方法，该方法无需那些并不存在的捷径。他们设计了一个量子电路，可以在单次机器执行中，将单个新查询与包含许多不同类别的庞大训练数据集进行比较。他们的工作证明，构建一个能够同时处理多类数据的量子分类器是可行的，且不需要那种能够瞬间访问任何数据的假设性存储设备。他们并没有依赖魔法或未经证实的科技，而是使用标准的物理操作构建了一个系统，这些操作可以在实际的量子硬件上运行。结果显示，在模拟中，该机器的准确度与最好的经典方法相匹配，并提供了一条新的架构路径，该路径不需要将整个训练集加载到独立的、庞大的存储库中。
研究人员首先着手解决如何将普通数据转化为量子计算机能够理解的语言的问题。量子机器运行在必须具有特定数学尺寸的状态上，就像气球必须充气到精确的体积才能保持形状一样。如果你只是简单地缩小一个大型物体以使其适应，你就会丢失关于其原始大小的信息。该团队使用了一种称为“逆立体投影”（inverse stereographic projection）的数学技术，将数据映射到一个球面上。这个过程非常巧妙，因为它在将数据点拟合到所需的量子格式的同时，保留了数据的原始大小和形状。通过这样做，他们确保了原始数据中两点之间的距离能忠实地反映在它们的量子表示之间的距离中。这一步至关重要；否则，量子计算机比较的将是扭曲的影子而非实际物体，从而导致错误的答案。
一旦数据被正确编码，团队就构建了一个充当巨大比较引擎的电路。在传统方法中，计算机会先将新查询与第一个训练点进行比较，然后是第二个，接着是第三个，以此类推。本文描述的量子电路则采取了更激进的做法：它将所有训练数据置于一种叠加态中，即它们同时以所有可能状态组合的形式存在。该电路随后使用一个受控交换（controlled swaps）网络，这可以被视为一种复杂的排序机制，来进行数据路由。这个网络允许量子计算机同时将查询与来自每一个类别的每一个训练点进行比较。机器不需要顺序检查它们；它一次性评估整个图书馆。
测量过程的核心依赖于一种被称为 SWAP 测试的技术。这是一种检查两个量子态之间相似程度的过程。如果两个状态完全相同，测试会产生一种结果；如果它们不同，则产生另一种结果。研究人员设计的电路使得获得特定测量结果的概率与训练点距离查询点的远近直接相关。通过多次运行电路并统计结果，机器可以构建出一个关于哪些训练点是最接近匹配项的统计图景。至关重要的是，该电路还能追踪每个最近邻所属的类别。这使得系统可以进行“多数投票”，根据最近邻的情况决定最终的标签，就像人类在询问一群专家意见时所做的那样。
该团队使用一个涉及四个不同数据类别的基准测试对他们的设计进行了测试，其中包含了数千次模拟比较。他们发现，该量子电路重现了经典方法的精确决策规则。在无限次测量的极限情况下，量子系统与经典系统在每一个测试案例上都达成了一致。即使在现实次数的测量下，量子分类器的准确度也与经典方法仅差极小，在最困难的情景下差异也小于一个百分点。这种性能水平意义重大，因为它表明量子方法并未为了速度或复杂性而牺牲准确性。该系统成功识别了正确的邻居并分配了正确的标签，证明了其底层逻辑经得起推敲。
这项工作的核心优势在于它避免了对“量子随机存取存储器”（QRAM）的需求。许多之前的量子机器学习提案都假设存在这种技术，即量子计算机可以瞬间从庞大的存储库中检索任何数据片段。然而，QRAM 目前仍是一个理论概念，尚未被制造出来，甚至在物理上可能无法大规模构建。新设计并不使用 QRAM，而是将数据直接加载到电路的寄存器中。虽然这个加载过程所需的时间与数据规模成正比，但它是一个实际可行的、可实现的步骤，不依赖于假设性的硬件。研究人员透明地说明了这一成本，指出加载数据的时间目前是主要的瓶颈，但他们展示了比较环节的过程是非常高效的，并且不需要将数据存储在独立的、无法直接访问的存储器中。
研究人员还将他们的方法与其他近年来提出的量子方法进行了对比。他们发现，依赖于不同类型数据编码的方法往往会丢失关于数据点大小的重要信息，从而导致较低的准确度。他们的方法由于保留了数据的完整几何结构，表现得与最好的经典方法一样出色，并优于其他依赖于不完整编码的量子方案。此外，在统计包括用于持有数据的内存量在内的总物理组件数量时，对于超过一定规模的数据集，他们的设计比基于 QRAM 的方法更高效。这表明，他们的架构不仅是一个理论上的奇思妙想，更是未来硬件的一条可行路径。
研究结论指出，构建一个无需依赖未证实技术的、能够实现多类分类的量子分类器是可能的。该系统成功地将经典数据转化为量子态，将查询与整个数据集进行同步比较，并以高准确度读取结果。虽然目前系统的速度受限于将数据加载进来的时间，但其架构本身是稳健且模块化的。这意味着，随着科学家开发出更好的向量子计算机加载数据的方法，这个特定的电路设计可以直接从中受益，而无需重新设计。这项工作清晰、具体地演示了如何利用量子干涉来解决经典的搜索问题，使该领域向能够真正协助分析复杂数据的实用应用迈出了坚实的一步。
您所在领域的论文太多了？
获取与您研究关键词匹配的最新论文每日摘要——附技术摘要，使用您的语言。