用量子压缩技术在少量子比特上实现高效聚类，适合当前量子设备。
qc-kmeans: A Quantum Compressive K-Means Algorithm for NISQ Devices
- 用傅里叶特征摘要压缩数据，固定大小不随样本增加。
- 仅需最多9个量子比特，峰值量子比特数不随数据量增长。
- 适合资源受限的NISQ设备，仿真中表现接近理想情况。
在当前噪声中等规模量子（NISQ）设备上进行聚类受制于数据加载和量子比特数量限制。本文提出一种混合压缩k均值算法qc-kmeans，通过常数大小的傅里叶特征草图（QFF sketch）总结数据集，并利用浅层QAOA电路求解小规模每组QUBO以选取中心点。该草图估计器无偏，均方误差为$O(\varepsilon^2)$，当$B,S=Θ(\varepsilon^{-2})$时成立；峰值量子比特需求 $q_{\text{peak}}=\max\{D,\lceil \log_2 B\rceil + 1\}$ 不随样本数增加。采用精英保留策略的精炼步骤保证代理代价非递增。在Qiskit Aer模拟中（深度$p=1$），方法在低维合成基准上运行于≤9个量子比特，与量子基线相比达到具有竞争力的平方误差和；运行时间不可直接比较。在九个真实数据集（最多$4.3\times 10^5$个点）上，模拟中保持恒定峰值量子比特使用。在IBM噪声模型下，精度与理想设置相近。总体而言，qc-kmeans提供了面向NISQ的公式，具备浅层、有界宽度电路，在模拟中表现出竞争性聚类质量。
原文摘要 · Abstract (English)
Clustering on NISQ hardware is constrained by data loading and limited qubits. We present \textbf{qc-kmeans}, a hybrid compressive $k$-means that summarizes a dataset with a constant-size Fourier-feature sketch and selects centroids by solving small per-group QUBOs with shallow QAOA circuits. The QFF sketch estimator is unbiased with mean-squared error $O(\varepsilon^2)$ for $B,S=Θ(\varepsilon^{-2})$, and the peak-qubit requirement $q_{\text{peak}}=\max\{D,\lceil \log_2 B\rceil + 1\}$ does not scale with the number of samples. A refinement step with elitist retention ensures non-increasing surrogate cost. In Qiskit Aer simulations (depth $p{=}1$), the method ran with $\le 9$ qubits on low-dimensional synthetic benchmarks and achieved competitive sum-of-squared errors relative to quantum baselines; runtimes are not directly comparable. On nine real datasets (up to $4.3\times 10^5$ points), the pipeline maintained constant peak-qubit usage in simulation. Under IBM noise models, accuracy was similar to the idealized setting. Overall, qc-kmeans offers a NISQ-oriented formulation with shallow, bounded-width circuits and competitive clustering quality in simulation.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。