在量子特征空间中使用量子相似性矩阵的无监督聚类

摘要

一种用于执行数据点的无监督聚类的方法包括基于每个数据点的特征维度来确定要包括在量子处理器中的量子位的数量。该方法包括，对于每个数据点对，在具有所确定的量子位的数量的量子处理器上执行量子电路。所述量子电路包括被参数化为具有第一多个旋转的特征图模板电路、被参数化为具有第二多个旋转的后向特征图模板电路、以及输出相似性度量的度量电路。所述方法包括基于每个数据点对的相似性度量来创建相似性矩阵，并且将相似性矩阵输入经典聚类算法以对数据点进行聚类。特征图模板电路和后向特征图模板电路各自使用量子处理器的量子位的叠加和纠缠的量子特性。

说明书

技术领域

本发明涉及无监督聚类，并且更具体地，涉及在量子特征空间中使用量子相似性矩阵的无监督聚类。

背景技术

无监督学习(Unsupervised learning)是许多大数据工作流程的关键组成部分，尤其是在制药和生物科学中。当数据包含大量测量数据时，通常不可能按比例进行标记，并且依赖聚类来将数据处理成可解释的组。

因此，在本领域中需要解决上述问题。

发明内容

从第一方面来看，本发明提供了一种执行多个数据点的无监督聚类的方法，包括：基于所述多个数据点中的每一个数据点的多个特征维度来确定要包括在量子处理器中的量子位的数量；对于所述多个数据点的每个数据点对，在具有所述确定的数量的量子位的量子处理器上执行量子电路，其中所述量子电路包括：特征图模板电路，其被参数化为具有第一多个旋转，其中所述第一多个旋转基于所述数据点对的第一数据点的特征值；后向特征图模板电路，其被参数化为具有第二多个旋转，其中所述第二多个旋转基于所述数据点对的第二数据点的特征值；以及度量电路，其输出所述数据点对的相似性度量；基于每个数据点对的所述相似性度量来创建所述多个数据点的相似性矩阵；以及将所述相似性矩阵输入到经典聚类算法以聚类所述多个数据点，其中所述特征图模板电路和所述后向特征图模板电路各自使用所述量子处理器的所述量子位的叠加和纠缠的量子特性。

从另一方面来看，本发明提供了一种混合量子经典系统，包括：量子处理器，所述量子处理器具有与要被聚类的多个数据点中的每个数据点的多个特征维度相对应的多个量子位，所述量子处理器被配置成：对于所述多个数据点的每个数据点对，执行量子电路，所述量子电路包括：特征图模板电路，其被参数化为具有第一多个旋转，其中所述第一多个旋转基于所述数据点对的第一数据点的特征值；后向特征图模板电路，其被参数化为具有第二多个旋转，其中所述第二多个旋转基于所述数据点对的第二数据点的特征值；以及度量电路，其输出所述数据点对的相似性度量，其中所述特征图模板电路和所述后向特征图模板电路各自使用所述量子处理器的所述量子位的叠加和纠缠的量子特性；以及经典处理器，其与所述量子处理器通信，所述经典处理器被配置成：接收所述多个数据点的每个数据点对的所述相似性度量；基于每个数据点对的所述相似性度量来创建所述多个数据点的相似性矩阵；以及对所述相似性矩阵执行经典聚类算法以聚类所述多个数据点。

根据本发明的实施例，一种对多个数据点进行无监督聚类的方法包括基于该多个数据点的每个数据点的多个特征维度来确定要包括在量子处理器中的量子位的数量。该方法包括，对于该多个数据点中的每一个数据点对，在具有所确定的量子位数量的量子处理器上执行量子电路。所述量子电路包括被参数化为具有第一多个旋转的特征图模板电路，其中所述第一多个旋转基于所述数据点对中的第一数据点的特征值。量子电路还包括被参数化为具有第二多个旋转的后向特征图模板电路，其中所述第二多个旋转基于数据点对中的第二数据点的特征值。量子电路还包括输出针对数据点对的相似性度量的度量电路。该方法包括基于每个数据点对的相似性度量来创建多个数据点的相似性矩阵，并将所述相似性矩阵输入经典聚类算法以聚类所述多个数据点。特征图模板电路和后向特征图模板电路各自使用量子处理器的量子位的叠加和纠缠的量子特性。

