WHERE CAN QUANTUM KERNEL BASED CLASSIFICA-
Year: 2021

Abstract:
The classification problem is a core problem of supervised learning, which is widely present in our life. As a class of algorithms for pattern analysis, Kernel methods have been widely and effectively applied to classification problems. However, when very complex patterns are encountered, the existing kernel methods are powerless. Recent studies have shown that quantum kernel methods can effectively handle some classification problems of complex patterns that classical kernel methods cannot handle. However, this does not mean that quantum kernel methods are better than classical kernel methods in all cases. It is still unclear under what circumstances quantum kernel methods can realize their great potential. In this paper, by exploring and summarizing the essential differences between quantum kernel functions and classical kernel functions, we propose a criterion based on inter-class and intra-class distance and geometric properties to determine under what circumstances quantum kernel methods will be superior. We validate our method with toy examples and multiple real datasets from Qiskit and Kaggle. The experiments show that our method can be used as a valid determination method.

heading: 1 INTRODUCTION
text: Since the birth of quantum computing, researchers have been looking for the best place to apply quantum algorithms. The first two quantum algorithms devised were Grover (1996) and Shor (1994). They proved the advantages of quantum algorithms in some specific problems such as search and factorization theoretically. With the rise of artificial intelligence, more and more quantum algorithms combine quantum computing with machine learning. For example, quantum neural network (QNN) was first proposed by Ezhov & Ventura (2000) but was only defined in general terms at the physical level. Ricks & Ventura (2003) defined an approach to train QNNs, but the complexity of its method is exponential. Subsequently, Lloyd et al. (2013), Blacoe et al. (2013), and Rebentrost et al. (2014) tried to introduce quantum computing into clustering, distributed semantics, and SVMs, respectively, but their approaches were too limited to theory. As researchers introduce quantum into various machine learning algorithms, Schuld et al. (2015), Biamonte et al. (2017), Kopczyk (2018), Ciliberto et al. (2018) have started to summarize and sort out the concept of quantum machine learning.
The physical implementation of quantum computers has made great strides in recent years. In 2019, Arute et al. (2019) announced the achievement of quantum hegemony, a milestone event in quantum computing. Also, thanks to the emergence of several quantum computing platforms, such as those of IBM and Google, it has become possible for ordinary researchers to translate their research on quantum machine learning algorithms from theory to practice. For example, Farhi & Neven (2018), Quek et al. (2021), Verdon et al. (2019), Garg et al. (2019), Srivastava et al. (2020), and Meichanetzidis et al. (2020) have demonstrated the value of quantum machine learning in machine learning tasks by practice, respectively.
On the other hand, one of the most famous machine learning algorithms is the kernel method. A detailed description of the kernel method has been given by Burges (1998a), Muller et al. (2001), Scholkopf (2001) and Hofmann et al. (2008). Inspired by the classical kernel approach, Rebentrost et al. (2014) proposed a quantum kernel approach based on SVM, but only theoretically feasible.
It was not until Schuld & Killoran (2019), and Havlı́ček et al. (2019) systematically proposed two feasible implementations of quantum kernel methods that made quantum kernel methods became
one of the most mature and practically valuable quantum machine learning methods. Later, Blank et al. (2020), Wang et al. (2021), Kusumoto et al. (2021), and Peters et al. (2021) experimentally demonstrated the superiority of quantum kernel methods on some datasets. However, none of them have systematically explored the conditions when quantum kernel methods exist to their advantage. Schuld (2021) summarizes the connection between quantum kernel methods and classical kernel methods. However, it is still unclear when quantum kernel methods will have advantages over classical kernel methods. In this paper, we conclude under what circumstances the quantum kernel method is better or worse than the classical kernel method. Specifically,
• We propose that the quantum kernel function is probabilistic and classify the existing kernel functions.
• We propose a distance-based criterion δ to determine whether the quantum kernel method has the quantum advantage for a given dataset and demonstrate this experimentally.
• We explore and find the relationship between the superiority of quantum kernel methods in two dimensions and (1) the complexity of the data pattern (2) the data based on Mersenne Twister random distribution.

