導(dǎo) 讀

本文是 ICML 2023 入選論文 Near-Optimal Quantum Coreset Construction Algorithms for Clustering 的解讀。該論文作者為北京大學(xué)計算機學(xué)院博士生薛燁誠、信息科學(xué)技術(shù)學(xué)院圖靈班本科生陳曉雨，以及前沿計算研究中心的助理教授李彤陽博士和姜少峰博士。

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

01

引言：什么是量子計算？

量子計算（Quantum Computing）是一種不同于經(jīng)典計算機的計算模型。上世紀七八十年代，隨著量子力學(xué)的發(fā)展，相關(guān)研究提出了觀測、模擬量子系統(tǒng)的需求，而構(gòu)建遵循量子力學(xué)而非經(jīng)典物理原理的“量子計算機”的想法也應(yīng)運而生。1982年，F(xiàn)eynman 提出，用經(jīng)典計算機模擬量子體系的演化具有本質(zhì)的困難，而使用“量子計算機”來完成這些工作也許是一條可行的道路。1985年，Deutsch 從理論計算機的角度思考和提出了“通用量子計算機”的概念。1994年，Shor 提出的大數(shù)質(zhì)因數(shù)分解的量子算法向人們揭示了量子計算可觀的加速潛能。如今，量子計算仍在蓬勃發(fā)展。將量子計算應(yīng)用于機器學(xué)習(xí)、對機器學(xué)習(xí)問題研究更快的量子算法也成為一個方興未艾的研究領(lǐng)域。

目前，一種常用的量子機器學(xué)習(xí)算法設(shè)計方法是，使用經(jīng)典的算法框架，而在算法的具體實現(xiàn)中，一些較為復(fù)雜、在經(jīng)典計算機上耗時較多的子過程由量子設(shè)備來完成。我們的算法也屬于這一類雜交算法。Grover 算法[1]（或者更廣泛地， amplitude amplification 算法）及在此基礎(chǔ)上衍生出的種種量子子程序常在這一類算法中起到重要作用。

我們簡單介紹一下最簡單版本的 Grover 算法?？紤]在一個規(guī)模為 N 的數(shù)據(jù)集中尋找一個特定的數(shù)據(jù)點。我們事先不知道關(guān)于這一數(shù)據(jù)點的任何信息，只能在數(shù)據(jù)集中任意拿出一個點，并判斷它是不是我們要尋找的。在經(jīng)典計算模型下，每次取樣得到所求數(shù)據(jù)點的概率為1/N，需要O(N)次訪問才能保證以常數(shù)概率得到所求的數(shù)據(jù)點。而在量子計算模型下，我們可以構(gòu)造這樣一個量子態(tài)：

這是一個均勻疊加態(tài)。由于量子力學(xué)的規(guī)則，其每個分量的振幅為1/\sqrt{N}而非1/N。我們可以將一些量子操作作用于這一量子態(tài)上，使得在所求數(shù)據(jù)點的振幅較小的時候，每次操作其振幅都有大約O(1/\sqrt{N})的增長。在測量量子態(tài)時，振幅模長的平方即為測量得到相應(yīng)分量的概率。因此在量子計算中，我們只需O(\sqrt{N}) 次操作即可保證以常數(shù)概率得到所求數(shù)據(jù)點。這相對于經(jīng)典計算有平方加速。

利用 Grover 算法的原理，人們研究出了種類多樣、用途廣泛的量子子程序。比如 Brassard 等人的量子計數(shù)算法[2]，Hamoudi 的多個量子態(tài)制備算法[3]等等。

02

問題描述：聚類問題的核心集

聚類（clustering）是一類重要的無監(jiān)督機器學(xué)習(xí)問題。這類問題關(guān)注的是，對于一系列雜亂無章而可能存在潛在的數(shù)據(jù)模式的數(shù)據(jù)點，如何將它們合理地劃分為不同的類別。k-median 問題是最基礎(chǔ)、最受關(guān)注的聚類問題之一，其定義為：

設(shè)在d維歐氏空間中有一個規(guī)模為n的數(shù)據(jù)集D，給定一個整數(shù)參數(shù)k，求一個歐氏空間中規(guī)模為k的點集C ，使得其代價函數(shù)

最小。這里dist(x, C)為數(shù)據(jù)點x到集合C的l_{2}距離。k-means 問題與之類似，唯一的區(qū)別是代價函數(shù)被定義為距離之平方的和。

精確地求解k-median 問題是 NP 難的。因此，一個重要的研究方向是求 k-median 問題的近似解。核心集是求解聚類問題近似解的一項有力技術(shù)。一個ε核心集往往由一個規(guī)模較小（常常只有poly(k)）的集合S和該集合上的一個權(quán)重函數(shù)構(gòu)成，使得對于歐氏空間中任何一個規(guī)模不大于k的集合C，都有