根据本发明的实施例，一种混合量子经典系统包括量子处理器。所述量子处理器具有多个量子位，所述多个量子位对应于要被聚类的多个数据点中的每个数据点的多个特征维度。所述量子处理器被配置成针对所述多个数据点中的每个数据点对执行量子电路。所述量子电路包括被参数化为具有第一多个旋转的特征图模板电路，其中所述第一多个旋转基于所述数据点对中的第一数据点的特征值。所述量子电路包括被参数化为具有第二多个旋转的后向特征图模板电路，其中所述第二多个旋转基于数据点对中的第二数据点的特征值。所述量子电路包括输出针对数据点对的相似性度量的度量电路。特征图模板电路和后向特征图模板电路各自使用量子处理器的量子位的叠加和纠缠的量子特性。所述混合量子经典系统包括与所述量子处理器通信的经典处理器。所述经典处理器被配置成接收所述多个数据点中的每一数据点对的相似性度量，基于每一数据点对的相似性度量来创建所述多个数据点的相似性矩阵，并且对所述相似性矩阵执行经典聚类算法以聚类所述多个数据点。

附图说明

现在将参照优选实施例仅通过示例的方式描述本发明，如以下附图所示：

图1是示出根据本发明实施例的执行多个数据点的无监督聚类的方法100的流程图。

图2是根据本发明实施例的特征图模板电路的示例的示意图。

图3是根据本发明实施例的量子电路的示例的示意图。

图4是根据本发明实施例的混合量子经典系统的示意图。

图5显示了数据集的模拟和实验结果。

具体实施方式

聚类是以相同聚类中的对象比其它聚类中的对象彼此更相似的方式将一组对象分组的任务。无监督聚类是将样本从高维分布分类为离散数量的聚类而不需要训练数据来这样做的无监督学习。聚类算法对样本之间的距离的概念进行操作。在最简单的情况下，使用点积。

常见的大规模示例包括在寻找生物疗法或通过RNA测序或蛋白质存在来分类细胞时对配体进行分组。聚类还用于营销以识别具有特定偏好的客户群，从而允许公司针对特定产品广告将特定客户作为目标。

谱聚类算法是利用数据的所提供的相似性矩阵的特征值以允许在特征空间中进行聚类的聚类算法，该特征空间遵循数据的更自然的维度。谱聚类算法的性能取决于所提供的相似性矩阵封装数据点之间的距离的程度。例如，如果两个聚类在三维中被径向地分开，则使用三维径向距离度量来计算相似性矩阵的算法将胜过一维线性距离度量。除了谱聚类之外，还有使用所提供的相似性矩阵来确定聚类的其他聚类算法。这些的例子包括DBSCAN和凝聚分层聚类(agglomerative hierarchical clustering)。

在上述生物和化学情况以及许多其它情况下，所讨论的配体更自然地通过它们的高维量子表征和它们彼此的量子距离来描述。这个距离对于经典计算机是不可访问的，因为它需要计算分子大小的波函数指数，并且地面实况经典数据的值对于有意义的距离度量而言可能太混乱和非线性。这是这些领域的困难的核心。因此，如果我们想要准确地将这些系统聚类以能够分析或隔离重要的组，则我们必须使用量子计算机来产生数据点之间的关系。本文描述的方法和系统使用量子核来表示希尔伯特空间中两个样本之间的距离。

即使对于非生物数据，使用量子距离也能够给予我们对经典计算机不可访问的特征空间的访问，从而指数地扩展可用聚类途径的范围。在近期，我们将只能使用噪声中级量子(NISQ)系统，因此当我们使用这些器件以最大化量子优势的机会时，我们必须关于如何设计我们的量子方法具有非常大的选择性。在混合量子经典系统中使用较短电路的方法是最有前景的前沿。