heading: 2 BACKGROUND AND RELATED WORK
text: Classical Kernel. Kernel methods, summarised by Muller et al. (2001) and Hofmann et al. (2008), are an important class of machine learning methods that carry out machine learning by defining which data points are similar to each other and which are not. Mathematically, the similarity is a distance in the data space, i.e., the distance between digital representations of data points. Specifically, the kernel method uses a feature mapping function fc to map data from a point in the original input space O to a higher-dimensional Hilbert feature space Fc, i.e., fc : O → Fc, making separability between data classes more explicit. One of the most famous methods is the support vector machine (SVM) proposed by Burges (1998b).
One important factor that makes the kernel method successful is the kernel track. Scholkopf (2001) pointed out that instead of explicitly calculating the distance in high-dimensional Hilbert space, this distance can be calculated implicitly in low-dimensional input space by the kernel function K, but with the same effect. It can reduce the computational effort significantly and avoid a large number of calculations. A nonlinear classification problem is one of the classical machine learning problems, and kernel methods can effectively handle such problems. Recall that in classical kernel methods, such as support vector machine, a data point xi ∈ Rn is mapped into a potentially much higher dimensional feature space Fc via a nonlinear mapping function fc, where xi is represented by ϕ(xi), i.e., fc : xi → ϕ(xi). In space Fc, the nonlinear classification problem becomes a linear classification problem and simplifies the problem. The inner product of ϕ(xi)Tϕ(xj) is often seen as distances between xi and xj in the new space Fc. Quantum Kernel. The quantum kernel method is a kernel method designed to run on quantum computers based on quantum computing properties. Its principle is almost identical to the classical kernel method except that it maps the data point from the original input space O to the quantum Hilbert space Fq , i.e., fq : O → Fq . The key to the quantum kernel methods is the quantum mapping function fq . We can view the feature mapping function fq as the key to define the quantum kernel methods. Thus, if the quantum kernel approach is superior, the superiority lies in the quantum mapping function. The mechanism of quantum kernel methods is basically the same as that of classical kernel methods. The data point xi is mapped from the original input space O to the quantum state space Fq , i.e., fq : xi → |ϕ(xi)⟩, where the |·⟩ denotes a vector and physically it represents a state of some quantum system. The ⟨·| is the Hermitian Conjugate of the vector |·⟩. In practice, the feature map is realized by acting the circuit U(xi) on the initial quantum state |0n⟩, i.e.,
|ϕ(xi)⟩ = U(xi) |0n⟩ . (1)
The quantum kernel can be obtained by running the circuit U†(xj)U(xi) on the initial quantum state |0n⟩, where U† is the Hermitian conjugate of U . Then estimate | ⟨0n|U†(xj)U(xi) |0n⟩ |2 by counting the frequency of the 0n output as a value of k(xi, xj). Fig.1A shows the process flow of the quantum kernel method and classical kernel method.
Quantum Kernel Method Based On Pauli Feature Map. Following the IBM quantum computing platform, we take two qubits as an example. The general expression of a 2-qubit quantum kernel is
k(xi, xj) = | ⟨ϕ(xi)|ϕ(xj)⟩ |2 = | 〈 02 ∣∣U†(xj)U(xi) ∣∣02〉 |2. (2)
By the definition of Havlı́ček et al. (2019), the quantum circuit U is realized by U(x⃗) = Uϕ(x⃗)H ⊗ 2Uϕ(x⃗)H ⊗ 2, where the ⊗ is the Kronecker Product of two matrices. For the Secondorder Pauli-Z evolution circuit, Uϕ(x⃗) = exp(i(x0Z0 + x1Z1 + (π − x0)(π − x1)Z0Z1)), where Z0, Z1 are quantum Z-Gates, and H is the quantum Hadamard-Gate. We denote the corresponding quantum kernel method as the Z-ZZ quantum kernel method, and the corresponding feature map is showed in Fig.1B(3). The feature maps of the Z quantum kernel method and the ZZ quantum kernel method are shown in Fig.1B(1) and Fig.1B(2), respectively. In this paper, all references to quantum kernel methods refer to the Z-ZZ quantum kernel method unless otherwise stated. In section 4.3, we compare these three quantum kernel methods.
Support Vector Machine. Support Vector Machine is a maximal margin classifier. It is seen as one of the most successful cases of the kernel approach. SVMs are dedicated to finding a hyper-plane that separates different classes and makes the margin as large as possible. In general cases, i.e., nonlinear cases, the data is mapped non-linearly to high dimensional Hilbert space by a mapping function. Then the distance between two data points can be calculated using the kernel function. Suppose we have a set of data points D = {(x1, y1), · · · , (xn, yn)}, where xi ∈ Rd and yi ∈ {−1,+1}. According to Burges (1998b), the nonlinear SVM can be modified and expressed by an optimization problem as maximize:
LD ≡ n∑ i αi − 1 2 n∑ i,j=0 αiαjyiyjk(xi, xj) (3)
s.t. 0 ≤ αi ≤ C and ∑n i αiyi = 0, where i = 1, · · · , n. The decision function is
f(x) = sign( Ns∑ i=1 αiyiϕ(si) Tϕ(x) + b) = sign( Ns∑ i=1 αiyik(si, x) + b), (4)
where si are the support vectors and Ns is the number of support vectors. The SVM-based quantum kernel method is very similar in principle to the traditional SVM, except that the computation of the kernel is performed on a quantum computer. Havlı́ček et al. (2019) refer to it as quantum kernel estimation. We show the specific estimation method in Section 4.2.

