Good morning Pennylane’s team.
Quick question: is there anything about Quantum Unsupervised ML algorithms? For example the quantum version of classical clustering algorithm? If someone knows about previous works with the implementation could post here?
Thanks in advance.
Hi @checcopo,
Indeed, you have the unsupervised learning approach, too, in quantum. The best example is Quantum K-means.
Hey @checcopo,
You can also check out this demo:
It’s got unsupervised QML 
. But there’s also a ton of research on this. A quick Google search shows a lot of hits!
Thank you @Christophe_Pere and @isaacdevlugt for answering. Probably I am a little bit confused about this topic. I saw on the web that it’s possible to make protocols to cluster data by using Qiskit as many examples are based on it. My question is, is it possible to use Pennylane and, in that case, train a PQC to cluster data? I mean, in Kmeans algorithm you assign k number of centroids randomly in your data-space and, according to a condition on the distance between each centroids and the data, you build clusters. Is it possible to update the parameters of a PQC to realize this process or it is simple no sense?
Thanks in advance, sorry for being so confused.
Hey @checcopo, this will most certainly be possible in PennyLane! Do you have examples in Qiskit that you’re familiar with that you can share? We have some great PennyLane-Qiskit features (see our plugin: PennyLane-Qiskit Plugin — PennyLane-Qiskit 0.35.1 documentation), but I’m 99.999% certain you can translate any Qiskit example to pure PennyLane
Good morning guys, sorry for having disappeared for a while. I would like to address this question again, with the difference that now I have understood much more and I have tried to implement a simple code to replicate the K-means with a quantum circuit. Moreover, I still have doubts and noob questions to you, so please try to understand my situation, I don’t want to bother you too much.
Ok let’s start:
In my Q-Kmeans, which I am going to present below, I have basically tried to build the Kmeans directly from examples found on Internet plus the Sklearn source code, but with the difference that I use a quantum circuit to estimate the distance between the datapoints of the dataset and the guessed, random picked, centroids. I use the SWAP test, and since the distance I get (by measuring the qml.expval(qml.PauliZ(wires=0)) is directly associated to the fidelity, I extract 1-fidelity(); then, I assign points to the clusters based on the minimum distance and I update the centroid’s position by also getting the “geometrical centre” of the points belonging to the cluster, by taking the mean of them.
Now, I get some results, but the point is: I will never get results which agree 100% to the classical ones, since I am mapping points in a 2-D plane to a spherical surface, (the qubit’s Bloch sphere), so points which are close to each other on a sphere (and consequently belonging to the same cluster) could be very far apart on a 2-D plane. This effect could be reduced by re-scaling everything and force the points to stay on a portion of the sphere, by using sklearn.preprocessing.MinMaxScaler((min_feature, max_feature), but this way we are neglecting the possible quantum advantage. So, I am a bit confused and I will ask you different questions:
- What could/should I do next;
- Do you have tutorials on that, since I haven’t found many;
- Is what I said correct in your opinion?
I have 2 more questions but are not urgent like the previous:
I have read a little description of the quantum algorithm which will suggest to use Grover to search for the state that is closer to a given centroid, and this way it would possible to scale the problem and get a real advantage thanks to Grover minimization search. I can’t understand how to integrate it in the code below, since I measure distances, I don’t have state and I don’t know a priori which is the closest state to a given centroid.
Second question, I have seen it is possible to set-up the same problem, but reformulating as a QUBO and use D-Wave to solve it: do you have/know some materials/tutorials where people have already done this on specific quantum Kmeans algorithm?
This is the code that is composed by a class which perform the Q-Kmeans and a testing script:
import numpy as np
import pennylane as qml
n_qubits = 3
shots = 2048
device = qml.device("default.qubit", wires=n_qubits)
@qml.qnode(device=device, shots=shots)
def DistanceEstimation(datapoint: np.array, centroid: np.array) -> list:
"""
Calculates the distance between each point in the dataset and the
centroid of the cluster we guess. This distance is related to the
fidelity between the quantum states representative of the centroid
and the datapoints.
:param datapoint: (np.array) The datapoints to embed in the circuit;
:param centroid: (np.array) The centroid of the cluster to embed in the circuit;
:return: measure: (list) List of distances between the datapoints and the centroids
after quantum circuit measurement of the expectation value along PauliX,
PaulyY and PauliZ operators respectively.
"""
qml.Hadamard(wires=0)
qml.RX(datapoint[0], wires=1)
qml.RY(datapoint[1], wires=1)
qml.RX(centroid[0], wires=2)
qml.RY(centroid[1], wires=2)
qml.CSWAP(wires=[0, 1, 2])
qml.Hadamard(wires=0)
measure = [qml.expval(qml.PauliX(wires=0)), qml.expval(qml.PauliY(wires=0)), qml.expval(qml.PauliZ(wires=0))]
return measure
class QuantumKmeans:
def __init__(self, seed: int, k: int, data: np.array) -> None:
"""
Class which implements the quantum version of the K-means algorithm for
clustering unlabelled data. This is a hybrid implementation, where the
distance between each point in the data and the centroid is calculated
by using a quantum circuit, in particular, getting the fidelity between
quantum states representing points and centroids.
Rather, the cluster assignment is done classically.
:param seed: (int) The random seed for reproducibility;
:param k: (int) The number of clusters we guess;
:param data: (np.array) The datapoints;
:return None.
"""
self.seed = seed
self.k = k
self.data = data
@staticmethod
def check_convergence(centroids_prev: float, centroids_current: float, threshold: float) -> np.array:
"""
Check convergence based on the distance between centroids.
:param centroids_prev: (float) Centroid at the previous iteration;
:param centroids_current: (float) Centroid at the current iteration;
:param threshold: (float) Threshold for convergence;
:return: (np.array) True if the convergence is achieved, False otherwise.
"""
distances = np.linalg.norm(centroids_prev - centroids_current, axis=1)
return np.all(distances < threshold)
@staticmethod
def initialize_centroids(data: np.array, k: int) -> np.array:
"""
Initialize the centroids by randomly selecting k centroids from the dataset.
:param data: (np.array) The datapoints;
:param k: (int) The number of clusters we guess
:return: centroids (np.array) The centroids;
"""
centroids_indices = np.random.choice(len(data), k, replace=False)
centroids = data[centroids_indices]
return centroids
@staticmethod
def calculate_distances(data: np.array, centroids: np.array) -> np.array:
"""
Call the distance calculation function and use the swap test to get the distances.
:param data: (np.array) The datapoints;
:param centroids: (np.array) Centroids the user has guessed;
:return: np.array(distances) (np.array) Distances' array.
"""
distances = []
for point in data:
point_distances = [1 - DistanceEstimation(datapoint=point, centroid=centroid)[2] for centroid in centroids]
distances.append(point_distances)
return np.array(distances)
@staticmethod
def assign_clusters(distances: np.array) -> int:
"""
Assign the current cluster label to the point which has the smaller distance between
the centroid from which the distance is calculated.
:param distances: (np.array) Distances between the points and centroids;
:return: np.argmin(distances, axis=1): (int) The index of the smallest distance.
"""
return np.argmin(distances, axis=1)
@staticmethod
def update(clusters: int, k: int, data: np.array) -> np.array:
"""
Update the cluster's centroid by calculating the geometrical cluster's centre by
taking the mean between all the points which belong to the cluster if there are
points inside the cluster, otherwise the centroid is taken randomly.
:param clusters: (int) The cluster's labels;
:param k: (int) The number of clusters we guess;
:param data: (np.array) The datapoints;
:return: centroids_arr: (np.array) The new centroids updated.
"""
centroids = []
for i in range(k):
cluster_point = data[clusters == i]
if len(cluster_point) > 0:
new_centroid = np.mean(cluster_point, axis=0)
else:
new_centroid = data[np.random.choice(len(data))]
centroids.append(new_centroid)
centroids_arr = np.array(centroids)
return centroids_arr
def kmeans_quantum(self, max_iter: int, threshold: float) -> tuple:
np.random.seed(self.seed)
"""
Perform k-means clustering with quantum circuit defined previously, and call
all the method listed inside this class.
:param max_iter: (int) The maximum number of iteration which the algorithm will run;
:param threshold: (float) The threshold to stop the algorithm;
:return: clusters, centroids: (tuple) The clusters and their centroids.
"""
centroids = self.initialize_centroids(self.data, self.k)
centroids_prev = centroids.copy()
for it in range(max_iter):
print(f"Iteration {it + 1}")
distances = self.calculate_distances(self.data, centroids)
clusters = self.assign_clusters(distances)
centroids = self.update(clusters, self.k, self.data)
if self.check_convergence(centroids_prev, centroids, threshold):
break
centroids_prev = centroids.copy()
return clusters, centroids
Here there are additional scripts which run the algo and plot also data clustered on the 2-D plane and on the Bloch sphere
from sklearn.datasets import load_iris
from sklearn.preprocessing import MinMaxScaler
import matplotlib.pyplot as plt
from sklearn.model_selection import train_test_split
from qkmeans_class import QuantumKmeans
import numpy as np
from sklearn.cluster import KMeans
from sklearn.metrics import adjusted_rand_score, rand_score
clusters = 4
seed = 9
iris = load_iris()
max_scaling = np.pi/4
min_scaling = -np.pi
X = iris.data
y = iris.target
scaler = MinMaxScaler(feature_range=(0, np.pi/2)) #the mentioned feature rescaling
X_scaled = scaler.fit_transform(X)
X = X_scaled
X_train, X_test, y_train, y_test = train_test_split(X, y, random_state=seed, test_size=0.05)
q_kmeans = QuantumKmeans(seed=seed, k=clusters, data=X_train)
c_kmeans = KMeans(n_clusters=clusters, n_init="auto", random_state=seed, tol=0.0001, max_iter=40) # call classical Sklearn method
c_kmeans.fit(X_train)
c_clusters = c_kmeans.labels_
c_centroids = c_kmeans.cluster_centers_
q_clusters, q_centroids = q_kmeans.kmeans_quantum(max_iter=40, threshold=0.0001) #call quantum method
print("Quantum clusters:\n", q_clusters)
print("Classical clusters:\n", c_clusters)
# This is made when there is no 1 to 1 correspondence between classical and quantum clusters
'''q_clusters[np.where(q_clusters == 2)] = 4
q_clusters[np.where(q_clusters == 3)] = 2
q_clusters[np.where(q_clusters == 1)] = 3
q_clusters[np.where(q_clusters == 4)] = 1'''
fig, axs = plt.subplots(nrows=1, ncols=2, figsize=(12,7))
for classical_cluster_label in set(c_clusters):
axs[0].scatter(X_train[c_clusters == classical_cluster_label, 0], X_train[c_clusters == classical_cluster_label, 1], s=50, label=f"Cluster {classical_cluster_label}", alpha=0.4)
axs[0].scatter(c_centroids[0, 0], c_centroids[0, 1], marker='x', s=200, c='tab:blue', linewidths=3)
axs[0].scatter(c_centroids[1, 0], c_centroids[1, 1], marker='x', s=200, c='tab:orange', linewidths=3)
axs[0].scatter(c_centroids[2, 0], c_centroids[2, 1], marker='x', s=200, c='tab:green', linewidths=3)
axs[0].scatter(c_centroids[3, 0], c_centroids[3, 1], marker='x', s=200, c='tab:red', linewidths=3)
axs[0].set_title("Classical Kmeans")
axs[0].legend()
for cluster_label in set(q_clusters):
axs[1].scatter(X_train[q_clusters == cluster_label, 0], X_train[q_clusters == cluster_label, 1], s=50, label=f"Cluster {cluster_label}", alpha=0.4)
axs[1].scatter(q_centroids[0, 0], q_centroids[0, 1], marker='+', s=200, c='tab:blue', linewidths=3)
axs[1].scatter(q_centroids[1, 0], q_centroids[1, 1], marker='+', s=200, c='tab:orange', linewidths=3)
axs[1].scatter(q_centroids[2, 0], q_centroids[2, 1], marker='+', s=200, c='tab:green', linewidths=3)
axs[1].scatter(q_centroids[3, 0], q_centroids[3, 1], marker='+', s=200, c='tab:red', linewidths=3)
axs[1].set_title("Q-Kmeans")
axs[1].legend()
plt.show()
#print("New quantum clusters:\n", q_clusters) #print new quantum clusters
# Metrics for "accuracy"
quantum_rs, classical_rs = adjusted_rand_score(y_train, q_clusters), adjusted_rand_score(y_train, c_clusters)
print("Adjusted RS score: QUANTUM", quantum_rs)
print("Adjusted RS score: CLASSICAL", classical_rs)
print("RS score: QUANTUM", rand_score(y_train, q_clusters))
print("RS score: CLASSICAL", rand_score(y_train, c_clusters))
Plot on the Bloch sphere using Qutip
import matplotlib.pyplot as plt
import qutip
import pennylane as qml
from qkmeans_class import shots, device
import numpy as np
from data_creation import X
from comparison import quantum_centroids, quantum_clusters
@qml.qnode(device=device, shots=shots)
def SingleQubitCircuit(datapoint: np.array) -> list:
"""
Create a circuit to plot the datapoints on te Bloch sphere.
:param datapoint: (np.array) The datapoints;
:return: measure: (list) The measured expectation values of the circuit along PauliX, PauliY, PauliZ operators.
"""
qml.RX(datapoint[0], wires=0)
qml.RY(datapoint[1], wires=0)
measure = [qml.expval(qml.PauliX(wires=0)), qml.expval(qml.PauliY(wires=0)), qml.expval(qml.PauliZ(wires=0))]
return measure
q_centroid = np.zeros(shape=[3, 3])
q_data = np.zeros(shape=[len(X), 3])
for c_index in range(len(q_centroid)):
q_centroid[c_index, :] = SingleQubitCircuit(datapoint=quantum_centroids[c_index])
for data_index in range(len(q_data)):
q_data[data_index, :] = SingleQubitCircuit(datapoint=X[data_index])
def PlotonSphere(q_data: np.array, q_centroid: np.array):
b = qutip.Bloch()
b.point_color = ["r", "b", "g"]
b.point_marker = ['o', 'o', 'o', 's', 's', 's']
b.add_points([q_data[np.where(quantum_clusters == 0), 0][0], q_data[np.where(quantum_clusters == 0), 1][0], q_data[np.where(quantum_clusters == 0), 2][0]], alpha=0.4)
b.add_points([q_data[np.where(quantum_clusters == 1), 0][0], q_data[np.where(quantum_clusters == 1), 1][0], q_data[np.where(quantum_clusters == 1), 2][0]], alpha=0.4)
b.add_points([q_data[np.where(quantum_clusters == 2), 0][0], q_data[np.where(quantum_clusters == 2), 1][0], q_data[np.where(quantum_clusters == 2), 2][0]], alpha=0.4)
#b.add_points([q_data[np.where(y == 0), 0][0], q_data[np.where(y == 0), 1][0], q_data[np.where(y == 0), 2][0]], alpha=0.4)
#b.add_points([q_data[np.where(y == 1), 0][0], q_data[np.where(y == 1), 1][0], q_data[np.where(y == 1), 2][0]], alpha=0.4)
#b.add_points([q_data[np.where(y == 2), 0][0], q_data[np.where(y == 2), 1][0], q_data[np.where(y == 2), 2][0]], alpha=0.4)
b.add_points([q_centroid[0, 0], q_centroid[0, 1], q_centroid[0, 2]])
b.add_points([q_centroid[1, 0], q_centroid[1, 1], q_centroid[1, 2]])
b.add_points([q_centroid[2, 0], q_centroid[2, 1], q_centroid[2, 2]])
b.show()
return plt.show(block=True)
PlotonSphere(q_data=q_data, q_centroid=q_centroid)
Hi @checcopo, your approach sounds very interesting!
Rescaling your data to fit between 0 and Pi can help avoid the problem you’re getting with datapoints being assigned to the wrong centroid. If there’s a quantum advantage (although I’m not sure that there will be one) this pre-processing shouldn’t affect it since you’re basically just performing a multiplication to all datapoints before starting.
We have several demos that perform rescaling in different ways depending on the problem. Our demo on Dropout in Quantum Neural Networks uses MinMaxScaler for the rescaling.
I’ve never seen Grover used for this but I guess it could be possible. Constructing the oracle might be tricky but if you’re able to construct one that marks states that are close to a specific centroid then I guess it could work. If you find any research on this topic feel free to share it here! And if you’re looking for some content on Oracles we have a Codebook module on them 
.
About QUBO problems we have this video and this demo. I haven’t seen them being used for K-means though.
I hope this helps you!
Hi,
Papers approaching K-means (or K-medoids) with a QUBO formulation:
- Bauckhage et al., 2019, A QUBO Formulation of the k-Medoids Problem
- DiAdamo et al., 2021, Practical Quantum K-Means Clustering: Performance Analysis and Applications in Energy Grid Classification
- Matsumoto et al., 2022, Distance-based clustering using QUBO formulations
- Zaiou et al., 2021, Balanced K-means using Quantum annealing
- Arthur & Date, 2021, Balanced k-means clustering on an adiabatic quantum computer
These are a good start to formulating the k-means problem with a QUBO formalism.
Best
1 Like
Thanks for sharing these resources @Christophe_Pere !! 
1 Like