<jupyter_start><jupyter_text>Trusted Notebook" width="250 px" align="left">  _*Quantum K-Means algorithm*_ *** Contributors <NAME>, <NAME>, <NAME>, <NAME>, <NAME>, <NAME> and <NAME>$^{1}$1. Institute of Fundamental and Frontier Sciences, University of Electronic Science and Technology of China，Chengdu, China，610051***  IntroductionClustering algorithm is a typical unsupervised learning algorithm, which is mainly used to automatically classify similar samples into one category.In the clustering algorithm, according to the similarity between the samples, the samples are divided into different categories. For different similarity calculation methods, different clustering results will be obtained. The commonly used similarity calculation method is the Euclidean distance method.What we want to show is the quantum K-Means algorithm. The K-Means algorithm is a distance-based clustering algorithm that uses distance as an evaluation index for similarity, that is, the closer the distance between two objects is, the greater the similarity. The algorithm considers the cluster to be composed of objects that are close together, so the compact and independent cluster is the ultimate target. Experiment designThe implementation of the quantum K-Means algorithm mainly uses the swap test to compare the distances among the input data points. Select K points randomly from N data points as centroids, measure the distance from each point to each centroid, and assign it to the nearest centroid- class, recalculate centroids of each class that has been obtained, and iterate 2 to 3 steps until the new centroid is equal to or less than the specified threshold, and the algorithm ends. In our example, we selected 6 data points, 2 centroids, and used the swap test circuit to calculate the distance. Finally, we obtained two clusters of data points.$|0\rangle$ is an auxiliary qubit, through left $H$ gate, it will be changed to $\frac{1}{\sqrt{2}}(|0\rangle + |1\rangle)$. Then under the control of $|1\rangle$, the circuit will swap two vectors $|x\rangle$ and $|y\rangle$. Finally, we get the result at the right end of the circuit:$$|0_{anc}\rangle |x\rangle |y\rangle \rightarrow \frac{1}{2}|0_{anc}\rangle(|xy\rangle + |yx\rangle) + \frac{1}{2}|1_{anc}\rangle(|xy\rangle - |yx\rangle)$$If we measure auxiliary qubit alone, then the probability of final state in the ground state $|1\rangle$ is:$$P(|1_{anc}\rangle) = \frac{1}{2} - \frac{1}{2}|\langle x | y \rangle|^2$$If we measure auxiliary qubit alone, then the probability of final state in the ground state $|1\rangle$ is:$$Euclidean \ distance = \sqrt{(2 - 2|\langle x | y \rangle|)}$$So, we can see that the probability of measuring $|1\rangle$ has positive correlation with the Euclidean distance.The schematic diagram of quantum K-Means is as the follow picture.[[1]](cite) To make our algorithm can be run using qiskit, we design a more detailed circuit to achieve our algorithm. | Quantum K-Means circuit  Data pointspoint numthetaphilamxy10.01pipi0.7106330.70356220.02pipi0.7141420.730.03pipi0.7176330.69642140.04pipi0.7211070.69282450.05pipi0.7245620.6892161.31pipi0.8868110.46213271.32pipi0.8891110.45769281.33pipi0.8913880.45324191.34pipi0.8936430.448779101.35pipi0.8958760.444305  Quantum K-Means algorithm program<jupyter_code># Checking the version of PYTHON; we only support > 3.5
import sys
if sys.version_info < (3,5):
    raise Exception('Please use Python version 3.5 or greater.')

#Importing qiskit and math lib
from qiskit import  QuantumProgram
import math

#import Qconfig<jupyter_output><empty_output><jupyter_text>In this section, we first judge the version of Python and import the packages of qiskit, math to implement the following code. We show our algorithm on the ibm_qasm_simulator, if you need to run it on the real quantum conputer, please remove the "" in frint of "import Qconfig".<jupyter_code>pi = math.pi

theta_list = [0.01, 0.02, 0.03, 0.04, 0.05, 1.31, 1.32, 1.33, 1.34, 1.35]