图1是示出根据本发明实施例的执行多个数据点的无监督聚类的方法100的流程图。方法100包括基于多个数据点102中的每一个的多个特征维度来确定要包括在量子处理器中的量子位的数量。方法100进一步包括，对于多个数据点中的每一对数据点，在该量子处理器上执行具有确定的数量的量子位104的量子电路。该量子电路包括参数化为具有第一多个旋转的特征图模板电路。第一多个旋转基于数据点对中的第一数据点的特征值。量子电路还包括参数化为具有第二多个旋转的后向特征映射模板电路。第二多个旋转基于所述数据点对中的第二数据点的特征值。量子电路还包括输出数据点对的相似性度量的度量电路。方法100包括基于每对数据点的相似性度量来创建数据集的相似性矩阵106。方法100包括将相似性矩阵输入到经典聚类算法以聚类多个数据点108。特征图模板电路和后向特征图模板电路各自使用量子处理器的量子位的叠加和纠缠的量子特性。

具有n个特征维度的数据点的特征值可以由(特征值_1、特征值_2、...、特征值_n)表示。例如，具有两个特征维度的数据点可以具有值(0.1，0.2)，其中0.1是第一特征的特征值，0.2是第二特征的值。这里假设多个数据点中的每个数据点具有相同数量的特征维度。

根据本发明的一个实施例，对于每个特征维度在该量子处理器中包括一个量子位。然而，本发明的实施例不限于每特征单个量子位。量子处理器中量子位的数量可以大于或小于特征的数量

根据本发明的实施例，特征图模板电路包括多个纠缠双量子位量子门。例如，特征图模板电路可以包括多个CNOT门。

图2是根据本发明实施例的特征图模板电路200的示例的示意图。特征图模板电路200对两个量子位q0 202和q1 204进行操作。量子位q0 202和q1 204可以是数据量子位，并且可以各自使用多个物理量子位来实现。量子位q0 202和q1 204可以被初始化为基态

例如，门可以是旋转算子(rotation operator)。可基于数据点的一个或多个特征值将旋转参数化。例如，图2中的U1门206的变量可取决于数据点的第一特征值。图2中的U1门208变量可取决于数据点的第二特征值。图2中的U1门210的变量可取决于数据点的第一特征值和第二特征值。例如，变量可以取决于第一特征值和第二特征值的乘积。

特征图模板电路200可以包括纠缠双量子位量子门，例如CNOT门216、218。特征图模板电路200可以包括重复的一系列门。例如，门206-218可以重复，如图2所示，在特征图模板中重复一系列门的次数可以取决于特征图的复杂度。对于高度复杂的特征图，可以将一系列门重复10、20、50或更多次。

特征图模板电路200意在作为非限制性示例。特征图模板中可包含门的替代类型、组合及数目。此外，可以以不同于图2所示的顺序包括门。特征图模板电路可以作用于多于两个量子位。例如，对于具有n个特征维度的数据点，特征图模板电路可以作用于n个量子位。

特征图模板电路可以与后向特征图模板电路和度量电路组合以形成量子电路。根据本发明实施例的后向特征图模板电路包括一系列门，所述一系列门“撤销”特征图模板电路的门的旋转。反向特征图模板电路的旋转可以由第二数据点的特征值参数化。因此，通过基于第一数据点的特征值执行第一系列旋转，然后基于第二数据点的特征值执行第二系列“撤销”旋转，可以获得两个数据点之间的距离的量子模拟。该量子距离可以用于构建相似性矩阵。

图3是根据本发明实施例的量子电路300的示例的示意图。量子电路300用于提供其特征值可以表示为(0.1，0.2)和(0.3，0.4)的一对二维数据点的相似性度量。对于包括多于两个数据点的数据集，针对每对数据点实现量子电路。

量子电路300作用于具有两个量子位q0302和q1304的量子处理器上。量子电路300包括特征图模板电路306、后向特征图模板电路308和度量电路310。特征映射模板电路306包括基于第一数据点(0.1，0.2)的特征值而参数化的门。

