https://doi.org/10.31449/inf.v46i5.3608 Informatica46 (2022) 95–103 95 NewApproachofKNNAlgorithminQuantumComputingBasedonNew DesignofQuantumCircuits Vu Tuan Hai 1 , Phan Hoang Chuong 1 and Pham The Bao 2 E-mail: haivt@uit.edu.vn, chuongph@uit.edu.vn, ptbao@sgu.edu.vn 1 University of Information Technology, Vietnam National University - Ho Chi Minh City (VNUHCM) Ho Chi Minh City 700000, Vietnam 2 Saigon University, Ho Chi Minh City 700000, Vietnam Keywords: quantum computing, machine learning,k-nearest neighbor Received: June 27, 2021 Quantum computing is rising as a new type of computer that theoretically reduces the time complexity of classical methods exponentially because of the nature of superposition. It is promising to reduce run times on large datasets in machine learning (ML). Meanwhile,k-nearest neighbor (kNN) is a simple ML algorithm that can be translated to a quantum version (QkNN) to perform classification tasks efficiently. Here, we show a new version of QkNN which has a speed up in time complexity by using a new design of quantum circuits called integrated swap test. This quantum circuit can load twoN - dimensional states and calculate the fidelity between them. Results show that QkNN allows us to take a different approach to the ML field. Povzetek: 1 Introduction Important progress was made in the fields of quantum com- putation [1, 2, 3] and machine learning [4, 5, 6, 7]. Nor- mally, when a machine learning algorithm is loaded with large data, it shows the limitations of classical computing. Meanwhile, quantum computation provides us with a mod- ern computing model. The integration of these two fields has resulted in a new field - quantum machine learning (QML). QML uses superposition and entanglement to cre- ate methods that can handle large data even more quickly than classical computers. Not only can QML outperform its classical counterpart in terms of speed, but it can also handle quantum data effectively. Several classical ML al- gorithms are ported to quantum versions, such as quantum k-means clustering (QkM) [8], quantumk nearest neighbor (QkNN) [11] quantum support vector machine (QSVM) [9], quantum principal component analysis (QPCA) [10], . . . However, there is a gap in accuracy between QML and traditional ML. So, in this paper, we will propose some methods for optimizing one of the QML algorithms (the QkNN algorithm) to achieve nearly equal accuracy to its classical version. Although these QkNN algorithms have their merits, they also have several limitations. For example, the method pre- sented in Ref. [12] just measures the overlap between two binary states. The algorithm in Ref. [13] attempts to load the database with M data points into the circuit, which de- mands a greater number of qubits than is usual. The meth- ods proposed in Ref. [14] have a limit since they can only perform binary classification. Besides, the algorithm pre- sented in Ref. [12] requires complete knowledge of the test state which is limited when dealing with quantum data. The research in Ref. [11] deals with the pure quantum prob- lems that can not be applied while quantum computing is in NISQ era [15]. Almost all materials that attempt to explain the benefit of QkNN on real-world data (Iris [16], Breast Cancer [17]) still have worse results than the classical ver- sion, such as Refs. [19, 20], ... This paper is divided into three sections. Sec. 2 re- views the background of our QkNN algorithm, including classical kNN [21], swap test procedure [22], and divide- and-conquer algorithm for quantum state preparation [20], which we used to improve QkNN. Sec. 3 will be the main of this paper which describes our methodology. Sec. 4 shows the main result, the proof of the reliability of our proposed circuit, and its application in QkNN which test on the Iris dataset. Sec. 5 discusses the conclusion and potential future works. 2 Relatedworks 2.1 ClassicalkNN kNN[21] is a supervised classical machine learning algo- rithm used to identify test states (sayjvi) whose labels must be determined, it is based on the premise: "Two states that are similar to each other are more likely to belong to the same class or pattern". Since it is a straightforward algo- rithm, kNN enables us to reason about the structure of the 96 Informatica46 (2022) 95–103 Hai et al. data we are dealing with. The test and training states are alsoN - dimensional complex states. The working mech- anism is simple: findjvi’s k nearest neighbors based on some distance metric between it and training states (sayU), and then decide its mark based on the details of these neigh- bors through majority voting. For the requirements of kNN, any concept of a distance metric may be used, the most common is Euclidean distance d(jui;jvi) withjui2 U, defined as Eq. (1). d(jui;jvi) = v u u t N 1 X i=0 (u i v i ) 2 (1) Hereu i ,v i arejui,jvi components, respectively. When we get into the quantum world, the popular alternative choice for the distance measure is fidelityF(u;v). Fidelity between two such normalized statesjui andjvi is defined as Eq. (2) [23]: F(; ) = Tr q p p 2 (2) with =juihuj and =jvihvj. In case ^ u, ^ v are pure state, the fidelity function can simply as: F(^ u;^ v) =jh^ uj^ vij 2 withj^ ui = jui kxk andj^ vi = jvi kvk : (3) It ranges from 0 (if the states are orthogonal or com- pletely distinguishable) to 1 (if the states are equal). As a result, the greater the fidelity between the two states is, the closer they will be. If we get the square root of F(^ u;^ v), it will return the cosine similarity betweenjui andjvi, (jui;jvi), defined as Eq. (4). p F(^ u;^ v) =jhujvij = (jui;jvi) = P N 1 i=0 u i v i P N 1 i=0 u 2 i P N 1 i=0 v 2 i : (4) The kNN algorithm is composed of the steps which are presented in Algorithm. 1. Although the kNN algorithm is simple to understand and implement, it has some limitations. kNN can easily become intractable for classical computers as the number of dimensions of training states increases. Classifying an N - dimensional test state by applying it to M training states needs aboutO(M) multiplication operations. Fur- thermore, there is no general approach for determining k so hyperparameter tuning is typically used to determine the best possiblek [18]. So the total complexityO(kM). Meanwhile, QkNN will take onlyO( p kM) if it combine with quantum search algorithm [30]. The complexity anal- ysis will be discussed more in Sec. 3.2. 2.2 Swaptestprocedure The swap test is introduced in Ref. [22] can return the cor- rect value of fidelity between two quantum statesj i and j i as mentioned in Eq. 2 by a lot of measurements. In order to implement the swap test, we need at least three registers prepared in statesj0i,j i andj i as Fig. 1. Figure 1: Circuit diagram for swap test.H is the Hadamard gate. First register will be measured, second and third reg- isters respond for loadj i andj i, respectively. At point A, the initial system’s state is simply: jR A i =j0ij ij i orj0; ; i for short: (5) After that, the Hadamard gate convert first qubitq 0 into the superposition state: Hjq 0 i =Hj0i = 1 p 2 (j0i+j1i): (6) Thus, at point B, the whole system is in the state: jR B i = 1 p 2 (j0ij ij i+j1ij ij i): (7) Whereas the action of Fredkin gate (or CSWAP gate) be- tween point B and point C reads: C S j0ij ij i =j0ij ij i; C S j1ij ij i =j1ij ij i: (8) So at point C, we have: C S jR B i =jR C i = 1 p 2 (j0ij ij i+j1ij ij i): (9) Finally, we apply Hadamard gate onq 0 again that make system into: jR D i = 1 p 2 (j0ij ij i+j1ij ij i) + 1 p 2 (j0ij ij ij 1ij ij i) (10) When we measure the first qubit, there are two possible states that we can receive: New Approach of KNN Algorithm in Quantum. . . Informatica46 (2022) 95–103 97 Algorithm1 kNN Input: training states U = u 0 ;u 1 ;:::u (M 1) and its labels U L = u L0 ;u L1 ;:::;u L (M 1) , test states (unlabeled) V =v 0 ;v 1 ;:::;v (M 0 1) and hyperparameterk. Output: set of test labelsV L = (v L0 ;v L1 ;:::;v L ( M 0 1 ) ). 1: function PREDICT 2: fori 0 toM 0 1do 3: Load all training statesU and test statesv i on the register. 4: forj 0 toM 1do 5: Calculate(dist (vi) ) j = dist(u j ;v i ). 6: endfor 7: Sort dist (vi) =f(dist (vi) ) 0 ;:::(dist (vi) ) ((M 1) g (descending or ascending 8: Choosek neighbors which are nearest tov i . 9: Conduct majority voting and assign the labelv Li of the majority to the test point. 10: endfor returnV L = (v L0 ;v L1 ;:::;v L ( M 0 1 ) ) 11: endfunction P(q 0 = 0) orP(0) = 1 2 (h jh j+h jh j) 1 2 (j ij i+j ij i) = 1 2 + 1 2 jh j ij 2 P(q 0 = 1) orP(1) = 1 2 (h jh jh jh j) 1 2 (j ij ij ij i) = 1 2 1 2 jh j ij 2 (11) The final result now is: F( ; ) =P(0) P(1) =jh j ij 2 : (12) Ifj i andj i are orthogonal,jh j ij 2 = 0, that mean P(0) = P(1) = 0:5. Otherwise, ifj i andj i are identi- cal,jh j ij 2 = 1, that meanP(0) = 1;P(1) = 0. 2.3 Preparequantumstate Normally, loading quantum states requires the quantum system a lot of gates because the statej i =c 0 j0i+:::+ c N 1 jN 1i (or P N 1 j=0 c j jji has the dimensionalN which frequently greater than 2, and components in it are belong to the complex space. An easiest approach is to encodem - bits of binary data into qubit strings. Let d j =fd (k) j g m k=1 (d (k) j = 0;1;j = 0;:::;N 1) be the binary bit-strings, the equation for encoding can be described by Ref. [24]: j i = 1 p N N 1 X j=0 jjijd (m) j :::d 1 j i: (13) This method of encoding is simple and can represent any state by using a series of NOT gate. The downside is that it not only does not use superposition but also needs more qubits -mN qubits for one state to encodeN components in it. The greaterm is, the more precisely the component is defined. Another way which is provided in Ref. [28, 29, 20] will help us use fewer qubits a lot, this devised method is based on quantum forking [25]. The basic theory is to break a problem into sub-problems of the same class and then com- bine the solutions of these sub-problems to offer the solu- tion to the original problem. The main idea is building the quantum state in each level of the state tree in a top-down or divide-and-conquer strategy. At each step, they divide the input into bi-dimensional sub-vectors, load it on qubit and repeat until reached the desired quantum state. In case of loading N - dimensional real vectors, these method [28, 29] take onlyO(log 2 N) qubits andO(N) computation cost. But it have an exponential depth in re- lation to the number of qubits. Another method is comes from Ref. [20] which has overall depthO(log 2 2 N) but us- ingO(N) qubits. Three above methods proposed a trade-off between the number of qubits and circuit depth, when using more qubits we have a short execution time and vice versa. For fitting with the NISQ device and simulation’s resources, we will choose Ref. [20] as the loading component for dealing with states that have small or medium dimensions. 3 Methodology 3.1 Integratedswaptestcircuit As discussed in the previous section, if we want to perform the calculation about the fidelity between twoN - dimen- sional states likej i andj i, we must have a quantum cir- cuit that has two separate functions. The first will load2N componentsf i g N 1 i=0 ,f i g N 1 i=0 . The second will apply theN - swap test to measure and calculate the probability of value 0 or 1 on the first qubit, p P(0) P(1) will be 98 Informatica46 (2022) 95–103 Hai et al. Figure 2: A circuit generated by the divide-and- conquer strategy described in Ref. [20] that encode the 8–dimensional statej i = [ 1 p 8 1 p 8 ::: 1 p 8 ] T . the final result. The idea to create a quantum circuit that meets the above requirement is to combine the circuit in Ref. [20], log 2 N (orn) Fredkin gates and two Hadamard gates. The outcome from the circuits in Ref. [20] will be the input of the second component. This new design of the quantum circuit whose name is integrated swap test, is described in Fig. 3. The total qubits that need to be used in this circuit in detail is(2(N 1)+1) for three sub - circuits. The first sub - circuit also the first qubit, will be measured to calculate the probability of value 0 or 1 on c (a classical channel, show in Fig. 3). The second and third sub - circuits (v 1 and v 2 ) have (N 1) qubits which is from index 1 to (N 1) and from N to 2(N 1) use to encodej i andj i, respectively. It continued to be active on wires which has indices: I v1 =fi 2 j1 i ng forj i; I v2 =fi 2 +(N 1)j1 i ng forj i: (14) Ourn Fredkin gates are attached on: I n C S =fI C S jI C S = (0;(i v1 ) j ;(i v2 ) j ); i v1 2I v1 ;i v2 2I v2 ;j = 1;:::;n)g: (15) Control qubits inn Fredkin gates always have index 0, the second i v1 and the third i v2 in the tuple I C S are the target qubits which swap each other if the first qubit has value1, nothing happened otherwise. Two Hadamard gates remain on the first wire like the original swap test. About the complexity, the number of qubits used to com- pute 2N - dimensional states is stillO(N), and the circuit depth isO(log 2 2 N+log 2 N+1) which is the sum of load- ing stage andN - swap test stage. Figure 3: Our new circuit that can calculate the fidelity be- tween two 8 - dimensional statesj i = [0 1 0 1 0 1 0 1] T andj i = [1 0 1 0 1 0 1 0] T . 3.2 HybridQkNNalgorithmwhenusing integratedswaptestcircuit Formally, our QkNN algorithm still consists of many steps that are described in Algorithm 1 but it has other crucial points. Not like other QkNN versions that deal with pure quantum problems [12, 13, 11], we use the idea that can combine the advantages of classical computing and quan- tum computing. The classical computer will do its best job including load states (Step 1 in Fig. 4), sort descending (Step 6 in Fig. 4), and mark label for test state (Step 7 in Fig. 4). The quantum computer only does the calculating fidelity task that outperforms the classical computer in case the dimension of states increases exponentially. In the first step, the classical computer will put a train- ing stateu j and a test statev i into the integrated swap test circuit. This step will be repeated MM 0 times with M andM 0 are the cardinality of the training set and test set, respectively. In the second and third steps, the quantum computer creates phasesf! i g N 2 i=0 for theR y gates in the circuit, these gates will be recreatedMM 0 times. For the pair(u j ;v i ), the circuit must perform - measuren iter times to reduce the noise from the real environment, it finally re- turns the average of all results. The fifth, sixth and seventh steps are not hard to understand, it is completely similar to the classical kNN. All of the steps from 2 to 7 described New Approach of KNN Algorithm in Quantum. . . Informatica46 (2022) 95–103 99 above will be repeated until the test set does not have any unlabeled states. Because all computation is done during prediction, there is no training phase, and we haveO(1) for both time and space. The prediction part is split into 2 parts: classical and quantum. Computing the distances between all train states and each test state will consume aboutO(Mlog 2 2 N), when takingk nearest neighbors will depend on the classical al- gorithm. If we use the Brute-force algorithm, the com- plexity isO(kM) or use some Sort algorithm, the com- plexity isO(MlogM). So the total complexity when pre- dictingM 0 test states isO(M 0 (Mlog 2 2 N +kM)+1) or O(M 0 (Mlog 2 2 N +MlogM)+1). In some research about fully quantum kNN, the above complexities can be reduced toO(M 0 M(log 2 2 N + p kM)+1) by replacing Brute-force or Sort algorithm by Grover algorithm [12, 13]. Obviously, this way will make our circuit deeper. 4 Experiments To evaluate the proposed methods, we perform two experi- ments. In the first experiment, we prove that the proposed circuit can be applied in some algorithms. In the second experiment, we use this circuit in our new QkNN on Iris dataset. We use Qiskit SDK [27] (version 0.24.1) in all exper- iments because of its completeness and ease of use, the maximum number of qubits is 31 on Intel core i5-5250U and 8 GB RAM classical computer. The maximum of di- mensional of state is15, so2(N 1)+1< 31 andN < 16. The number of shots is16384. The codes in this paper, including documentation, are available on Ref. [26]. 4.1 Proofofreliabilityofintegratedswap testcircuit We evaluate the integrated swap test circuit on various it- erations from 0 to 10000 and the number of dimensions f2 k g 3 k=1 . As in the Fig. 5, we easily see that the error is quite chaotic in0 -1000 iterations. It tends to be in an or- der and gets smaller according to the iterations from 1000 to10000. For the2 - dimensional state, the error is accept- able with Standard error (RE) between 0:25% and 0:75%. But in case of higher dimensional state, the average RE are 0:27%;1:01% and 5:34% for 2, 4 and 8 - dimensional re- spectively, it increases exponentially. We can explain this phenomenon as: the higher dimensional state, smaller the value of components. Meanwhile, we can use only a fi- nite number of shots (n shot = 16384), the smallest divi- sion is 1 16384 that can not be reduced anymore, note that P(0) = n (c=0) n shot andP(1) = n (c=1) n shot . 4.2 HybridQkNNonIrisdataset Since the number of qubits in the quantum circuit are re- stricted, the resources for describing the states are limited. Currently, the way the quantum circuit works is that one circuit is madeM times per test data point andMM 0 times in the whole predicting stage. That means the number of training states and test states is not the largest limiting fac- tor because the quantum circuit can be recreated once the machine runs out of memory. The limiting factor is the di- mensionality, the memory accepted with these values at 8. Values not following the relation ofN = 2 n can be chosen but can be considered a waste of qubit resources. The Iris dataset is 4 - dimensional and consists of 150 examples in total of three classes. It consists of length and width measurements of sepals and petals from three differ- ent flowers: Iris Setosa, Iris Versicolour, and Iris Virginica. In short, the dimensionality does not need to be changed, and the instances of each class will be equal to each other. The values of a statejxi must to be encoded to quantum state through dividing componentsfx i g 3 i=0 by normjxj be- fore conducting the experiment. After prepared data, the QkNN may be configured to be- gin classifying it. As mentioned in Sec. 4, Qiskit used in this project so the circuits will be simulated with the qasm_simulator. This simulator would run the circuit as if it were running on a quantum computer, which means it will have to run several times in order to reach the state provided by the quantum circuit. The setups of experiment include: 1. Using full features of Iris dataset (4 features). 2. Number of training states and test states will be n train =f2 i g 7 i=3 andn test =fb0:3 2 i cg 7 i=3 respec- tively. The train set and test set are not overlapped together. 3. Conduct on a variety ofk number of neighbors with k =f1;3;5;7g. In case of k is large compared to n train (k =f5;7g and n train =f8;16g), the experi- ment will not be conducted because the kNN will pro- duce an underfitted model. The first thing we can see is that the accuracy of classical and quantum method varies. From the metrics in Tab. 1, it is observable that on the Iris dataset, Hybrid QkNN outper- forms classical kNN in some cases (k =f3;5g) but aver- agely classical algorithm is still better than Hybrid QkNN. When comparing with recent QkNN [13, 19], our method was outperformed in almost all cases, these old methods have struggled when dealing with a large number of train states. On the other hand, Hybrid QkNN runs faster than a little bit, the total run-times shown as Tab. 3. The old QkNN have more disadvantage in that the train set must be small, all train states was loaded on the Oracles at the same times. So the experiments onn train = 128 can not be con- ducted because the algorithm makes the simulation run out of memory quickly. 100 Informatica46 (2022) 95–103 Hai et al. Some of the facts in Tab. 2 also indicate that the classi- cal kNN and Hybrid QkNN both tend to increase asn train increases. This phenomenon can be explained by looking at the confusion matrices in Fig. 7. It is apparent that in the confusion matrices, accuracy which is smaller than 100% is always in the case of the truth label is belong to class2 (Virginica) but our algorithm labeled class 1 (Versicolor). This comes from the fact that we encoded the normal state in terms of quantum state as shown from Fig. 6. a to Fig. 6. b, all states now occupy on the surface of 4 – dimensional ball and make the ratio between the interference space between the states labeled1 and the states labeled2 and the whole space of all states is larger. Meanwhile, the space of the states labeled0 is quite separate. That leads to the states of these two labels being confused. 5 Conclusion In this paper, we present the Hybrid QkNN algorithm, this algorithm uses the new design of quantum circuits that can achieve higher functionality compared to its previous ver- sion (swap test). One of the most important advantages of the Hybrid QkNN is that it is capable of handling a large number of train states without many qubits because it is combined with a classical computer to reduce a lot of tasks. The task that classical computer accomplishes currently do not have their corresponding quantum version so it is still performed well on a classical computer. In our experiment, we simulated the Hybrid QkNN to solve the problem of classifying the Iris dataset. The re- sults showed that our method can provide a high degree of accuracy that is nearly equal to the classical kNN. The rea- sons which make this algorithm does not achieve the same or higher accuracy come from the fact that we are forced to encode the normal state into the quantum state and the number of shots is limited. This can be fixed in the future if we have a more efficient simulator or simply experiment on a real quantum computer which is considered by experts to exist in the next few decades or earlier [15]. Acknowledgement This research was supported by The VNUHCM-University of Information Technology’s Scientific Research Support Fund under Grant No. D1-2022-08. References [1] Arute, F., Arya, K., Babbush, R., Bacon, D., Bardin, J., Barends, R., Boixo, S., Broughton, M., Buckley, B., Buell, D. & Others. Hartree- Fock on a superconducting qubit quantum computer. Science. 369, 1084-1089 (2020). https://doi.org/10.1126/science.abb9811 [2] Wu, S., Chan, J., Guan, W., Sun, S., Wang, A., Zhou, C., Livny, M., Carminati, F., Di Meglio, A., Li, A. & Others. Application of quantum ma- chine learning using the quantum variational clas- sifier method to high energy physics analysis at the LHC on IBM quantum computer simulator and hardware with 10 qubits. Journal Of Physics G: Nuclear And Particle Physics. 48, 125003 (2021). https://doi.org/10.1088/1361-6471/ac1391 [3] Alexeev, Y ., Bacon, D., Brown, K., Calderbank, R., Carr, L., Chong, F., DeMarco, B., Englund, D., Farhi, E., Fefferman, B. & Others. Quan- tum computer systems for scientific discovery. PRX Quantum. 2, 017001 (2021). https://doi.org/10.1103/ PRXQuantum.2.017001 [4] Dogan, A. & Birant. D. Machine learning and data mining in manufacturing. Expert Sys- tems With Applications. 166 pp. 114060 (2021). https://doi.org/10.1016/j.eswa.2020.114060 [5] Greener, J., Kandathil, S., Moffat, L. & Jones, D. A guide to machine learning for biologists. Nature Reviews Molecular Cell Biology. 23, 40-55 (2022). https://doi.org/10.1038/s41580-021-00407-0 [6] Shorten, C., Khoshgoftaar, T. & Furht, B. Deep Learning applications for COVID-19. Journal Of Big Data.8, 1-54 (2021). https://doi.org/10.1186/s40537- 020-00392-9 [7] Ma, W., Liu, Z., Kudyshev, Z., Boltasseva, A., Cai, W. & Liu, Y . Deep learning for the design of pho- tonic structures. Nature Photonics. 15, 77-90 (2021). https://doi.org/10.1038/s41566-020-0685-y [8] Lloyd, S., Mohseni, M. & Rebentrost, P. Quantum algorithms for supervised and unsupervised machine learning. ArXiv Preprint ArXiv:1307.0411. (2013) [9] Rebentrost, P., Mohseni, M. & Lloyd, S. Quantum support vector machine for big data classification. Physical Review Letters. 113, 130503 (2014). https://doi.org/10.1103/ PhysRevLett.113.130503 [10] Lloyd, S., Mohseni, M. & Rebentrost, P. Quantum principal component analysis. Nature Physics. 10, 631-633 (2014). https://doi.org/10.1038/nphys3029 [11] Wiebe, N., Kapoor, A. & Svore, K. Quantum Algorithms for Nearest-Neighbor Methods for Su- pervised and Unsupervised Learning. Quantum In- formation And Computation. 15, 318-358 (2015). https://doi.org/10.48550/arXiv.1401.2142 [12] Ruan, Y ., Xue, X., Liu, H., Tan, J. & Li, X. Quan- tum algorithm for k-nearest neighbors classification based on the metric of hamming distance. Interna- tional Journal Of Theoretical Physics.56, 3496-3507 (2017). https://doi.org/10.1007/s10773-017-3514-4 New Approach of KNN Algorithm in Quantum. . . Informatica46 (2022) 95–103 101 k - nearest neighbors 1 3 5 7 Average Classical kNN 98.7% 92.8% 96.7% 98.2% 96.6% QkNN [13, 19] 70.2% 71.6% 75.7% 50.7% 67.1% Our method 95.1% 97.3% 97.4% 94.5% 95.7% Table 1: A comparison between classical kNN, QkNN [13, 19] and our method (Hybrid QkNN) on the same dataset based onk. The accuracy of eachk was calculated averagely onn train from 16 to 128. n train 8 16 32 64 128 Average Classical kNN 100% 91.7% 92.6% 96.0% 100% 96.6% QkNN [13, 19] 100% 100% 49.5% 43.4% * 67.1% Our method 100% 100% 91.7% 92.1% 97.3% 95.7% Table 2: A comparison between classical kNN, QkNN [13, 19] and our method (Hybrid QkNN) on the same dataset based onn train . The accuracy of eachn train was calculated averagely onk from 1 to 7. [13] Basheer, A., Afham, A. & Goyal, S. Quantum k -nearest neighbors algorithm. ArXiv Preprint ArXiv:2003.09187. (2020). https://doi.org/10.48550/arXiv.2003.09187 [14] Fastovets, D., Bogdanov, Y ., Bantysh, B. & Lukichev, V . Machine learning methods in quantum comput- ing theory. International Conference On Micro-and Nano-Electronics 2018. 11022 pp. 110222S (2019). https://doi.org/10.1117/12.2522427 [15] Preskill, J. Quantum computing in the NISQ era and beyond. Quantum. 2 pp. 79 (2018). https://doi.org/10.22331/q-2018-08-06-79 [16] Fisher, R. The use of multiple measurements in taxonomic problems. Annals Of Eugen- ics. 7, 179-188 (1936). https://doi.org/10.1111/ j.1469-1809.1936.tb02137.x [17] Zwitter, M. & Soklic, M. Breast Cancer dataset. (1988), data retrieved from UCI Machine learning. [18] Zhang, S., Li, X., Zong, M., Zhu, X. & Cheng, D. Learning k for knn classification. ACM Transactions On Intelligent Systems And Technology (TIST). 8, 1- 19 (2017). https://doi.org/10.1145/2990508 [19] Kok, D., Caron, S. & Acun, A. Building a quantum kNN classifier with Qiskit: theoretical gains put to practice. (2021) [20] Araujo, I., Park, D., Petruccione, F. & Silva, A. A divide-and-conquer algorithm for quantum state preparation. Scientific Reports. 11, 1-12 (2021). https://doi.org/10.1038/s41598-021-85474-1 [21] Cunningham, P. & Delany, S. k-Nearest neighbour classifiers-A Tutorial. ACM Com- puting Surveys (CSUR). 54, 1-25 (2021). https://doi.org/10.1145/3459665 [22] Buhrman, H., Cleve, R., Watrous, J. & De Wolf, R. Quantum fingerprinting. Physical Review Let- ters. 87, 167902 (2001). https://doi.org/10.1103/ PhysRevLett.87.167902 [23] Jozsa, R. Fidelity for mixed quantum states. Jour- nal Of Modern Optics. 41, 2315-2323 (1994). https://doi.org/10.1080/09500349414552171 [24] Mitarai, K., Kitagawa, M. & Fujii, K. Quantum analog-digital conversion. Phys- ical Review A. 99, 012301 (2019). https://doi.org/10.1103/PhysRevA.99.012301 [25] Park, D., Sinayskiy, I., Fingerhuth, M., Petruccione, F. & Rhee, J. Parallel quantum trajectories via fork- ing for sampling without redundancy. New Journal Of Physics. 21, 083024 (2019). https://doi.org/10.1088/ 1367-2630/ab35fb [26] Hai, V . Source code and experiment results. (2022), Github, https://github.com/vutuanhai237/ HybridQkNN [27] Quantum, I. Qiskit open-source. (2021), Github, https://github.com/Qiskit [28] Iten, R., Colbeck, R., Kukuljan, I., Home, J. & Chri- standl, M. Quantum circuits for isometries. Physical Review A.93, 032318 (2016). https://doi.org/10.1103/ PhysRevA.93.032318 [29] Park, D., Petruccione, F. & Rhee, J. Circuit-based quantum random access memory for classical data. Scientific Re- ports. 9, 1-8 (2019). https://doi.org/10.1038/ s41598-019-40439-3 [30] Grover, L. A fast quantum mechanical algorithm for database search. Proceedings Of The Twenty- eighth Annual ACM Symposium On Theory Of Com- puting. pp. 212-219 (1996). https://doi.org/10.1145/ 237814.237866 102 Informatica46 (2022) 95–103 Hai et al. n train 8 16 32 64 128 QkNN [13, 19] 7s 51s 464s 4138s * Our method 8s 32s 257s 2835s 45600s Table 3: Total of run-times between QkNN [13, 19] and our method (Hybrid QkNN) on the same dataset based onn train . *The experiments of QkNN [13, 19] onn train = 128 can not be conducted because the algorithm makes the simulation run out of memory. Classical computer Quantum computer 2. Create integrated swap test circuit for in in , 3. Calculate , increase by one unit 5. Append into list , increase by one unit 7. Label by majority vo ng with training labels , increase by one unit 4. Returnd , = 1. Load training states , training labels and test states , 6. Sort descending and choose rst elements Begin End Figure 4: Hybrid QkNN’s diagram, a version of QkNN with collaboration between classical computer and quantum computer. Figure 5: Standard error (SE) and relative error (RE) when calculating fidelity between two states, are defined as: SE = Pn iter 1 i=0 jf predict i f truth j n iter andRE = SE ( Pn iter 1 i=0 f predict n iter ) 100(%). New Approach of KNN Algorithm in Quantum. . . Informatica46 (2022) 95–103 103 Figure 6: Visualisation of the encoding method on the dataset (Sepal width and Sepal height do not display in this figure). The untouched dataset (a), and the dataset encoded to be loaded into the quantum circuit (b). Figure 7: The confusion matrices on differentn train andk nearest neighbors. The color of boxes ranges from white to black corresponding for high to low integer values. 104 Informatica46 (2022) 95–103 Hai et al.