全文链接：https:///?p=37821
分析师：Yifan Zhang
量子计算在近期已然成为一个频繁出现的热门概念。尽管它在大众认知以及互联网社区中备受瞩目，热度极高，然而就其实际能力而言，当前仍然存在诸多局限（点击文末“阅读原文”获取完整代码数据）。
量子计算作为一个全新的领域，带来了相较于传统经典计算模式的重大范式转变。在量子计算的体系中，传统的 0 或 1 的经典比特被一种具有特定概率值的量子比特所替代。
由于量子比特具备特殊的量子态性质，所以每当对其进行测量时，它会依据一定的概率呈现出 0 或 1 的状态。例如，当一个量子比特处于 0.85 : 0.15 这样的状态时，那么我们大致可以预估它有 85% 的可能性在测量时结果为零，而有 15% 的可能性测量结果为 1。
虽然量子计算的发展道路依旧漫长，但机器学习无疑是其极具发展前景的潜在应用方向。以下几个示例能够帮助我们初步了解量子计算所具备的计算能力：
其一，一个量子比特能够同时包含 0 和 1 这两种状态。相应地，两个量子比特就可以保存四种值状态，即 00、01、10 和 11；三个量子比特则能够达到八种状态，以此类推。
其二，从理论上来说，n 个量子比特所包含的信息量等同于 2n 个经典比特。
此外，量子电路所具有的流体概率性质或许能够为深度学习带来独特的优势。要知道，深度学习本身就从网络中的概率流以及信息转换过程中获益匪浅。
当前，量子机器学习这一概念正逐渐流行起来。例如，TensorFlow 作为谷歌公司著名的深度学习框架，近期也推出了其量子版本 ——“TensorFlow Quantum”。
本文着重探讨量子版本的 k – means 算法（Q – means），旨在借助量子计算的优势提升聚类算法的性能，通过 Qiskit 模拟器来近似计算距离，进而为无监督机器学习提供全新的解决方案。文中详细阐述了 Q – means 算法的原理以及具体的实现步骤，并且将其与传统的 k – means 算法进行了对比，实验结果充分展示了 Q – means 算法的有效性以及潜在应用价值。
引言
随着信息技术发展，数据规模与复杂性增加，传统机器学习算法处理大规模数据面临挑战。量子计算具强大并行计算能力与潜在指数级加速优势，为解决复杂机器学习问题提供新思路。k-means 算法是经典无监督机器学习算法，广泛用于数据聚类等领域，但传统算法处理大规模数据效率低且易陷局部最优。Q-means 利用量子计算优势克服传统算法问题。
讲解视频
k-means 算法概述
（一）数据准备
从 “.csv” 文件读取数据，转换分类数据为数字，将数据框转为 numpy 矩阵。
df["Class"] = pd.Categorical(df["Class"])
df["Class"] = df["Class"].cat.codes
data = df.values[:, 0:2]
category = df.values[:, 2]
（二）参数设置
-
设置聚类数
k = 3，确定训练数据数n与数据特征数c。 -
生成随机中心，用均值和标准差确保代表整个数据集。
mean = np.mean(data, axis = 0)
std = np.std(data, axis = 0)
centers = np.random.randn(k,c)*std + mean
-
提供静态数据测试。
centers = np.array([[-0.25, 0.2], [0, -0.1], [0.25, 0.35]])
（三）绘制初始数据和中心
用不同颜色表示不同类别，绘制数据点与中心。
colors=['green', 'blue', 'black']
for i in range(n):
plt.scatter(data[i, 0], data[i,1], s=7, color = colors[int(category[i])])
plt.scatter(centers[:,0], centers[:,1], marker='*', c='g', s=150)
（四）迭代更新中心
-
初始化旧中心为全零矩阵，新中心为初始中心深拷贝。
-
计算数据点到每个中心距离。
-
将数据点分配到最近中心。
-
计算每个簇新中心，即该簇数据点均值。
-
计算新中心与旧中心误差，当误差为零停止迭代。
点击标题查阅往期内容
左右滑动查看更多
Q-means 算法原理
Q – means 算法是一种用于聚类的量子算法，是经典 k – means 算法的量子版本。以下是其详细原理介绍：
1. 总体流程
Q – means 算法在高层次上遵循与经典 k – means 算法相似的步骤，包括初始化中心点、将数据点分配到最近的中心点所属的簇以及更新中心点等操作。但在具体实现中，使用了量子子例程进行距离估计、寻找元素中的最小值、通过矩阵乘法获取作为量子态的新中心点以及进行高效的量子态层析成像（tomography）来获取经典的中心点描述。
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函数计算数据点到多个中心距离。
-
计算相位和角度。
-
创建量子寄存器和经典寄存器，构建量子电路。
qreg = QuantumRegister(3, 'qreg')
creg = ClassicalRegister(1, 'creg')
qc = QuantumCircuit(qreg, creg, name='qc')
backend = Aer.get_backend('qasm_simulator')
-
通过量子门操作实现编码和距离计算。
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])
-
测量辅助量子比特，统计结果得到距离。
（三）迭代更新中心
与 k-means 类似，不断迭代更新中心，直到中心估计值不变。
centers_old = np.zeros(centers.shape)
centers_new = deepcopy(centers)
data.shape
clusters = 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)
（三）确定数据点类别
-
量子算法确定类别
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))]
-
经典欧氏距离计算确定类别
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:///pdf/1812.03584.pdf
分析师
在此对Yifan Zhang对本文所作的贡献表示诚挚感谢，她完成了信息管理与信息系统专业的学位。擅长软件Java语言、SPSS，擅长领域包括数据采集、数据预处理、MySQL等，同时还擅长Python、Matlab仿真、视觉处理、神经网络、数据分析。
本文中分析的数据、代码分享到会员群，扫描下面二维码即可加群！
资料获取