（四）迭代更新中心

1. 初始化旧中心为全零矩阵，新中心为初始中心深拷贝。
2. 计算数据点到每个中心距离。
3. 将数据点分配到最近中心。
4. 计算每个簇新中心，即该簇数据点均值。
5. 计算新中心与旧中心误差，当误差为零停止迭代。

---

---

Q-means 算法原理

Q – means 算法是一种用于聚类的量子算法，是经典 k – means 算法的量子版本。以下是其详细原理介绍：

2. 距离估计（Centroid distance estimation）

• 目的：估计数据点与簇之间的平方距离。
• 方法
  • 利用量子过程进行估计，可以使用如 Swap Test 或 Frobenius 距离估计程序。对于 Q – means 算法，由于需要处理不同范数的向量间的距离或内积估计，首先估计对应于归一化向量的量子态之间的内积，然后将估计值乘以向量范数的乘积来得到未归一化向量的内积估计值，类似地可用于平方距离估计。
  • 具体地，假设有数据矩阵 V（是一个 N×d 的矩阵，N 表示数据点数量，d 表示数据维度）和质心矩阵 C（是一个 k×d 的矩阵，k 表示簇的数量）存储在 QRAM 中，且已知向量的范数以及某些特定的酉变换（unitaries）可以在时间 O (log (N×d)) 内执行，对于任意大于 0 的 Δ 和大于 0 的 epsilon1，存在一个量子算法执行特定映射，使得 | d2 (vi, cj) 的估计值 – d2 (vi, cj)| ≤ epsilon1 的概率至少为 1 – Δ，运行时间为 O (k×(eta /epsilon1)×log (1 / Δ))，其中 eta = maxi (||vi|| 的平方)，||vi|| 表示向量 vi 的范数。

3. 簇分配（Cluster assignment）

• 目的：根据距离估计结果，将每个数据点分配到最近的质心所属的簇。
• 方法
  • 在步骤 1 结束时，已经在不同寄存器中相干地估计了数据集中每个点与 k 个质心之间的平方距离。由于平方是单调函数，不需要计算距离的平方根即可找到距离每个数据点最近的质心索引。
  • 通过一个量子电路（Circuit for finding the minimum）来实现找到最小距离对应的索引。给定 k 个不同的 log p – bit 寄存器，存在一个量子电路可以在时间 O (k×log p) 内找到这些寄存器中值的最小值索引。

4. 质心状态创建（Centroid states creation）

• 目的：根据簇分配结果，计算新的质心状态。
• 方法
  • 首先定义特征向量 chi_j_t（是一个 N 维向量），它表示在迭代 t 时簇 j 的特征向量（经过归一化）。根据 k – means 算法更新质心的规则 c_j_(t + 1) =（1 / |C_j_t|）×sum (i 属于 C_j_t) vi，可以得到 c_j_(t + 1) = V 的转置 ×chi_j_t。
  • 通过测量相关寄存器，可以从状态 x_j_t 中采样，然后利用量子矩阵乘法 V 的转置来恢复近似的质心状态 c_j_(t + 1)，同时可以得到质心范数的估计值，误差分别为 epsilon2 和 epsilon3。

5. 质心更新（Centroid update）

• 目的：将量子态表示的质心转换为经典描述的质心，以便进行下一次迭代。
• 方法
  • 对步骤 3 中创建的质心状态 c_j_(t + 1) 应用向量态层析成像算法（vector state tomography）。对于每个 j 属于 k，需要多次调用创建 c_j_(t + 1) 的酉变换来实现 ||c_j – c_j 的估计值 || < epsilon4，总共需要调用 O ((k×(log k)×d×(log d)) / (epsilon4 的平方)) 次。
  • 向量态层析成像给出单位范数质心的经典估计值，误差在 epsilon4 范围内。结合质心范数的估计值（相对误差为 epsilon3），可以恢复质心向量，并且满足 ||c_j 的估计值 – c_j|| ≤sqrt (eta)×(epsilon3 + epsilon4)=epsilon_centroids，其中 eta 的定义同上。

（一）数据准备和参数设置

与 k-means 类似，读取数据、转换数据、设置参数。

（二）定义距离计算函数
point_centroid_distances函数计算数据点到多个中心距离。

