本文是 ICML 2023 入选论文 Near-Optimal Quantum Coreset Construction Algorithms for Clustering 的解读。该论文作者为北京大学计算机学院博士生薛烨诚、信息科学技术学院图灵班本科生陈晓雨，以及前沿计算研究中心的助理教授李彤阳博士和姜少峰博士。

 

　　论文地址：https://arxiv.org/abs/2306.02826

 

01 引言：什么是量子计算？

 

　　量子计算（Quantum Computing）是一种不同于经典计算机的计算模型。上世纪七八十年代，随着量子力学的发展，相关研究提出了观测、模拟量子系统的需求，而构建遵循量子力学而非经典物理原理的“量子计算机”的想法也应运而生。1982年，Feynman 提出，用经典计算机模拟量子体系的演化具有本质的困难，而使用“量子计算机”来完成这些工作也许是一条可行的道路。1985年，Deutsch 从理论计算机的角度思考和提出了“通用量子计算机”的概念。1994年，Shor 提出的大数质因数分解的量子算法向人们揭示了量子计算可观的加速潜能。如今，量子计算仍在蓬勃发展。将量子计算应用于机器学习、对机器学习问题研究更快的量子算法也成为一个方兴未艾的研究领域。

 

　　目前，一种常用的量子机器学习算法设计方法是，使用经典的算法框架，而在算法的具体实现中，一些较为复杂、在经典计算机上耗时较多的子过程由量子设备来完成。我们的算法也属于这一类杂交算法。Grover 算法[1]（或者更广泛地， amplitude amplification 算法）及在此基础上衍生出的种种量子子程序常在这一类算法中起到重要作用。

 

　　我们简单介绍一下最简单版本的 Grover 算法。考虑在一个规模为 N 的数据集中寻找一个特定的数据点。我们事先不知道关于这一数据点的任何信息，只能在数据集中任意拿出一个点，并判断它是不是我们要寻找的。在经典计算模型下，每次取样得到所求数据点的概率为1/N，需要O(N)次访问才能保证以常数概率得到所求的数据点。而在量子计算模型下，我们可以构造这样一个量子态：

　　这是一个均匀叠加态。由于量子力学的规则，其每个分量的振幅为1/\sqrt{N}而非1/N。我们可以将一些量子操作作用于这一量子态上，使得在所求数据点的振幅较小的时候，每次操作其振幅都有大约O(1/\sqrt{N})的增长。在测量量子态时，振幅模长的平方即为测量得到相应分量的概率。因此在量子计算中，我们只需O(\sqrt{N}) 次操作即可保证以常数概率得到所求数据点。这相对于经典计算有平方加速。

 

　　利用 Grover 算法的原理，人们研究出了种类多样、用途广泛的量子子程序。比如 Brassard 等人的量子计数算法[2]，Hamoudi 的多个量子态制备算法[3]等等。

 

02 问题描述：聚类问题的核心集

 

　　聚类（clustering）是一类重要的无监督机器学习问题。这类问题关注的是，对于一系列杂乱无章而可能存在潜在的数据模式的数据点，如何将它们合理地划分为不同的类别。k-median 问题是最基础、最受关注的聚类问题之一，其定义为：

 

　　设在d维欧氏空间中有一个规模为n的数据集D，给定一个整数参数k，求一个欧氏空间中规模为k的点集C ，使得其代价函数

　　最小。这里dist(x, C)为数据点x到集合C的l_{2}距离。k-means 问题与之类似，唯一的区别是代价函数被定义为距离之平方的和。

图示：聚类问题

 

　　精确地求解k-median 问题是 NP 难的。因此，一个重要的研究方向是求 k-median 问题的近似解。核心集是求解聚类问题近似解的一项有力技术。一个ε核心集往往由一个规模较小（常常只有poly(k)）的集合S和该集合上的一个权重函数构成，使得对于欧氏空间中任何一个规模不大于k的集合C，都有

　　这意味着，对任何一个可行解C，用原始数据集D和核心集S计算代价函数所得的结果是极为接近的。因此，任何一个对小规模核心集S的近似解也是对原始数据集D的一个近似解。在得到核心集后，为得到原问题的近似解，只需在核心集上运行一个求解算法即可。

图示：核心集

 

03 理论成果：\tilde{O}(\sqrt{n k})的量子核心集构造算法

 