根据本发明的实施例，特征图模板电路306包括针对每个特征维度基于针对该特征维度的数据点对中的第一数据点的特征值而参数化的旋转。例如，在图3中，特征图模板电路306包括基于第一数据点的第一特征值0.1而参数化的U1门312。在图3所示的例子中，将第一特征量乘以2，基于该积对U1门312进行参数化，即2*0.1＝0.2。特征图模板电路314还包括基于第一数据点的第二特征值0.2而参数化的U1门308。在图3所示的例子中，将第二特征量乘以2，基于该积对U1门314进行参数化，即2*0.2＝0.4。

根据本发明的实施例，特征图模板电路306包括针对每个特征维度基于针对该特征维度的多个数据点中的第一数据点的特征值而参数化的多个旋转。例如，在图3中，特征图模板电路306包括基于第一数据点的第一特征值0.1而参数化的第一U1门312，以及基于第一数据点的第一特征值0.1而参数化的第二U1门316。如上所述，特征图模板电路可以包括重复两次或更多次的一系列操作。

根据本发明的实施例，特征图模板电路306包括针对数据点中的第一数据点基于第一数据点的多个特征值而参数化的旋转。例如，特征图模板电路306包括基于第一数据点的第一特征值0.1和第二特征值0.2而参数化的U1门318。如图3所示，U1门318基于17.89参数化，其基于第一特征值和第二特征值计算：17.89＝2*(π-0.1)(π-0.2)。提供该数量作为如何基于数据点的多个特征值对旋转进行参数化的非限制性示例。

后向特征图模板电路308包括基于第二数据点(0.3，0.4)的特征值而参数化的门。根据本发明的实施例，对于每个特征维度，后向特征图模板电路308包括基于特征维度的数据点对中的第二数据点的特征值而参数化的至少一个旋转。例如，后向特征图模板电路308包括基于第二数据点的第一特征值0.3而参数化的U1门318。后向特征映射模板电路308还包括基于第二数据点的第二特征值0.4而参数化的U1门320。

后向特征图模板电路308之后是度量电路310。度量电路输出包括在量子处理器中的每个量子位的度量值。每个量子位的度量可以被读出到一个相应的经典位。例如，在图3中，量子位q0302的度量可以被读出到经典位c0322，并且量子位q1304的度量可以被读出到经典位c1324。每个相应的经典位被组合以提供相似性度量。例如，可以读取两位数字C1C0作为相似性度量的值(例如11＝3)。对于两个数据点i和j，相似性度量可以用作相似性矩阵的第i、第j个元素。相似性度量可以直接输入到相似性矩阵中，或者可以用于确定要输入到相似性矩阵中的数目。例如，可以通过对相似性度量进行乘法、除法或取反来找到该数目。可以通过将相似性度量输入到输出要在相似性矩阵中使用的数目的函数中来找到该数目。

图4是根据本发明实施例的混合量子经典系统400的示意图。系统400包括量子处理器402。量子处理器402具有多个量子位404、406，这些量子位对应于有待被聚类的多个数据点中的每个数据点的多个特征维度。量子处理器402被配置成针该多个数据点中的每个数据点对执行量子电路。量子电路包括被参数化为具有第一多个旋转的特征图模板电路，其中第一多个旋转基于该数据点对中的第一数据点的特征值。量子电路包括被参数化为具有第二多个旋转的后向特征图模板电路，其中第二多个旋转基于数据点对中的第二数据点的特征值。量子电路包括输出数据点对的相似性度量的度量电路。特征图模板电路和后向特征图模板电路各自使用量子处理器的量子位的叠加和纠缠的量子特性。该量子处理器402的特征图模板电路、后向特征图模板电路、以及度量电路可以具有以上参照图1至图3所描述的属性。

混合量子经典系统400包括与量子处理器402通信的经典处理器408。经典处理器被配置成接收多个数据点中的每对的相似性度量，并且基于每个数据点对的相似性度量来创建多个数据点的相似性矩阵。经典处理器408还被配置成对相似性矩阵执行经典聚类算法以对多个数据点进行聚类。

根据本发明的实施例，经典处理器408还被配置为将多个数据点中的每个数据点分配给聚类，并且针对多个数据点中的每个数据点输出对聚类的指示。