1. 计算相位和角度。
2. 创建量子寄存器和经典寄存器，构建量子电路。

qreg = QuantumRegister(3, 'qreg')creg = ClassicalRegister(1, 'creg')qc = QuantumCircuit(qreg, creg, name='qc')backend = Aer.get_backend('qasm_simulator')

1. 通过量子门操作实现编码和距离计算。

qc.h(qreg[2])qc.u3(theta_list[0], phi_list[0], 0, qreg[0])           qc.u3(theta_list[i], phi_list[i], 0, qreg[1]) qc.cswap(qreg[2], qreg[0], qreg[1])qc.h(qreg[2])qc.measure(qreg[2], creg[0])

1. 测量辅助量子比特，统计结果得到距离。

（三）迭代更新中心
与 k-means 类似，不断迭代更新中心，直到中心估计值不变。

centers_old = np.zeros(centers.shape)centers_new = deepcopy(centers)data.shapeclusters = np.zeros(n)distances = np.zeros((n,k))error = np.linalg.norm(centers_new - centers_old)

四、实验结果与分析

（一）绘制数据和中心
展示算法聚类结果。

for i in range(n):    plt.scatter(data[i, 0], data[i,1], s=7, color = colors[int(category[i])])plt.scatter(centers_new[:,0], centers_new[:,1], marker='*', c='g', s=150)

量子聚类算法可视化及电路实现

数据准备与特征编码

（一）数据读取与预处理
从 “.csv” 文件读数据，转换分类数据为数字编码，转为 numpy 矩阵。

（二）定义特征编码函数
encode_feature函数将数据特征值映射为角度和相位值。

def encode_feature(x):    return ((x + 1) * pi / 2)

（三）确定数据点和质心
设置数据点坐标，定义质心数组，计算相位和角度值。

三、量子寄存器与电路构建

（一）创建量子寄存器
根据需求创建三个量子寄存器。

qreg_input = QuantumRegister(k, name='qreg_input')qreg_centroid = QuantumRegister(k, name='qreg_centroid')qreg_psi = QuantumRegister(k, name='qreg_psi')

（二）创建经典寄存器
创建经典寄存器存储测量结果。

creg = ClassicalRegister(k, 'creg')

（三）构建量子电路
使用寄存器构建量子电路。

（二）量子电路可视化
绘制量子电路，设置背景颜色和样式。

style = {'backgroundcolor': '#DFEAEC', 'showindex': False, 'displaycolor': {        'id': 'red', 'meas':'#0066DA', 'h': '#00DAA7', 'u3': '#EFFF1B'} }qc.draw(output='mpl', style=style, reverse_bits= False,filename="d2.png",scale=1.2)

（三）确定数据点类别

1. 量子算法确定类别

results_list = []for i in range(1, 4):    qc.h(qreg[2])    qc.u3(theta_list[0], phi_list[0], 0, qreg[0])               qc.u3(theta_list[i], phi_list[i], 0, qreg[1])     qc.cswap(qreg[2], qreg[0], qreg[1])    qc.h(qreg[2])    qc.measure(qreg[2], creg[0])    job = execute(qc, backend=backend, shots=1024)    result = job.result().get_counts(qc)    results_list.append(result['1'])class_list = ['Green', 'Blue', 'Black']quantum_p_class = class_list[results_list.index(min(results_list))]

1. 经典欧氏距离计算确定类别

distances_list = [((x_p - i[0])**2 + (y_p - i[1])**2)**0.5 for i in [(xgc, ygc), (xbc, ybc), (xkc, ykc)]]classical_p_class = class_list[distances_list.index(min(distances_list))]

结论

本文介绍量子聚类算法可视化与电路构建，展示量子计算在数据分类潜力。但量子计算处发展阶段，有技术挑战。

参考文献

Kerenidis et al. q-means: A quantum algorithm for unsupervised machine learning, 2018 https://arxiv.org/pdf/1812.03584.pdf

---

关于分析师

在此对Yifan Zhang对本文所作的贡献表示诚挚感谢，她完成了信息管理与信息系统专业的学位。擅长软件Java语言、SPSS，擅长领域包括数据采集、数据预处理、MySQL等，同时还擅长Python、Matlab仿真、视觉处理、神经网络、数据分析。