heading: 3 METHODS

heading: 3.1 QUANTUM KERNEL IS A PROBABILISTIC KERNEL
text: The kernel function is an equation for measuring similarity. In vector space, we estimate the similarity of vectors utilizing vector kernel functions. Similarly, graph kernels describe the similarity of two graphs, and tree kernels compare the similarity of trees, which are often used in natural language
processing. A question arises as to how to define kernels or what kind of kernel functions can be effectively used or not. There is no answer to this question. Mercer (1909) argues that a valid kernel function needs to satisfy symmetry and positive definiteness. However, some kernel functions that do not obey Mercer’s condition still achieve good results in some specific tasks, such as the widely used sigmoid kernel function proposed by Lin & Lin (2003). Mix kernel function proposed by Smits & Jordaan (2002) tries to achieve better properties when combining different kernel functions.
The mechanism of the quantum kernel function is similar to some traditional kernel functions. It follows the Mercer theorem and is a practical kernel function that expands the family of kernel functions. However, its implementation is based on quantum superposition states and entanglement. Since the values obtained are based on probabilities in a statistical sense, we call it a probabilistic kernel function. For correspondence, we call the classical kernel function a deterministic kernel function. We try to clearly show the relationship and difference between different kernel functions by a diagram (Fig.2). It is worth noting that there are no guarantees for one kernel to work better than the other in all cases, according to the No Free Lunch Theorem (Wolpert & Macready (1997)). Choosing different kernel functions in various subjects will achieve better results. The primary purpose of this paper is to investigate under what circumstances the quantum kernel method is better or worse than the classical kernel method.