這意味著，對任何一個可行解C，用原始數(shù)據(jù)集D和核心集S計算代價函數(shù)所得的結(jié)果是極為接近的。因此，任何一個對小規(guī)模核心集S的近似解也是對原始數(shù)據(jù)集D的一個近似解。在得到核心集后，為得到原問題的近似解，只需在核心集上運行一個求解算法即可。

03

理論成果：\tilde{O}(\sqrt{n k})的量子核心集構(gòu)造算法

本論文首次提出了一種能夠在\tilde{O}(\sqrt{n k})時間內(nèi)構(gòu)造核心集的量子算法。算法所構(gòu)造的核心集規(guī)模為poly(k)。人們可以進而在這一核心集上運行一個求解算法，并得到原問題的一個近似解。下表中列出了論文所得的一些結(jié)果及其與經(jīng)典結(jié)果的對比。

表格中的定理編號為論文中的編號。表格中呈現(xiàn)了我們對k-median 和 k-means 這兩種最受關(guān)注的聚類問題的結(jié)果，包括算法復(fù)雜度和相符合的下界。此前，關(guān)于此類問題最好的經(jīng)典結(jié)果是 Braverman 等人提出的 k-median 核心集構(gòu)造算法[4]，其時間復(fù)雜度為O(n+poly(k))。而我們的量子算法是亞線性的，打破了經(jīng)典算法自然的線性時間復(fù)雜度下界。并且從我們所證明的量子復(fù)雜度下界中可以看出，在忽略對數(shù)因子的情況下，我們的算法是最優(yōu)的。

對于更普遍的(k,z)-clustering 問題，我們的算法同樣適用。在論文中，我們給出了對一般(k,z) -clustering 問題的量子算法及其正確性證明。

04

技術(shù)概述：經(jīng)典算法的量子實現(xiàn)和多維量子計數(shù)算法

我們算法設(shè)計的主要思路是選擇了兩個已有的經(jīng)典算法并完成了它們量子化的實現(xiàn)，通過將一些在經(jīng)典計算機上耗時較長的子過程替換為能夠完成相同任務(wù)的量子算法來獲得加速。我們首先用 Thorup 的近似求解算法[5]得到一個雙標準近似解A，然后在這一近似解基礎(chǔ)上，利用 Cohen-Addad 等人的核心集構(gòu)造算法[6]來構(gòu)造一個核心集。

Cohen-Addad 等人的核心集構(gòu)造算法主要包括兩個階段：首先，將整個數(shù)據(jù)集D利用A劃分為一系列每組內(nèi)數(shù)據(jù)點有一定相似性的群組，群組的數(shù)目與n和k無關(guān)；然后在每個群組中進行抽樣，將抽得的樣本點賦權(quán)，以此構(gòu)成核心集。對后一個階段，我們將原來的經(jīng)典抽樣方法換成了量子抽樣。在前一個階段中，算法首先將數(shù)據(jù)集以A中的點為中心分為若干類，對于每個類計算其規(guī)模大小等性質(zhì)，并據(jù)此將每個類劃分成一系列環(huán)。然后通過計算這些環(huán)的一些性質(zhì)，將性質(zhì)相似的環(huán)聚合為一個群組。為以量子方式在盡量短的時間內(nèi)完成這種對每個類、每個環(huán)的性質(zhì)的計算，我們提出了多維量子計數(shù)算法。這一算法在其他量子機器學(xué)習(xí)問題中也可能發(fā)揮作用。

考慮一個規(guī)模為n的數(shù)據(jù)集D，這一數(shù)據(jù)集被劃分為m個子集，有一個映射告訴我們每個數(shù)據(jù)點被劃分到了哪個子集中。試求每個子集中的元素個數(shù)。

這一問題在經(jīng)典計算機上似乎需要至少Ω(n)時間來求解，因為我們必須知道每一個數(shù)據(jù)點被劃分到了哪個子集。我們給出了一個量子算法，可以在 \tilde{O}(\sqrt{n m}/ε) 時間內(nèi)求得對所有子集規(guī)模的ε估計。我們同時證明了一個相應(yīng)的下界，說明我們的算法在忽略對數(shù)因子的情況下是最優(yōu)的。

考慮另外給出D上的一個有界函數(shù)，將每個數(shù)據(jù)點映到一個正整數(shù)。假設(shè)我們所求的不再是每個子集的規(guī)模，而是每個子集中所有點所對應(yīng)的函數(shù)值的和。我們的算法經(jīng)過簡單擴展也可以在幾乎相同的時間復(fù)雜度內(nèi)求解這類問題：只需對函數(shù)值寫出其二進制表示，然后逐比特計算其和并將所得結(jié)果相加即可。

參考文獻

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