　　本论文首次提出了一种能够在\tilde{O}(\sqrt{n k})时间内构造核心集的量子算法。算法所构造的核心集规模为poly(k)。人们可以进而在这一核心集上运行一个求解算法，并得到原问题的一个近似解。下表中列出了论文所得的一些结果及其与经典结果的对比。

 

 

　　表格中的定理编号为论文中的编号。表格中呈现了我们对k-median 和 k-means 这两种最受关注的聚类问题的结果，包括算法复杂度和相符合的下界。此前，关于此类问题最好的经典结果是 Braverman 等人提出的 k-median 核心集构造算法[4]，其时间复杂度为O(n+poly(k))。而我们的量子算法是亚线性的，打破了经典算法自然的线性时间复杂度下界。并且从我们所证明的量子复杂度下界中可以看出，在忽略对数因子的情况下，我们的算法是最优的。

 

　　对于更普遍的(k,z)-clustering 问题，我们的算法同样适用。在论文中，我们给出了对一般(k,z) -clustering 问题的量子算法及其正确性证明。

 

04 技术概述：经典算法的量子实现和多维量子计数算法

 

　　我们算法设计的主要思路是选择了两个已有的经典算法并完成了它们量子化的实现，通过将一些在经典计算机上耗时较长的子过程替换为能够完成相同任务的量子算法来获得加速。我们首先用 Thorup 的近似求解算法[5]得到一个双标准近似解A，然后在这一近似解基础上，利用 Cohen-Addad 等人的核心集构造算法[6]来构造一个核心集。

 

　　Cohen-Addad 等人的核心集构造算法主要包括两个阶段：首先，将整个数据集D利用A划分为一系列每组内数据点有一定相似性的群组，群组的数目与n和k无关；然后在每个群组中进行抽样，将抽得的样本点赋权，以此构成核心集。对后一个阶段，我们将原来的经典抽样方法换成了量子抽样。在前一个阶段中，算法首先将数据集以A中的点为中心分为若干类，对于每个类计算其规模大小等性质，并据此将每个类划分成一系列环。然后通过计算这些环的一些性质，将性质相似的环聚合为一个群组。为以量子方式在尽量短的时间内完成这种对每个类、每个环的性质的计算，我们提出了多维量子计数算法。这一算法在其他量子机器学习问题中也可能发挥作用。

 

　　考虑一个规模为n的数据集D，这一数据集被划分为m个子集，有一个映射告诉我们每个数据点被划分到了哪个子集中。试求每个子集中的元素个数。

　　这一问题在经典计算机上似乎需要至少Ω(n)时间来求解，因为我们必须知道每一个数据点被划分到了哪个子集。我们给出了一个量子算法，可以在 \tilde{O}(\sqrt{n m}/ε) 时间内求得对所有子集规模的ε估计。我们同时证明了一个相应的下界，说明我们的算法在忽略对数因子的情况下是最优的。

 

　　考虑另外给出D上的一个有界函数，将每个数据点映到一个正整数。假设我们所求的不再是每个子集的规模，而是每个子集中所有点所对应的函数值的和。我们的算法经过简单扩展也可以在几乎相同的时间复杂度内求解这类问题：只需对函数值写出其二进制表示，然后逐比特计算其和并将所得结果相加即可。

 

参考文献

[1] Grover, Lov K. "A fast quantum mechanical algorithm for database search." Proceedings of the twenty-eighth annual ACM symposium on Theory of computing. 1996.

[2] Brassard, Gilles, Peter Høyer, and Alain Tapp. "Quantum counting." Automata, Languages and Programming: 25th International Colloquium, ICALP'98 Aalborg, Denmark, July 13–17, 1998 Proceedings 25. Springer Berlin Heidelberg, 1998.

[3] Hamoudi, Yassine. "Preparing many copies of a quantum state in the black-box model." Physical Review A 105.6 (2022): 062440.

[4] Braverman, Vladimir, et al. "Clustering high dimensional dynamic data streams." International Conference on Machine Learning. PMLR, 2017.

[5] Thorup, Mikkel. "Quick k-median, k-center, and facility location for sparse graphs." SIAM Journal on Computing 34.2 (2005): 405-432.

[6] Cohen-Addad, Vincent, David Saulpic, and Chris Schwiegelshohn. "A new coreset framework for clustering." Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing. 2021.