heading: 3.2 THE PROPOSED PATTERNS AND CRITERIA FOR JUDGING QKM
text: First, we would like to demonstrate the advantages of quantum kernel methods over classical kernel methods when dealing with data patterns based on the Mersenne Twister random distribution. The Mersenne Twister is a pseudo random number generator which was first proposed by Matsumoto & Nishimura (1998). The Mersenne Twister is used as default pseudo random number generator by many software, such as Python, R, and PHP. The Mersenne Twister random distribution is a distribution that be generated by the Mersenne Twister method.
Theorem 3.1 (Advantages of QKM for random distributions) In two dimensions, the Z-ZZ quantum kernel method has better learning ability than classical kernel methods for randomly distributed data patterns based on Mersenne Twister.
Proof. We assume that the Z-ZZ feature map can effectively simulate the efficacy of the feature map proposed by Liu et al. (2021). By Matsumoto & Nishimura (1998), for a k-bits binary number, the Mersenne Twister algorithm generates discrete uniformly distributed random numbers in the range [0, 2k − 1]. Solving this problem is a discrete logarithm problem (DLP). For DLP, Liu et al. (2021) say no efficient classical algorithm can achieve inverse-polynomially better accuracy than random guessing. Therefore, the Z-ZZ quantum kernel method can demonstrate quantum superiority over the classical kernel methods for Mersenne Twister-based randomly distributed data patterns.
Second, we demonstrate that whether quantum kernel methods have quantum advantages is related to the δ of the data set, where δ will be defined in Equ.(7). Because any classification problem can be transformed into a binary situation, we all base our study on the binary classification problem. If the distance between classes is large enough, i.e., the simple case, the quantum kernel methods are not as good as the classical kernel methods. Based on fourteen Adhoc-Modify datasets (Section 4.1 Qiskit package datasets (6)), we measure the δ of each dataset and draw a graph with δ as the horizontal coordinate. Fig.3 shows that when δ increases to a certain level, the advantage of the quantum kernel method disappears.
To measure the degree of separation of two classes Cl and Cm, we first define the inter-class distance
D(Cl, Cm) = 1
NlNm Nl∑ k=1 Nm∑ j=1 d(x (l) k , x (m) j ), (5)
where Nl and Nm are the number of observations belonging to class Cl and Cm, respectively. The x (l) n is the n-th sample in class Cl and d(, ) is the euclidean distance between two samples, i.e.,
d(x⃗, y⃗) = √∑n
i=1(xi − yi)2. For the sake of uniformity, we also need to define the intra-class distance for class C, i.e.,
D(C) = 1
N(N − 1) N∑ k=1 N∑ j=1,j ̸=k d(xk, xj), (6)
where the N is the of class C, and xn is the n-th sample in class C. We propose a criterion to evaluate whether quantum kernel methods will be better than classical kernel methods. In a binary classification problem, we define the degree of integration of Cl and Cm as δlm.
δlm = D(Cl, Cm)
D(Cl) +D(Cm) (7)
Theorem 3.2 illustrates that the larger the δ, the greater the separation of the two classes. When the delta is large enough, the quantum kernel function loses its quantum advantage.
Theorem 3.2 (Deficiencies of the QKM) In the case of a balanced number of the two classes, there exists δ0 such that the quantum kernel method will not be better than the classical kernel method in handling classification problems when δ > δ0. In practice, δ0 is usually taken as 0.6.
Proof. Suppose our measurement independent identical distribution M1,M2 · · ·MR which have expectation E(M) = µ and variance D(M) = σ2, where M is the random variable, R is the number of measurement shots. By the Central Limit Theorem, for any m, the distribution function FR(m) = P{ ∑R i=1 Mi−RE√
DR ≤ m} satisfies: limR→∞ FR(x) = limR→∞{
∑R i=1 Mi−RE√
RD ≤ x} =
1√ 2π ∫m −∞ e − t22 dt. This shows that when R is large enough, the random variable YR = ∑R i=1 Mi−RE√ RD
obeys normal distribution N(0, 1). So, ∑R i=1 Mi = √ RDYR+RE = √ RσYR+Rµ obeys normal distribution N(Rµ,Rσ2). However, even fully error corrected, the quantum methods still have the noise caused by measurement. Two types of data are linearly separable or almost linearly separable when D(Cl, Cm) ≫ D(Cl) +D(Cm), i.e., δ ≫ δ0. It is easy for a deterministic kernel method to find a boundary line with an infinitely small error. So, when δ > δ0, the quantum kernel method is not better than the classical kernel method in handling classification problems.
In fact, as a probabilistic kernel method, a quantum kernel method has more error than a deterministic kernel method caused by the measurement process. It is especially evident in some simple cases because we assume that deterministic kernel methods must find a boundary line. However, errors in probabilistic methods are inevitable.

heading: 4 EXPERIMENTS