传统的处理器408可以是专用的“硬连线”设备，或者它可以是可编程设备。例如，它可以是但不限于个人计算机、工作站或用于特定应用的任何其它合适的电子设备。在一些实施例中，它可以被集成到单元中，或者它可以是可附接的、远程的和/或分布式的。

根据本发明的实施例，混合量子经典系统使用量子设备来计算一些数据的相似性矩阵，然后将相似性矩阵输入经典谱聚类算法。与使用在经典计算机上计算的相似性矩阵的算法相比，该系统可以在可以使用量子特征图分离的数据点上更好地执行。特别地，该系统采用利用叠加和纠缠的量子特性的量子特征图。在经典计算机上的特征空间中实现相同的维数将需要指数时间(除非多项式层次结构崩溃)。

我们将使用量子设备计算的相似性矩阵并入如下的谱聚类算法中。从要被聚类的数据集开始，我们使用特征维度的数目来确定要在相似性矩阵的计算中使用的量子位的数量。根据本发明的实施例，量子位的数量等于特征维度。在确定要使用的量子位的数量之后，我们使用作用于所确定的量子位的数量的量子电路来计算相似性矩阵。我们确保选择包括特征图模板电路的量子电路，该特征图模板电路使用叠加和纠缠的量子特性。特征图模板电路被特别设计成传统上指数地难以模拟。

对于每对数据点，我们创建并运行量子电路以度量两个数据点之间的距离。量子电路包括一个特征图模板电路，其被参数化为具有等于第一数据点的特征值的旋转。量子电路还包括后向特征图模板电路，其被参数化为具有等于第二数据点的特征值的旋转。量子电路包括输出针对数据点对的相似性度量的度量电路。度量电路可以度量所确定的量子位的数量中的每个量子位。量子位的值可以被读出到指示数据点对的相似性度量的经典位上。我们使用每个数据点对的相似性度量来创建相似性矩阵。我们将相似性矩阵输入经典聚类算法，以计算所提供的数据集中的聚类。根据本发明的实施例，经典聚类算法是谱聚类算法。然而，本发明的实施例不限于谱聚类算法。可以使用其它类型的聚类算法，例如k-Means聚类和密度聚类。此外，可以基于要使用的特定经典聚类算法来构造量子电路。

我们已经使用已知其聚类标识的数据集来实现和测试了该系统，因此可以验证该系统的准确性。该系统能够以100％的准确性识别两个聚类，而具有传统计算的相似度矩阵的谱聚类完全不能对数据进行聚类。图5示出了一个数据集的模拟结果500和实验结果502，其中具有聚类的三种不同度量的结果：(1)Fowles_mallows，(2)交互信息，以及(3)rand_index。聚类的三种不同度量是评价聚类算法执行得有多好的三种不同方法。对于实际结果502，量子电路在量子硬件中实现。

对于每个数据集，针对量子电路结合以下三种经典算法之一来执行使用混合量子经典算法的仿真：“凝聚(agglomerative)”、“dbscan”和“谱(spectral)”。“1.0的值表示每个数据点被精确聚类，而低于1.0的值表示不准确的聚类。如图5所示，每个模拟的混合量子经典算法的值为1.0，表明100％的准确度。

对于每个数据集，对四种经典算法中的每一种执行使用纯经典算法的模拟：“linear”，“poly”，“rbf”和“sigmoid”。如图5所示，纯经典算法比混合系统具有低得多的准确度。

三个不同度量的实验结果502每个具有等于或非常接近于1的值，这表明即使在物理硬件中实现时也具有高准确度。图5中的结果突出了本文所公开的方法和系统准确地聚类对于经典计算机而言非常有问题的数据集的能力。

已经出于说明的目的给出了本发明的各种实施例的描述，但是其不旨在是穷尽的或限于所公开的实施例。在不背离所描述的实施例的范围的情况下，许多修改和变化对于本领域的普通技术人员将是显而易见的。选择本文所使用的术语以最好地解释实施例的原理、实际应用或对市场上存在的技术改进，或使本领域的其他普通技术人员能够理解本文所公开的实施例。