Coreset Clustering on Small Quantum Computers
Coreset Clustering on Small Quantum Computers
复制标题
DOI：
10.3390/electronics10141690
复制
发表时间：
2020-04
期刊：
影响因子：
--
通讯作者：
T. Tomesh;P. Gokhale;Eric R. Anschuetz;F. Chong
中科院分区：
文献类型：
--
作者：
T. Tomesh;P. Gokhale;Eric R. Anschuetz;F. Chong
许多机器学习的量子算法需要访问叠加的经典数据，但是，对于许多自然数据集和算法，将数据集加载到叠加中所需的间接费用可以消除与经典算法相比的任何潜在量子加速。混合量子经典计算中的新范式来解决此问题，依靠核心来最大程度地减少量子算法的数据加载开销。通过将其作为QAOA优化实例，在小核心上，我们使用数值模拟来比较我们能够找到经典K-均值聚类的范式。与随机采样相比，与核心良好的数据集以及QAOA可能在核心上超过标准k均值的数据集。对于整个数据集上的K均值优于K均值的量子优势所需的 - 表明是挑战。
Many quantum algorithms for machine learning require access to classical data in superposition. However, for many natural data sets and algorithms, the overhead required to load the data set in superposition can erase any potential quantum speedup over classical algorithms. Recent work by Harrow introduces a new paradigm in hybrid quantum-classical computing to address this issue, relying on coresets to minimize the data loading overhead of quantum algorithms. We investigated using this paradigm to perform k-means clustering on near-term quantum computers, by casting it as a QAOA optimization instance over a small coreset. We used numerical simulations to compare the performance of this approach to classical k-means clustering. We were able to find data sets with which coresets work well relative to random sampling and where QAOA could potentially outperform standard k-means on a coreset. However, finding data sets where both coresets and QAOA work well—which is necessary for a quantum advantage over k-means on the entire data set—appears to be challenging.