heading: 4.1 DATA PREPARATION
text: Qiskit package datasets. Five datasets from qiskit.ml.datasets were used in the experiments. (1) Digits datasets. This dataset consists of 1797 8×8 images, and each image is a handwritten number
0∼9. We perform binary classification for every two digits. Thus, 45 small datasets were generated. (2) Breast cancer dataset. (3) Iris dataset. (4) Wine dataset. (5) Adhoc dataset. Note that (1)∼(4) are copies from UCI ML Hand-written Digits Dataset, UCI ML Breast Cancer Wisconsin (Diagnostic) Dataset, UCI ML Iris Plants Dataset, and UCI ML Wine Recognition Dataset, respectively. For (5) Adhoc dataset, we separate the two classes and translate all the data points in one class by the same distance, leaving the other class unchanged. In this way, we get 14 datasets, denoted as (6) Adhoc-Modify datasets.
Kaggle datasets. Five datasets from Kaggle were used in the experiments. (7) Email spam dataset (Balaka Biswas), (8) Heart disease dataset (Zeeshan Mulla). (9) Giants and dwarfs dataset (Vinesmsuic). (10) Star type dataset (Baris Dincer). (11) Drug dataset (Pratham Tripathi).
Geometric toy datasets. We designed the two-dimensional geometric toy datasets to illustrate the learning ability of the quantum kernel method for processing classification problems in geometric patterns. (12) Geometric non-random datasets. We designed 2∼5 layers of concentric circles and four squares with different mixing degrees. Fig.4A shows the four circular datasets and four square datasets. (13) Geometric random datasets. Based on the Mersenne Twister random distribution, we designed datasets with random distributions in three geometric patterns: Circular, square, and equilateral triangle patterns. The three graphs on the right side of Fig.4B show a sample of these three datasets, respectively.

heading: 4.2 PROCESS OF TRAINING AND TESTING OF QUANTUM KERNEL METHODS
text: We briefly introduce the training process of the quantum kernel method here, following the idea of Liu et al. (2021). Suppose a training dataset Dtrain = {(x1, y1), ..., (xn, yn)}. Since the only difference of the quantum kernel method in an SVM from the classical SVM is kernel calculation, here we only show the kernel calculation process in a quantum computer.
Training: For each pair of data points xi and xj (i ̸= j) in Dtrain, we apply U†(xi)U(xj) on the input ∣∣0⊗ 2〉. After R repetitive runs, we record the number of times the output results in ∣∣0⊗ 2〉, denoted as R0 and k(xi, xj) = R02R , where i ̸= j and k(xi, xi) = 1. In the end, we apply Equ.(3) directly. Testing: When there comes a new sample xnew, for each data point xi in Dtrain, we apply U†(xi)U(xnew) on the input
∣∣0⊗ 2〉. After R repetitive runs, we record the number of times the output results in
∣∣0⊗ 2〉, denoted as R1 and k(xnew, xi) = R1+2R2R . In the end, we apply Equ.(4) directly.

