{'fraction_non_alphanumeric': 0.027670980668218985, 'fraction_numerical': 0.007689391888233065, 'mean_word_length': 4.708809891808346, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 2, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Q-means using variational quantum feature embedding

This paper proposes a hybrid quantum-classical algorithm that learns a suitable quantum feature map that separates unlabelled data that is originally non linearly separable in the classical space using a Variational quantum feature map and q-means as a subroutine for unsupervised learning. The objective of the Variational circuit is to maximally separate the clusters in the quantum feature Hilbert space. First part of the circuit embeds the classical data into quantum states. Second part performs unsupervised learning on the quantum states in the quantum feature Hilbert space using the q-means quantum circuit. The output of the quantum circuit are characteristic cluster quantum states that represent a superposition of all quantum states belonging to a particular cluster. The final part of the quantum circuit performs measurements on the characteristic cluster quantum states to output the inter-cluster overlap based on fidelity. The output of the complete quantum circuit is used to compute the value of the cost function that is based on the Hilbert-Schmidt distance between the density matrices of the characteristic cluster quantum states. The gradient of the expectation value is used to optimize the parameters of the variational circuit to learn a better quantum feature map.


Introduction
The quantum algorithm Q-means [9] theorises an exponential speedup over the conventional K-means classical machine learning algorithm. However, it performs cluster assignment based on Euclidean distances, meaning that it would not work for non-linearly separable clusters (Fig. 1) in the original space, e.g. Concentric circles, Moons, Corners etc. Thus there is a need to implement feature mapping / kernel methods to deal with data in a higher dimensional space making data highly separable, giving better clustering results.
The idea of "quantum metric learning" discussed in [14] Quantum embedding provides an efficient way to train a variational circuit to find a hyperplane that separates the labelled data in the quantum Hilbert feature space. It uses arvind6599@gmail.com nikpuri@adobe.com the labels provided alongside the data to find an efficient quantum feature map to perform supervised learning. [17] The idea of encoding classical data into quantum states can be interpreted as a quantum feature map, which can help in finding the underlying the patterns within the unlabelled data. The variational circuit can be used to perform quantum computations that are classically intractable to obtain classically intractable feature maps in a high dimensional quantum feature Hilbert space.
After the data is embedded into the quantum Hilbert space, Q-means can be implemented on the quantum states to obtain characteristic cluster quantum states i.e. the quantum states that are superposition all the quantum states in a particular cluster. A cost function based on the cluster quantum states can be evaluated by measuring the overlap or fidelity between the characteristic cluster quantum states, ensuring high separation between clusters and low cluster scatter about the centroids. The optimization of the cost function is done using the gradient of the quantum circuit operations. This gradient is evaluated using the automatic differentiator discussed in [4]. Subsequently the quantum parameters for the variational feature map are updated for a better quantum feature map.
Dealing with non-trivial clustering tasks requires kernels that deal in higher dimensions where it is highly likely to be linearly separable.
NISQ Devices have been successfully used to implement Kernel methods in supervised learning [13,2,5,8,17,16,1,11] to obtain promising results using different type of classifiers such as kernel-based, 2 -margin SVM, minimum enclosing ball, K-Nearest Neighbours, distance based classifiers etc . [8] suggests two methods for supervised classification, first based on variational circuits to learn the function to approximate a classifier and second being a quantum SVM with a quantum feature map to implement a classically intractable kernel function for unique results. [15] discusses the application of approximating any teacher function given a labelled dataset by training a a Variational circuit to build a classifier. A quantum circuit can use a mixture of both ideas for unsupervised learning that learns a classically intractable quantum circuit for the input data.
The classical problem of Kernel K-means is an integer programming problem making it an NP-Hard problem. Other approaches such as adiabatic computing have been used as another method for K-means to find the best labelling possible for the encoded data, discussed in [3]. The problem is encoded into a Hamiltonian and the quantum state evolves with time towards the ground state of the problem Hamiltonian. The result is a quantum state that has the highest amplitude for the best possible labelling solution.
Finding an optimal solution to the k-means clustering problem for d-dimensional observations is an NP-Hard problem in euclidean space, even in the case of binary clustering. If we fix k and d values then the complexity of finding an optimal solution is O(n kd+1 ) The current work deals with supervised learning, which reduces the complexity and changes the nature of the problem. The purpose of the paper is to learn a quantum metric to find a pattern in the unlabelled data that consists of non-convex clusters.
This will eliminate the problem of finding a suitable kernel that works best for the dataset. As we know in the classical case there is no one fits all kernel that outputs optimal clustering solutions for all kinds of datasets. Leveraging the universal nature of QAOA in quantum computation, we try to use the high dimensionality of the Hilbert space to find an optimal quantum feature map that are classically intractable. Section 2 illustrates the methodology used to implement the algorithm. Section 3 illustrates the complete algorithm using pseudocode. Section 4 discusses the observations based on the simulations and inferences based on the results. Section 5 is a discussion regarding further possible applications of this classicalquantum hybrid algorithm. The final section of the paper is the conclusion.

Methodology
From the perspective of quantum computing, a quantum feature map x → |x corresponds to a quantum circuit U (x, θ) that takes classical data as input and performs feature encoding by applying quantum gates or unitary transformations on a ground or vacuum state |0...0 of a Hilbert space [17] F to produce quantum states: The choice of feature map is very important to the algorithm. This decides the nature of the kernel function K(x i , c j )= | x i |c j | 2 . First part of the quantum circuit involves encoding unlabelled classical data using quantum gates ( Fig. 2) that perform unitary operations on the initial quantum state based on quantum parameters θ and input data. A variational circuit is used to perform quantum feature encoding to learn the best possible quantum feature map U (x, θ) to obtain meaningful clustering results. Fig. 2: Quantum variational circuit implementing the quantum feature map [14] giving |x referred to as U (x, θ) for a two dimensional data point (x1,x2).
Advantage of using a Variational quantum feature map : U (x, θ) explores the best representation space to find non-trivial patterns underlying the data in a quantum feature Hilbert space. Also, the quantum feature Hilbert space dimensions are exponential with respect to qubits used in the initial state. This way high dimensional feature spaces can be efficiently implemented. The ansatz proposed in [14] also used in this paper is based on the QAOA framework. Repetitions of this ansatz can implement classically intractable feature maps based on the universality of QAOA in quantum computing [12]. Fixed state preparation If we chose a feature map such that K( x i , c j )= | x i |c j | 2 is too simple then the quantum circuit is unable to provide a quantum advantage. An example of a simple output from a feature map quantum circuit would be product states as it is easily simulated classically. Since quantum circuits are hard to simulate classically there does exist a list of quantum circuits that could do the required operations, providing a quantum advantage.
An example of such a quantum circuit is discussed in [8], which suggests a feature map on n-qubits as where H is the standard Hadamard gate and U φ(x) is : (2)

Q-means: Kernel estimation and labelling based on swap test
An unsupervised algorithm that performs K-means on quantum states to output centroid quantum states based on the unlabelled input data assumed to be stored in a Q-RAM [9]. The proposed algorithm makes use of q-means in a slightly different way. Q-means will be used a subroutine to output characteristic cluster This form of output is necessary because of the nature of the measurement to be made on the output of the q-means based subroutine.
Kernel estimation Perform the mapping: where K(x i , c j = | x i |c j | 2 and |K(x i , c j ) − K(x i , c j )| ≤ 1 Details of this step are illustrated in Kernel estimation section.
Cluster membership assignment The max value out of all the K register containing the kernel value is used to assign the cluster membership and generate labels for each data point [7].
Characteristic cluster quantum states On measuring the label register, the first qubit collapses to a superposition of data points belonging to the observes cluster label. This way we are able to obtain the characteristic cluster quantum Cluster centroid update Matrix multiplication of matrix X T and vector |χ j to obtain the state c t+1 j with error 2 , along with an estimation of | c t+1 j | with relative error 3 Once the convergence condition is satisfied for q-means subroutine, the |χ j are measured in the next section of the quantum circuit to evaluate the cost function.
Method of kernel estimation and Labelling As illustrated in Fig 2, computing of the kernel function starts by applying U (x, θ) and hadamard gate to the ancillary qubit : Now, swapping is done between the data point and the centroid qubits using ancilla as the control quibit to obtain the state.
Once again, Hadamard gate is applied to the accilary qubit to create interfernce between the swapped qubits to obtain the final state (ψ ± ij = |x i |c j ± |c j |x i ) : The probability of obtaining |0 when the third register is measured is, [9] Rewriting the final state by swapping the last two registers (|0 |ψ + → |ψ ij , 0 (G is a garbage state) we can summarize the whole algorithm as : A : |i |j |0 |0 |0 → |i |j √ p 0 |ψ ij , 0 + 1 − p 0 |G, 0 Now that we know how to apply the transformation A defined in Eqn. 10, [6] amplitude estimation can be used to create the desired state, which stores the kernel value based on Theorem : Theorem 1. Given algorithm A,for any positive integer P, the amplitude estimation algorithm outputsp 0 (0 ≤p 0 ≤ 1) such that : with probablity 8/π 2 . It uses exactly P iterations of the algorithm A. If p 0 = 0 thenp 0 = 0 with certainty, and if p 0 = 1 and P is even, thenp 0 = 1 with certainty. Fig. 5: left) A swap test to measure the overlap between the characteristic cluster quantum states |φ and |ψ right)Representation of 2 clusters |ψ and |φ on a bloch sphere [14] There are recent developments in amplitude estimation [18] that which requires lesser circuit depth focusing on implementation on NISQ devices by avoiding phase estimation. A simple final step of finding the maximum p 0 value to label (j * ) each data point, as the highest kernel value implies the greatest similarity to a particluar cluster's centroid quantum state. [7] can be used to find the lowestp 1 which is inversely proportional to the Kernel value as the amplitudes are normalized.
where j * is the label for the data point x i Advantage of using q-means as a subroutine for unsupervised learning : Data is readily available in the form of quantum states after the quantum feature map performs quantum embedding. Implying that the input does not not have to be interpreted as classical data using conventional feature encoding such as basis encoding or amplitude encoding, and has more freedom as it already lies in the high dimensional quantum feature Hilbert space. It is not restricted by a certain method of state preparation thus finding the local optimum kernel that performs well for the encoded data. The algorithm effectively uses quantum parallelism for distance calculation and labelling each data point, which is the primary reason for the exponential speed-up in it's complexity over the classical counterpart.
Limitations of the q-means subroutine Neither quantum simulators nor quantum computers large enough to test q-means are available currently as discussed in [9]. Although the results of Q-means are consistent with the results of δ-K means which is a noisier version of the conventional K-means. With advancement in quantum technology in the future q-means will be implementable on a quantum computer.

Measurement
The previous section outputs the set {|χ j : j ∈ [1 − k]}. This section which forms the final part of the quantum circuit (Fig. 4) consists of a measurement that computes the overlap between the characteristic cluster quantum states. This is used as a measure of the separation between the clusters. The swap test calculates the fidelity between the quantum states.

Cost function and θ update
All the measurements representing the expectation value of the observable are summed up to form a cost C(θ) function representing the total inter-cluster overlap in the quantum feature Hilbert space.
This cost function is similar to the Hilbert Schmidt distance (D hs ) used in [14]. D hs is used to quantify the underlying distance between the clusters, which depends on the overlap between the quantum states embedded in each cluster. If k=2 and |a is from cluster A and |b belongs to cluster B then D hs is given by : and the respective cost function is simply C = 1 -D hs (A, B) Since q-means uses data in superposition to obtain an exponential speedup and lesser qubit usage, it also leads to restrictions in the nature of the cost function. Restrictions such as inability to calculate intra-cluster scatter as | χ 0 |χ 0 | 2 = 1. The resultant cost function thus reformulates the objective as minimizing the overlap between the clusters.
The quantum parameter θ is updated using the gradient of the C(θ) which is computed using Pennylane automatic differentiator [4]. The RMSPropOptimizer along with the QAOAEmbedding framework was used to run simulation illustrated in Fig 5.

Algorithm
The psuedocode illustrates the framework for the Variational q-means based on all the steps that were described in detail in the previous sections.

Algorithm 1: Variational Quantum Kernel K-means
Input: Random initialization of θ for the Variational quantum circuit. Choose hyperparameter step size for the Pennylane RSMPropOptimizer and error parameters 1, 2, 3, 4,.The data matrix X ∈ R n×d stored in a QRAM. Initialize K centroids c 0 0 , c 0 1 , ...c 0 K using K-means ++ method, and store it in the QRAM. K ancilla qubits each initialized to |0 to compute fidelity. Output: Overlap cost function and trained parameter θ θ θ representing the learnt quantum feature map U (x, θ θ θ) 1 initial iteration t=0 Quantum computation 2 Part 1: Variational Quantum Feature Map U(x,θ) Feature embedding |x = U (x, θ) |00..0 Create a superposition state Using an oracle to form a superposition state based on the index of the data point.
where, K(xi, cj)= | xi|cj | 2 . Cluster Assignment Characteristic cluster quantum state and Centroid estimation Label quantum register is measured to obtain state χ j = 1 √ |C j | x i ∈C J |i with probability All inter-cluster overlaps are measured using swap test between each pair of distinct characteristic cluster quantum state. Classical computation 7 Compute cost function C(θ) based on the output of the quantum circuit.

Results from simulations
The simulations (Fig 6) to compute overlap cost function are implemented using Pennylane's QAOA embedding framework 1 .All the datasets are pre-processed using Sklearn before quantum embedding. Currently no quantum simulators are available to test q-means, so cluster datasets with labels were used as inputs for the quantum embedding circuit to train the quantum partameters.  Observations In Fig 6, the blobs dataset is very well separated in the original space, due to which the algorithm did not take many iterations to converge. Whereas in the case of non-linearly separable datasets, the algorithm took more number of iterations to converge. The quantum parameters had to be trained to find the pattern that is non-trivial in the classical space.
Step size = 0.1 is observed to perform better than the other step sizes.

Discussion
Evaluating clustering performance using quantum metrics Clustering performance of an unsupervised learning can be evaluated using the overlap measurement to quantify the separation between the clusters in the quantum Hilbert space. The output labeled data can be mapped using quantum embedding and learn a good feature mapping, then score it based on the measurement -based distance between the density matrices using -1 or -2 norms.
Interpretation of the quantum parameters The trained parameter θ represents the representation space learnt by the algorithm for the embedded dataset. The final quantum feature map can be used to interpret underlying pattern in the dataset.

Conclusion
Despite a complete understanding of the idea of clustering discussed in [10], this paper aims to create maximal separation between dissimilar quantum states to perform clustering. The algorithm learns a quantum feature map by training quantum parameters based on labels obtained from the q-means unsupervised learning subroutine. The repetitive approach of performing unsupervised learning followed by adaptively training the feature map aims at learning the best representation of the data in the quantum feature Hilbert space. By explicitly implementing the kernel estimation, we are able to explore more feature spaces that are better suited for the embedded dataset. Since the current existing simulators cannot be used to implement the complete algorithm, the quantum advantage is yet to be experimentally shown.