Q_program = QuantumProgram()
#Q_program.set_api(Qconfig.APItoken, Qconfig.config['url'])<jupyter_output><empty_output><jupyter_text>Here we define the number pi in the math lib, because we need to use u3 gate. And we also define a list about the parameter theta which we need to use in the u3 gate. As the same above, if you want to implement on the real quantum comnputer, please remove the symbol "" and configure your local Qconfig.py file.<jupyter_code>def k_means():
    # create Quantum Register called "qr" with 5 qubits
    qr = Q_program.create_quantum_register("qr", 5)
    # create Classical Register called "cr" with 5 bits
    cr = Q_program.create_classical_register("cr", 5)
    
    # Creating Quantum Circuit called "qc" involving your Quantum Register "qr"
    # and your Classical Register "cr"
    qc = Q_program.create_circuit("k_means", [qr], [cr])
    
    #Define a loop to compute the distance between each pair of points
    for i in range(9):
        for j in range(1,10-i):
            # Set the parament theta about different point
            theta_1 = theta_list[i]
            theta_2 = theta_list[i+j]
            #Achieve the quantum circuit via qiskit
            qc.h(qr[2])
            qc.h(qr[1])
            qc.h(qr[4])
            qc.u3(theta_1, pi, pi, qr[1])
            qc.u3(theta_2, pi, pi, qr[4])
            qc.cswap(qr[2], qr[1], qr[4])
            qc.h(qr[2])
                
            qc.measure(qr[2], cr[2])
            qc.reset(qr)
            
            result = Q_program.execute("k_means",   backend = 'local_qasm_simulator')   
            print(result)
            print('theta_1:' + str(theta_1))
            print('theta_2:' + str(theta_2))
            print( result.get_data("k_means"))
                
            #result = Q_program.execute(["reset"], backend='ibmqx4', shots=1024, timeout=600)

if __name__ == "__main__":
    k_means()<jupyter_output>COMPLETED
theta_1:0.01
theta_2:0.02
{'time_taken': 0.036707773, 'counts': {'00000': 1024}}
COMPLETED
theta_1:0.01
theta_2:0.03
{'time_taken': 0.05818302, 'counts': {'00000': 1024}}
COMPLETED
theta_1:0.01
theta_2:0.04
{'time_taken': 0.121639978, 'counts': {'00000': 1024}}
COMPLETED
theta_1:0.01
theta_2:0.05
{'time_taken': 0.153166482, 'counts': {'00000': 1024}}
COMPLETED
theta_1:0.01
theta_2:1.31
{'time_taken': 0.132502901, 'counts': {'00100': 196, '00000': 828}}
COMPLETED
theta_1:0.01
theta_2:1.32
{'time_taken': 0.163225122, 'counts': {'00100': 180, '00000': 844}}
COMPLETED
theta_1:0.01
theta_2:1.33
{'time_taken': 0.186406598, 'counts': {'00100': 188, '00000': 836}}
COMPLETED
theta_1:0.01
theta_2:1.34
{'time_taken': 0.214266842, 'counts': {'00100': 191, '00000': 833}}
COMPLETED
theta_1:0.01
theta_2:1.35
{'time_taken': 0.239643323, 'counts': {'00100': 205, '00000': 819}}
COMPLETED
theta_1:0.02
theta_2:0.03
{'time_taken': 0.263497595, 'counts': {'00000': 1024}}
COMPLETED
theta_1:0.02
the[...]<jupyter_text>Here we achieve the function k_means() and the test main function to run the program. Considering the qubits controlling direction of ibmqx4, we takes the quantum register 1, 2, 4 as our working register, if you want to run this program on other computer, please redesign the circuit structure to ensure your program can be run accurately.   Result analysisIn this program, we take the quantum register 1, 2, 4 as our operated register (considering the condition when using ibmqx4.) We take the quantum register 1, 4 storing the input information about data points, and the quantum register 2 as controlling register to decide whether to use the swap operator. To estimate the distance of any pair of data points, we use a loop to implement the K-Means Circuit. In the end, we measure the controlling register to judge the distance between two data points. The probability when we get 1 means that the distance between two data points.  Reference[1].Quantum algorithms for supervised and unsupervised machine learning(*see open access: [ arXiv:1307.0411v2](https://arxiv.org/abs/1307.0411)*)<jupyter_code>%run "../version.ipynb"<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.1023768259470166, 'fraction_numerical': 0.07774201535033425, 'mean_word_length': 4.297704918032787, 'pattern_counts': {'":': 1, '<': 24, '<?xml version=': 0, '>': 25, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '4', 'dir': 'jupyter-structured-clean-dedup', 'id': '573633', 'license': 'Apache-2.0', 'n_tokens_mistral': 2896, 'n_tokens_neox': 2450, 'n_words': 948, 'path': 'appendix/teach_me_qiskit_2018/quantum_machine_learning/1_K_Means/Quantum K-Means Algorithm.ipynb', 'repo_name': 'kardashin/qiskit-tutorial', 'size': '8101'}