heading: 4.3 EXPERIMENTS RESULTS
text: The quantum kernel method is good at complex data patterns. In this part, we explore the ability of quantum kernel methods to solve classification problems under challenging patterns. Firstly, we increase the learning difficulty by increasing the complexity of the geometric patterns and get four patterns, i.e., P1∼P4 in Fig.4A. Experiments show that from P1 to P4, the classical kernel approach, which initially performs better, gradually loses its superiority. In contrast, the superiority of the quantum kernel approach begins to emerge.
To further increase the learning difficulty, we hypothesized the existence of a pattern in which the data are randomly distributed over the geometry according to the Mersenne Twister. The right three graphs in Fig.4B show this kind of data pattern. To explore the learning ability of quantum kernel methods for Mersenne Twister randomly distributed data patterns, we plotted the relationship between the size of the dataset and the prediction accuracy of each method. Considering the randomness of the random distribution, we take the average result of 50 times as the result of each experiment. The experiments demonstrate that the quantum kernel method has a more robust learning capability than the classical kernel method in this complex pattern.
The quantum kernel method fails at large values of δ. In this part, we will show that our criteria can effectively determine whether quantum kernel methods can demonstrate advantages over classical kernel methods or not. First, taking the Digits dataset as an example, we perform binary classification for every two digits. Thus, we generate 45 small datasets. We then use PCA to reduce the dimensionality of all data to 2 dimensions, as shown in Fig.5. We recorded each small dataset’s training and test accuracy after applying four classical kernel methods and a quantum kernel method. The bottom left panel in Fig.5 shows the prediction accuracy of each method. According to the experimental results, we attach a corner mark to each data set. The red rounded corner markers indicate that the quantum kernel method has the potential for quantum dominance on the corresponding dataset, while the black rounded corner markers indicate that it does not. The blue corner markers indicate that the quantum kernel method is indistinguishable from the classical kernel method. Intuitively, the quantum kernel approach for linearly divisible data sets does not show superiority. However, for complex models with relatively high fusion, the quantum kernel approach has the potential to be superior.
To validate our criteria δ, we prepared 81 datasets: 45 small datasets from Digits, 14 datasets from Adhoc-Modify, Breast cancer, Iris, Wine, Email spam, Heart disease, Giants and dwarfs, Star Type, Drug, 4 datasets from Geometric non-random, i.e., the top-left, bottom-left, top-right and bottomright four datasets in Fig.4A, 10 datasets from Geometric random including five circles of size thirty and five squares of size forty. The difference in prediction accuracy between classical kernel methods
and quantum kernel methods on each dataset is calculated. It is shown by the relevant vertical lines in Fig.6. The magnitude of δ on each dataset is shown with an asterisk in Fig.6. According to the experiments, when the quantum kernel method has an advantage, the asterisks appear below the 0.6 level line all the time. We can get the conclusion that (i) the availability of quantum superiority correlates with δ and (ii) the quantum kernel method can be better than the classical kernel method when δ < 0.6, although it is not a sufficient condition.
Simple quantum kernel methods do not offer quantum advantages. When the feature space is so large that the kernel function is computationally expensive, quantum kernel methods can effectively estimate their kernel functions, but classical kernel methods cannot. So, quantum kernel methods are preferred over classical kernel methods for classification problems with complex patterns. However, a simpler quantum kernel function can be simulated classically. For a simple-kernel-based quantum kernel method, it no more has the superiority. Its ability to handle complex pattern problems is significantly reduced and even inferior to classical kernel methods. Interestingly, sometimes this simple quantum kernel function works well with simple pattern problems.
We illustrate the above opinion experimentally. In this part, we prepared 68 datasets: 45 small datasets from Digits, Breast cancer, Iris, Wine, Adhoc, Email spam, Heart disease, Giants and dwarfs, Star Type, Drug, 4 datasets from Geometric non-random, i.e., the top-left, bottom-left, top-
right and bottom-right four datasets in Fig.4A, 10 datasets from Geometric random including five circles of size thirty and five squares of size forty. By comparing the performance of the best classical kernel method and the three quantum kernel methods on 68 training datasets, we find that some kernel methods based on simple quantum kernel functions, such as the Z quantum kernel method, do outperform the Z-ZZ kernel method on some datasets, but do not outperform the best classical kernel methods. However, when quantum superiority exists, it is often achieved by Z-ZZ kernel methods. The experiments show that the quantum kernel method superiority on only one dataset is achieved by the Z quantum kernel method.

heading: 5 CONCLUSION
text: The classification problem is one of the most common problems in machine learning, and both classical kernel methods and quantum kernel methods can effectively handle the classification problem. However, it is difficult to determine what situation each of them is suitable for. This paper explores when quantum kernel methods can take quantum advantage by comparing different kernel functions. Moreover, a judgment criterion is proposed to help one decide when quantum kernel methods can achieve better results than classical kernel methods. Experiments show that our method is effective.

Review summaries:
The paper investigates the circumstances under which quantum kernel methods will be superior to classical kernel methods.  The criteria is based on a threshold of the ratio of the inter- and intra-class distances of the (binary) training data.  Validation of the proposed criteria is carried out on a range of toy and real datasets.

This article studies the superiority of quantum kernel methods over classical kernel methods. The authors relate the quantum advantages for classification tasks to the separation between the classes.  Several numerical simulations were conducted to support the theoretical findings. 

This paper studies quantum kernel methods for classification problems. It compares the differences between quantum kernel functions and classical kernel functions. A degree of integration and two theorems are proposed. Some empirical experiments are done on the datasets from Qiskit and Kaggle.