<jupyter_start><jupyter_text>Quantum enhanced support vector machineAuthors: *<NAME>, <NAME>, <NAME>*  In this notebook, we will explore a quantum algorithm developped to enhance a machine learning (ML) algorithm. In particular, we will study the Quantum enhanced support vector machine, introduced by the scientific staff of IBM in Ref.[1](https://arxiv.org/pdf/1804.11326.pdf).  Brief overview of machine learning Machine learning algorithms are mainly divided in two categories: supervised and unsupervised algorithms.   In the case of **supervised learning**, the training set is given with labels. For example, in the MNIST dataset, the training set are hanwritten numbers and the labels are the numbers. The goal of supervised algorithm is to learn to predict these labels and to be able to generalize to unlabelled data of the same kind. After the training on MNIST, the algorithm should be able predict that an image of a 5 is actually labelled by a 5. There many examples of supersvised learning such as support vector machine, random forest, deep neural networks, etc.In the case of **unsupervised learning**, the training set is given without labels. The goal of the algorithm is to find some structure in the data. One example of such algorithms is the k-means clustering. There, the user specifies the number of clusters he wants to find in the data and the algorithm finds automatically the different clusters. Another example is the T-SNE algotrithm, widely used for data visualisation. This algorithm takes data in a high-dimensional space and tries to find some structure in the data, that can be visualized by the user in 2D or 3D. As an example, we show here the application of the t-SNE algorithm on the MNIST dataset. Even without labels, the different numbers separate nicley in different clusters. We will now focus on a specific supervised learning algorithm, the suppert vector machine. But, let us first introduce the data set we want to classify  Breast Cancer dataset We want to classfify the [Breast Cancer Wisconsin (Diagnostic) Data Set ](https://archive.ics.uci.edu/ml/datasets/Breast+Cancer+Wisconsin+(Diagnostic)). The dataset consists in 569 training examples, with each 32 attributes such as the perimeter, the texture, the area, etc. The diagnosis of these data can be malginant or benign. For the sake of simplicity, which will be particularly relevant for the quantum enhanced version of the algorithm, we do a dimensional reduction of our data from 32 attributes to 2, with the help of a [principal component analysis](https://es.wikipedia.org/wiki/An%C3%A1lisis_de_componentes_principales) (PCA). Such unsupervised algorithm finds the principal axes of the data with a singular value decomposition.<jupyter_code>import numpy as np
from dataset import breast_cancer
from sklearn.datasets.samples_generator import make_blobs
from qiskit.aqua.utils import split_dataset_to_data_and_labels 
from sklearn import svm
from utils import svm_utils 
from matplotlib import pyplot as plt
%matplotlib inline
%load_ext autoreload
%autoreload 2
n = 2 # number of principal components kept
training_dataset_size = 20
testing_dataset_size = 10

sample_Total, training_input, test_input, class_labels = breast_cancer(training_dataset_size, testing_dataset_size, n)

data_train, _ = split_dataset_to_data_and_labels(training_input)
data_test, _ = split_dataset_to_data_and_labels(test_input)<jupyter_output><empty_output><jupyter_text>Linear Support vector machine We first emphasize that there two types of data that can be classified by these algorithms: linearly separable datasets and non linearly separable datasets. Our dataset is clearly not linearly separable. We show two examples in the different classes here below.<jupyter_code># We use the function of scikit learn to generate linearly separable blobs
centers = [(2.5,0),(0,2.5)]
x, y = make_blobs(n_samples=100, centers=centers, n_features=2,random_state=0,cluster_std=0.5)


fig,ax=plt.subplots(1,2,figsize=(10,5))


ax[0].scatter(data_train[0][:,0],data_train[0][:,1],c=data_train[1])
ax[0].set_title('Breast Cancer dataset');

ax[1].scatter(x[:,0],x[:,1],c=y)
ax[1].set_title('Blobs linearly separable');<jupyter_output><empty_output><jupyter_text>Let us first focus on the linearly separable dataset. We would first like to separate linearly the data set. However, there are many ways separating linearly this dataset,as one can see in the image below. Ideally, the separating line should be chosen such that it can generalize properly.   Linear Support vector machine: Hard margins and soft margins  The support vector machine algorithm tries to find the parameters $w$ and $b$ such that the data with labels $y=1$ satisfy $w\,x+b>1$, and the data $y=-1$ satisfy $w\,x+b1$. This problem corresponds to the optimization of a quadratic problem with linear constraints $\min \limits_{w,b}\vert \vert w\vert \vert^2 \text{ such that } y_i (w \, x_i+b)\geq 1, i=1...N$and has therefore a unique extremum. The latter can be found with a gradient-descent technique.In some of the problems, one would prefer to have a control on the margins by giving a weight to every point of the dataset, which would be an hyper parameter. This can done by considering the following problem$\min \limits_{w,b,\xi_i>0}\vert \vert w\vert \vert^2+C\sum_{i=1}^{N}\xi_i \text{ such that } y_i (w x_i+b)\geq 1-\xi_i, i=1...N$For $C=\infty$, we recover the hard margin case. The value of C allows one to control the size of the margins.Combining the inequalities $\xi\geq 0$ and $y_i (w x_i+b)\geq 1-\xi_i$, the minization problem can be rewritten as$\min \limits_{w,b,\xi_i>0}\vert \vert w\vert \vert^2+C\sum_{i=1}^{N}\max(0,1-y_i (w x_i+b))$The second term of this inequality is the so called Hinge Loss and the SVM problem can be seen as a minization of the Hing Loss with a $L_2$ regularization of the weigths. We finally notice that problem has still a unique minimum.  Support vector machine and dual problem One can show that the optimization problem of the SVM is equivalent to the minization its dual formulation. For example, in the case of the soft margins, the dual problem takes the form$\max \limits_{\{\alpha_i\}}\sum_i-\frac{1}{2}\sum_{j,k}\alpha_j\alpha_k y_j y_k (x_j^Tx_k) \text{ with the constraints } 0 \leq \alpha_i \leq C \text{ and } \sum_i \alpha_i y_i=0$One of the advantages of this formulation is that oit only involves the saclar products $ x_j^T x_k$. This is a crucial point when we will go to kernel methods.   Support vector machine with Kernel  As we have already seen, the data are not always linearly separable. A simple trick to be able to still use a linear classifier are the kernel methods, as sketched in the Figure above. For example, this one-dimensional dataset is not linearly separable. However, when embedding them in the two-dimensional space with the map $\Phi: x \rightarrow (x,x^2)$. The datas become again linearly separable. In the ducal formulation, one only has to compute the scalar product $ x_j^T x_k$, which after the embedding takes the form $ \Phi(x_j^T) \Phi(x_k)$. The pretty nice point of using the kernel trick is that one does not have to do the embedding if one knows the value of the the scalar product. An example is the gaussian kernels where the data are embedded in a high dimensional space and mapped to gaussians, where the scalar product can be computed analitcally.   Hands-on session on support vector machineBefore going to quantum case, we will implement the both the linear and kernel SVM algorihms for the  breast cancer dataset. We first have a look at our data set<jupyter_code>plt.scatter(data_train[0][:,0],data_train[0][:,1],c=data_train[1])
plt.title('Breast Cancer dataset');<jupyter_output><empty_output><jupyter_text>We then define a linear SVM classifier and train it on the data set.<jupyter_code>model= svm.LinearSVC()
model.fit(data_train[0], data_train[1])
accuracy_train = model.score(data_train[0], data_train[1])
accuracy_test = model.score(data_test[0], data_test[1])


X0, X1 = data_train[0][:, 0], data_train[0][:, 1]
xx, yy = svm_utils.make_meshgrid(X0, X1)
Z = model.predict(np.c_[xx.ravel(), yy.ravel()])
Z = Z.reshape(xx.shape)

fig,ax=plt.subplots(1,2,figsize=(15,5))
ax[0].contourf(xx, yy, Z, cmap=plt.cm.coolwarm)
ax[0].scatter(data_train[0][:,0], data_train[0][:,1], c=data_train[1])
ax[0].set_title('Accuracy on the training set: '+str(accuracy_train));

ax[1].contourf(xx, yy, Z, cmap=plt.cm.coolwarm)
ax[1].scatter(data_test[0][:,0], data_test[0][:,1], c=data_test[1])
ax[1].set_title('Accuracy on the test set: '+str(accuracy_test));<jupyter_output><empty_output><jupyter_text>The background indicates the decision function for the SVM algorithm. As an exercise, you can change the datasets to the linearly separable blobs and/or play with the value C, that change the margins. Remember, $C=\infty$ is the hard margin case. We now implement a SVM with gaussian kernel<jupyter_code>clf = svm.SVC(gamma = 'scale')
clf.fit(data_train[0], data_train[1]);
accuracy_train = clf.score(data_train[0], data_train[1])
accuracy_test = clf.score(data_test[0], data_test[1])


X0, X1 = data_train[0][:, 0], data_train[0][:, 1]
xx, yy = svm_utils.make_meshgrid(X0, X1)
Z = clf.predict(np.c_[xx.ravel(), yy.ravel()])
Z = Z.reshape(xx.shape)

fig,ax=plt.subplots(1,2,figsize=(15,5))
ax[0].contourf(xx, yy, Z, cmap=plt.cm.coolwarm)
ax[0].scatter(data_train[0][:,0], data_train[0][:,1], c=data_train[1])
ax[0].set_title('Accuracy on the training set: '+str(accuracy_train));

ax[1].contourf(xx, yy, Z, cmap=plt.cm.coolwarm)
ax[1].scatter(data_test[0][:,0], data_test[0][:,1], c=data_test[1])
ax[1].set_title('Accuracy on the test set: '+str(accuracy_test));<jupyter_output><empty_output><jupyter_text>First steps in QiskitWe give a very brief introduction into Qiskit, which is a package to create quantum circuits and execute them on a local simulator or that can also be sent to IBMQ, a real quantum computer.So let's create a first quantum circuit, with a classical register.<jupyter_code>import qiskit as qk

# Creating Qubits
q = qk.QuantumRegister(2)
# Creating Classical Bits
c = qk.ClassicalRegister(2)<jupyter_output><empty_output><jupyter_text>Define and print empty circuitSo far we only have an empty quantum circuit with 2 qubits (`q0_0` and `q0_1`) and 2 classical registers (`c0_0` and `c0_1`).<jupyter_code>circuit = qk.QuantumCircuit(q, c)
print(circuit)<jupyter_output><empty_output><jupyter_text>Add gates to the qubitsAs an example we add a Hadamard gate $H$ to the 0-th qubit and a Controlled-Not (also called Controlled-X, CNOT or CX) gate to the circuit, where the control qubit is qubit 0 and the target qubit is qubit 1.**What do these qubits do?**The initial state of `q0_0` is $\vert 0 \rangle_0$ and we first apply a Hadamard on it $H \vert 0 \rangle_0 = \frac{1}{\sqrt{2}} (\vert 0 \rangle_0 + \vert 1 \rangle_0)$.At this point `q0_1` is still in the ground state $\vert 0 \rangle_1$ and the state of the whole circuit can be described as $\frac{1}{\sqrt{2}} (\vert 0 \rangle_0 + \vert 1 \rangle_0) \otimes \vert 0 \rangle_1$The CNOT gate now applies a $X$ gate to `q0_1` if `q0_0` is in the $\vert 1 \rangle$ state otherwise nothing happens to `q0_1` which is the same as applying the unity matrix $\mathbb{1}$. This can be fromally writen as $\vert 0 \rangle \langle 0 \vert_0 \otimes \mathbb{1}_1 + \vert 1 \rangle \langle 1 \vert_0 \otimes X_1$.The final state after these two gates is $\frac{1}{\sqrt{2}} (\vert 00 \rangle_{0,1} + \vert 11 \rangle_{0,1})$<jupyter_code># Initialize empty circuit
circuit = qk.QuantumCircuit(q, c)
# Hadamard Gate on the first Qubit
circuit.h(q[0])
# CNOT Gate on the first and second Qubits
circuit.cx(q[0], q[1])
# Measuring the Qubits
circuit.measure(q, c)
print (circuit)<jupyter_output><empty_output><jupyter_text>Run the circuit on the quantum simulatorIn a next step we run this circuit on a quantum simulator.The measurements that we added before at the end of the circuit will measure if the single qubits are either in the state $\vert 0 \rangle$ or $\vert 1 \rangle$ by returning writing the classical bits 0 or 1 into the classical register.<jupyter_code># Using Qiskit Aer's Qasm Simulator: Define where do you want to run the simulation.
simulator = qk.BasicAer.get_backend('qasm_simulator')

# Simulating the circuit using the simulator to get the result
job = qk.execute(circuit, simulator, shots=100)
result = job.result()

# Getting the aggregated binary outcomes of the circuit.
counts = result.get_counts(circuit)
print (counts)<jupyter_output><empty_output><jupyter_text>Quantum Classification Remember what is the idea of a classical SVM. We have a set of points that are in either one group or another and we want to find a line that separates these two groups. This line can be linear, but it can also be much more complex, which can be achieved by the use of Kernels.**So what will we need in the case of a quantum computer?**- 1st we will have to translate the classical data point $\vec{x}$ into a quantum datapoint $\vert \Phi{(\vec{x})} \rangle$. This can be achieved by a circuit $\mathcal{U}_{\Phi(\vec{x})} \vert 0 \rangle $. Where $\Phi()$ could be any classical function applied on the classical data $\vec{x}$.- 2nd we need a parameterized quantum circuit $W( \theta )$ that processes the data in a way that in the end we...- 3rd can apply a measurement that returns a classical value $-1$ or $1$ for each classical input $\vec{x}$ that indentifies the label of the classical data.**The most general ansatz**Following these steps we can define an ansatz for this kind of problem which is $W(\theta) \mathcal{U}_{\Phi}(\vec{x}) \vert 0 \rangle$.These kind of ansatz are called quantum variational circuits.  Quantum SVMIn the case of a quantum SVM we will only used the quantum feature maps $\mathcal{U}_{\Phi(\vec{x})}$ to translate the classical data into quantum states and build the Kernel of the SVM out of these quantum states. After calculating the Kernel matrix on the quantum computer we can train the Quantum SVM the same way as the classical SVM.**Defining the Quantum Kernel**The idea of the quantum kernel is exactly the same as in the classical case. We take the inner product $K(\vec{x}, \vec{z}) = \vert \langle \Phi (\vec{x}) \vert \Phi(\vec{z}) \rangle \vert^2 = \langle 0^n \vert \mathcal{U}_{\Phi(\vec{x})}^{t} \mathcal{U}_{\Phi(\vec{z})} \vert 0^n \rangle$, but now with the quantum feature maps $\mathcal{U}_{\Phi(\vec{x})}$. The idea is that if we choose a quantum feature maps that is not easy to simulate with a classical computer we might obtain a quantum advantage.Side note: _There is no proof yet that the QSVM brings a quantum advantage, but the argument the authors of [1](https://arxiv.org/pdf/1804.11326.pdf) make, is that there is for sure no advantage if we use feature maps that are easy to simulate classically, because then we would not need a quantum computer to construct the Kernel._**Feature map**For the feature maps we use the ansatz $\mathcal{U}_{\Phi(x)} = U_{\Phi(x)} \otimes H^{\otimes n}$, where $U_{\Phi(x)} = \exp \left( i \sum_{S \in n} \phi_S(x) \prod_{i \in S} Z_i \right)$, which simplifies a lot when we (like in [1](https://arxiv.org/pdf/1804.11326.pdf)) only consider $S \leq 2$ interactions, which means we only let two qubits interact at a time.For $S \leq 2$ the product $\prod_{i \in S}$ only leads to interactions $Z_i Z_j$ and non interacting terms $Z_i$. And the sum $\sum_{S \in n}$ over all these terms that are possible with $n$ qubits.Finally we define the classical functions $\phi_i(\vec{x}) = x_i$ and $\phi_{i,j}(\vec{x}) = (\pi - x_i)( \pi- x_j)$.If we write this ansatz for 2 qubits and $S \leq 2$ we see how it simplifies:$$U_{\Phi(x)} = \exp \left(i \left(x_1 Z_1 + x_2 Z_2 + (\pi - x_1)( \pi- x_2) Z_1 Z_2 \right) \right)$$We won't get into details to much here, why we would take this ansatz. It is simply an ansatz that is simple enough an leads to good results.Finally we can define a depth of these circuits. Depth 2 means we repeat this ansatz two times. Which means our feature map becomes $U_{\Phi(x)} \otimes H^{\otimes n} \otimes U_{\Phi(x)} \otimes H^{\otimes n}$**Measuring the Quantum Kernel**Finally we need to extract the information about the quantum kernel again from the quantum circuit to feed it into the classical SVM algorithm. This is actual a non-trivial task, because we want to measure the overlap of two states $K(\vec{x}, \vec{z}) = \vert \langle \Phi (\vec{x}) \vert \Phi(\vec{z}) \rangle \vert^2$ but there is a smart way to estimate this overlap, in [1](https://arxiv.org/pdf/1804.11326.pdf) they used this circuit for that estimation. Which simply uses the fact that **if** $\mathcal{U}_{\Phi(x)} = \mathcal{U}_{\Phi(z)}$ the whole unitary would simplify to $\mathbb{1}$ and the input should be equal to the output.If we now measure the output, the frequency of the measurement string $0^n$ gives you an estimate of the overlap $\vert \langle \Phi (\vec{x}) \vert \Phi(\vec{z}) \rangle \vert^2$. (Because initially all qubits were $\vert 0 \rangle$)  Build circuit for feature mapQiskit Aqua provides a pre-built function that can construct the quantum circuit for $\mathcal{U}_{\Phi(x)}$. The Second Order Expansion refers to the number of interacting qubits which we called $S$ before. Since $S \leq 2$ we have terms with maximally two interacting qubits $Z_i Z_j$ (not for example $Z_i Z_j Z_k$), therefore Second Order.The function `SecondOrderExpansion` has the arguments `feature_dimension`, which is the dimension of the input data $\vec{x}$ and at the same time also the number of qubits. `depth` is the number of repetitions of the feature map.<jupyter_code>from qiskit.aqua.components.feature_maps import SecondOrderExpansion

feature_map = SecondOrderExpansion(feature_dimension=2, 
                                   depth=1)<jupyter_output><empty_output><jupyter_text>Print the feature map circuitTo print the feature map circuit we define an arbitrary vector `x` that we want to encode and construct the circuit for this datapoint.<jupyter_code>x = np.array([0.6, 0.3])
print(feature_map.construct_circuit(x))<jupyter_output><empty_output><jupyter_text>You might wonder now why there are no $Z_i$ and $Z_i Z_j$ matrices. This is simply because Qiskit does not provide these gates. We have to tranlate them into the gate set that Qiskit provides, which are manly 1-qubit rotations (here `U3`) and CNOTs. Qiskit does this work for us. It translates our feature map directly to gates that can be run on their qunatum computer. This is called compiling.  QSVM AlgorithmQiskit aqua also provides a pre-defined function to train the whole QSVM. Where we only have to provide the feature map, a training and a test set and Qiskit will do all the work for us.Apart from finding the quantum Kernel the QSVM algorithm does only classical optimization. In the end there is no difference to the classical SVM, except that the Kernels are coming from a quantum distribution.QSVM will minimize the loss $$L(W) = \sum_i \alpha_i - \frac{1}{2}\sum_{i,j} y_i y_j \alpha_i \alpha_j K(\vec{x}_i, \vec{x}_j)$$via optimizing the parameters $\vec{\alpha}$.After training we can predict a label $y'$ of a data instance $\vec{s}$ with $y' = \text{sign}\left( \sum_i y_i \alpha_i K(\vec{x}_i, \vec{s}) \right)$.<jupyter_code>from qiskit.aqua.algorithms import QSVM

qsvm = QSVM(feature_map, training_input, test_input)<jupyter_output><empty_output><jupyter_text>Run QSVMFinally we will have to define where we would like to run this algorithm. For now we will run it on a local QASM Simulator. But the algorithm could also be sent to the IBMQ an be evaluated on a real quantum computer.We will have to define the `shots`, which are the number of measurements that we will take for each qubit. And for better reproducability we also set here the random seeds `seed_simulator` and `see_transpiler`.<jupyter_code>from qiskit.aqua import run_algorithm, QuantumInstance
from qiskit import BasicAer

backend = BasicAer.get_backend('qasm_simulator')
quantum_instance = QuantumInstance(backend, shots=1024, seed_simulator=10598, seed_transpiler=10598)

result = qsvm.run(quantum_instance)<jupyter_output><empty_output><jupyter_text>Analyze output`results` is a dictionary that contains elements like the kernel matrix, the label predictions and also the classical weights of the QSVM.Let's have a quick look at them:  The kernel matrix for the trainingSince the training set contains 40 elements, the kernel matrix has dimension 40x40<jupyter_code>plt.scatter(training_input['Benign'][:,0], training_input['Benign'][:,1])
plt.scatter(training_input['Malignant'][:,0], training_input['Malignant'][:,1])
plt.show()
length_data = len(training_input['Benign']) + len(training_input['Malignant'])
print("size training set: {}".format(length_data))
print("Matrix dimension: {}".format(result['kernel_matrix_training'].shape))<jupyter_output><empty_output><jupyter_text>The success ratio shows how accurate the QSVM predicts the labels<jupyter_code>print("testing success ratio: ", result['testing_accuracy'])
test_set = np.concatenate((test_input['Benign'], test_input['Malignant']))
y_test = qsvm.predict(test_set, quantum_instance)<jupyter_output><empty_output><jupyter_text>And here we plot the results. The first plot shows the label predictions of the QSVM and the second plot shows the test labels.<jupyter_code>plt.scatter(test_set[:, 0], test_set[:,1], c=y_test)
plt.show()

plt.scatter(test_input['Benign'][:,0], test_input['Benign'][:,1])
plt.scatter(test_input['Malignant'][:,0], test_input['Malignant'][:,1])
plt.show()<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.09786665437957887, 'fraction_numerical': 0.01538957747776805, 'mean_word_length': 5.134539287733182, 'pattern_counts': {'":': 0, '<': 68, '<?xml version=': 0, '>': 71, 'https://': 6, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '16', 'dir': 'jupyter-structured-clean-dedup', 'id': '636624', 'license': 'Apache-2.0', 'n_tokens_mistral': 6764, 'n_tokens_neox': 6411, 'n_words': 2840, 'path': 'Quantum Support Vector Machines.ipynb', 'repo_name': 'PatrickHuembeli/QSVM-Introduction', 'size': '21729'}