ICML 2023 | 聚类问题近似最优的量子核心集构造算法

关键词：聚类，核心集，量子计算

导  读

本文是 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 的数据集中寻找一个特定的数据点。我们事先不知道关于这一数据点的任何信息，只能在数据集中任意拿出一个点，并判断它是不是我们要寻找的。在经典计算模型下，每次取样得到所求数据点的概率为  ，需要  次访问才能保证以常数概率得到所求的数据点。而在量子计算模型下，我们可以构造这样一个量子态： 

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

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

02

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

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

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

最小。这里  为数据点  到集合  的  距离。  -means 问题与之类似，唯一的区别是代价函数被定义为距离之平方的和。

图示：聚类问题

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

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

图示：核心集

03

理论成果：  的量子核心集构造算法

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

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

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

04

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

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

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

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

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

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

参考文献

[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.

图文 | 薛烨诚

PKU QUARK Lab

关于量子算法实验室

量子算法实验室 QUARK Lab (Laboratory for Quantum Algorithms: Theory and Practice) 由李彤阳博士于2021年创立。该实验室专注于研究量子计算机上的算法，主要探讨机器学习、优化、统计学、数论、图论等方向的量子算法及其相对于经典计算的量子加速；也包括近期 NISQ (Noisy, Intermediate-Scale Quantum Computers) 量子计算机上的量子算法。

实验室新闻：#PKU QUARK

实验室公众号：

课题组近期动态

—   版权声明  —

本微信公众号所有内容，由北京大学前沿计算研究中心微信自身创作、收集的文字、图片和音视频资料，版权属北京大学前沿计算研究中心微信所有；从公开渠道收集、整理及授权转载的文字、图片和音视频资料，版权属原作者。本公众号内容原作者如不愿意在本号刊登内容，请及时通知本号，予以删除。

点击“阅读原文”转论文链接