# Quantum-Based Feature Selection for Multiclassification Problem in Complex Systems with Edge Computing

Authors: Wenjie Liu; Junxiu Chen; Yuxiang Wang; Peipei Gao; Zhibin Lei; Xu Ma
Journal: Complexity
 (2020)

---

## Abstract

The complex systems with edge computing require a huge amount of multifeature data to extract appropriate insights for their decision making, so it is important to find a feasible feature selection method to improve the computational efficiency and save the resource consumption. In this paper, a quantum-based feature selection algorithm for the multiclassification problem, namely, QReliefF, is proposed, which can effectively reduce the complexity of algorithm and improve its computational efficiency. First, all features of each sample are encoded into a quantum state by performing operations CMP andRy, and then the amplitude estimation is applied to calculate the similarity between any two quantum states (i.e., two samples). According to the similarities, the Grover–Long method is utilized to find the nearest k neighbor samples, and then the weight vector is updated. After a certain number of iterations through the above process, the desired features can be selected with regards to the final weight vector and the threshold τ. Compared with the classical ReliefF algorithm, our algorithm reduces the complexity of similarity calculation from O(MN) to O(M), the complexity of finding the nearest neighbor from O(M) to OM, and resource consumption from O(MN) to O(MlogN). Meanwhile, compared with the quantum Relief algorithm, our algorithm is superior in finding the nearest neighbor, reducing the complexity from O(M) to OM. Finally, in order to verify the feasibility of our algorithm, a simulation experiment based on Rigetti with a simple example is performed.


---

## Body

## 1. Introduction

Complex systems [1] are nonlinear systems composed of agents that can act with local environmental information, which require big data to extract appropriate insights for their decision making. In the cloud computing [2–5], the data transmission delay between the data sources and the cloud centers is problematic for many complex systems where responses are usually required to be time critical or real time. Instead, a recently emerging computation paradigm, edge computing [6–9], is promising to cater for these requirements, as edge computing resources are deployed data sources which support time critical or real-time data processing and analysis. As we all know, the computing resources and storage resources of most intelligent terminals are very limited, which places higher requirements on the computing performance of algorithms, especially machine learning algorithms, in complex systems with edge computing.Machine learning [10, 11] continuously improves its performance through “experience,” where experience generally originates from massive data. At present, many machine learning algorithms based on massive data [12–14] have been proposed. In the practical scenario, the amount of data available for training is getting larger and larger, while the characteristics of data are becoming more and more abundant. Those data with redundant or unrelated features will cause the problem of “curse of dimensionality” [15], which greatly increases the computational complexity of the algorithm. One of the possible solutions is the dimension reduction [16], and the other is the feature selection [17].Relief algorithm [18] is a well-known feature selection algorithm for the two-classification problem. It is widely used because of its excellent classification effect. However, the limitation of this algorithm is that it can only perform the binary classification, and the efficiency of the algorithm will be greatly affected when the data size and feature size increase. To extend the application of the algorithm, Kononenko [19] proposed a new feature selection algorithm for the multiclassification problem, namely, ReliefF algorithm. It has the advantages of simple principle, convenient implementation, and good results and has been widely applied in various fields [20–22].On the other hand, since Benioff [23] and Feynman [24] explored the theoretical possibilities of quantum computing, some excellent results have been proposed one after another. For instance, Shor’s algorithm [25] solves the problem of integer factorization in polynomial time. Grover’s algorithm [26] has a quadratic speedup to the problem of conducting a search through some unstructured database. These excellent results have prompted people to think about how to apply this computing power into machine learning algorithms. Thus, a new research hotspot, quantum machine learning [27–32], has gradually formed. Although quantum technology provides a certain improvement in storage and computing power, the “curse of dimensionality” problem still exists in quantum machine learning. Therefore, the quantum-based dimensionality reduction method still has important research value. In 2018, Liu et al. [33] proposed a quantum Relief algorithm (namely, QRelief algorithm) for the two-classification problem, which reduces the complexity of similarity calculation from O(MN) to O(M).As we know, in the application scenario of edge computing, there are various multiclassification problems based on distributed, massive, and large-feature data. The objective of this study is to design a feasible feature selection method which can effectively get rid of redundant or unrelated features in machine learning, reducing the computation load of intelligent terminals, and thus meet the requirement of real-time data processing and analysis in edge computing. In this paper, we introduce some quantum technologies (such as CMP operation, amplitude estimation, and Grover–Long method) and propose a quantum-based feature selection algorithm, namely QReliefF algorithm, for the multiclassification problem.The main contributions of our work are as follows:(1)
A quantum method is proposed to solve the problem of feature selection for the multiclassification problem in complex systems with edge computing. The proposed method fully demonstrates the quantum parallel processing capabilities that classical computing cannot match and significantly reduces the computational complexity of the algorithm.(2)
The problem of finding nearest neighbor samples is firstly transformed into the similarity calculation of two quantum states (i.e., calculating their inner product) in quantum computing, and the Grover–Long method is utilized to speed up the search of the targets.(3)
A simulation experiment based on Rigetti is performed to verify the feasibility of our algorithm.The outline of this paper is as follows. The classic ReliefF algorithm is briefly reviewed in Section2, and the proposed quantum ReliefF algorithm is proposed in detail in Section 3. Then, we illustrate the process of the algorithm with a simple example in Section 4 and perform the simulation experiment on Rigetti in Section 5. Subsequently, the efficiency of the algorithm is analyzed in Section 6, and the brief conclusion and discussion are summarized in the last section.


## 2. Review of ReliefF Algorithm

ReliefF algorithm [19] is a feature selection algorithm which is used to handle the multiclassification problem. Before introducing our proposed quantum algorithm, let us review the detailed process of the algorithm.Without loss of generality, suppose there areM samples with N features, and they can be divided into P classes:(1)Cp=vqvq∈ℝN,q=1,2,…,Mp,p∈1,2,…,P,where vq is the q-th N-feature sample that belongs to Class Cp, vq=vq1,vq2,…,vqNT. And the weight vector of N features WT=wt1,wt2,…,wtNT is initialized to all zeros, the upper limit of iteration is T, and the relevance threshold (that differentiates the relevant and irrelevant features) is τ (0 ≤ τ ≤ 1). The main steps of ReliefF algorithm are as follows (its pseudocode can be seen in Algorithm 1).Algorithm 1: ReliefF algorithm.
(1)
Init WT = (0, …, 0)T
(2)
for
t = 1 toTdo
(3)
Pick a sample u randomly
(4)
Find k nearest neighbor samples Hj from the same class of sample u
(5)
forCp ≠ class(u) do
(6)
Find k nearest neighbor samples Mj(Cp) from the different Class Cp
(7)
end
(8)
fori = 1 toNdo
(9)
WTi=WTi−∑j=1kdiffi,u,Hj+∑Cp∉classupCp/1−pclassu∑j=1kdiffi,u,MjCp
(10)
end
(11)
end
(12)
Select the most relevant features according to WT and τAt each iteration, ReliefF randomly selects a sampleu and then searches for k nearest neighbor samples by cosine distance from each class. The closest same-class sample is called Hj, and the closest different-class sample is called Mj(Cp), where j = {1, 2, …, k}. The updating weight vector formula is shown as follows:(2)WTi=WTi−∑j=1kdiffi,u,Hj+∑Cp∉classupCp1−pclassu∑j=1kdiffi,u,MjCp,where p(Cp) represents the probability of randomly extracting samples of Class Cp, and the definition of diffi,u,v function is as follows:(3)diffi,u,v=ui−vimaxi−mini,iis continuous,0,ui=vi,1,ui≠vi.After iteratingT times, the final weight vector is obtained. Through the relevance threshold τ, we can retain relevant features and discard irrelevant features.ReliefF algorithm is an extension of Relief algorithm that extends the two-classification problem to multiclassification scenario. However, with the increase of category size, sample size, and sample features, ReliefF algorithm will also face with the problem of “dimension disaster,” and the speed of the algorithm will also drop sharply. So, how to improve the efficiency of ReliefF algorithm becomes an urgent problem to be solved.


## 3. The Proposed QReliefF Algorithm

In order to implement the feature selection for the multiclassification problem in complex systems with edge computing, a feasible quantum ReliefF algorithm is introduced in this section. Suppose the sample setsCp=vq=vq1,vq2,…,vqNTvq∈ℝN,q=1,2,…,Mp (p represents the category of classification, p∈1,2,…,P), the weight vector WT, the upper limit T, and the relevance threshold τ are the same as classical ReliefF algorithm defined in Section 2. Different from the classical one, all the features of each sample are represented as a quantum superposition state, and thus the problem of finding nearest neighbor samples is transformed into the similarity calculation of two quantum states (i.e., calculating their inner product). And the similarity between any two samples can be calculated in parallel in the way of quantum mechanics. Algorithm 2 describes the process of our algorithm in detail, and the specific steps are as follows.Algorithm 2: Quantum ReliefF algorithm.
(1)
Init WT = (0, …, 0)T
(2)
Normalized the sample sets: Cp⟶C¯p
(3)
Prepare quantum states for all samples by operations CMP and Ry, respectively. ϕpq=1/Nq∑i=0N−1i11−v¯qi20+v¯qi1
(4)
for
t = 1 toTdo
(5)
Select a state |ϕ〉 from ϕpq randomly which corresponds to u
(6)
Perform swap operation on |ϕ〉 and obtain φ=1/Nl∑i=0N−1i1−u¯i20+u¯i11
(7)
The similarity information coded into quantum state βp=1/Mp∑q=1Mpqv¯q−u¯ through swap test, the inner product and amplitude estimation operations
(8)
The nearest k samples in each class are obtained by Grover-Long method
(9)
fori = 1 toNdo
(10)
WTi=WTi−∑j=1kdiffi,u¯,Hj+∑C¯p∉classu¯pC¯p/1−pclassu¯∑j=1kdiffi,u¯,MjC¯p
(11)
end
(12)
end
(13)
WT
¯
=
1
/
T
WT
(14)
for
i = 1 toNdo
(15)
if WTi¯≥τ then
(16)
The i-th feature is relevant
(17)
else
(18)
The i-th feature is not relevant
(19)
end
(20)
end


### 3.1. State Preparation

In order to store classical information in quantum states, we need to normalize the sample sets:(4)Cp⟶C¯p=v¯q=v¯q1,v¯q2,…,v¯qNT,where(5)v¯qi=vqi∑i=1Nvqi2,i=1,2,…,N.Obviously,v¯qi is a real number, and v¯qi∈0,1. Then, we prepare the initial quantum states as below:(6)ϕpq=1Nq∑i=0N−1i11−v¯qi20+v¯qi1,where ϕpq corresponds to the quantum state of the q-th sample that belongs to Class C¯p and v¯qi represents the i-th eigenvalue of the q-th sample. Assume our initial state is q0⊗n10n=⌈log2N⌉; the construction scheme of the quantum state ϕpq includes the following steps.First, we perform Hadamard and CMP operations for |0〉⊗n and get a new state:(7)0⊗n⟶Hand CMP operations1N∑i=0N−1i,and its circuit diagram is shown in Figure 1, where the definition of CMP operation is(8)CMPiN0=iN0,i<N,iN1,i≥N.Figure 1
Quantum circuit of getting1/N∑i=0N−1i; H is the Hadamard operation and ○ represents the control qubit conditional being set to zero.The function of CMP operation is to cut the quantum state larger thanN, and its circuit diagram is shown in Figure 2. |i〉 and |N〉 represent a single qubit. The implementation of CMP operation needs to repeatedly implement such a circuit n times. After measurement, if the lowest register is |1〉, it means that i > N.Figure 2
Quantum circuit of CMP operation; • represents the control qubit conditional being set to one.Next, we perform the unitary rotation operationRy:(9)Ry2sin−1v¯qi=1−v¯qi2−v¯qiv¯qi1−v¯qi2,on the last qubit to obtain our target quantum state ϕpq:(10)1Nq∑i=0N−1i11−v¯qi20+v¯qi1.


### 3.2. Similarity Calculation

After the state preparation, the information of the samples is encoded into the quantum superposition stateϕpq. In this paper, we use the cosine distance to define the similarity between the random sample ū and other sample (e.g., v¯q):(11)su¯,v¯q=˙cosθ2=u¯v¯q2u¯2⋅v¯q2.Referring to equations (4) and (5), u¯2 and v¯q2 are 1, and equation (11) can be simplified as follows:(12)su¯,v¯q=u¯v¯q2.First, |ϕ〉 (i.e., the sample ū) is randomly selected from ϕpq which is the l-th sample in Class C¯p, as shown in the following equation:(13)ϕ=1Nl∑i=0N−1i11−u¯i20+u¯i1.Then, a swap operation is performed on |ϕ〉 to get(14)φ=1Nl∑i=0N−1i1−u¯i20+u¯i11.Next, aswap test (its circuit is given in Figure 3) is performed on φ,ϕpq, and we obtain(15)ψ=120φϕpq+ϕpqφ+121φϕpq−ϕpqφ.Figure 3
Quantum circuit ofswap test operation; the symbol of two crosses connected by a line represents the swap operation.From equation (15), we know the probability of measurement result being |1〉 is(16)Pql1=ψ11⊗I⊗Iψ=121φϕpq−ϕpqφ11⊗I⊗I=121φϕpq−ϕpqφ=12−12φϕpq2.In addition, the inner product between |φ〉 and ϕpq (i.e., the prepared state) can be calculated as follows:(17)φϕpq=1N∑iu¯i∗v¯qi=1Nu¯v¯q.Combining equation (16) with equation (17), we can get the similarity between samples ū and v¯q:(18)su¯,v¯q=1−2PqlC¯p1N2.SinceN is a constant value and u¯v¯q is the angle cosine between the random sample ū and other sample v¯q (e.g., in Class C¯p), then the smaller su¯,v¯q is, the smaller cosine distance is, which indicates that these two samples are more similar.Then, we can rewrite equation (15) as follows:(19)αp=1Mp∑q=1Mpq1−su¯,v¯q0+su¯,v¯q1.


### 3.3. Finding the Nearest Neighbor Samples

First, the quantum amplitude estimation method [34] is applied to store the similarity of the sample ū and v¯q in the last qubit:(20)βp=1Mp∑q=1Mpqsu¯,v¯q,where p∈1,2,…,P, and its quantum circuit diagram is given in Figure 4.Figure 4
Quantum circuit of amplitude estimation operation; GJ represents J iterations of Grover–Long method [35] and FM−1 represents the inverse Fourier transform [36].In the Grover–Long method [35], one iteration can be divided into four operations, i.e., G = −WI0W−1O, and its quantum circuit is shown in Figure 5. O is an oracle operation which performs a phase inversion on the targets:(21)O=eiϕvv+∑τ=0,τ≠v2n−1ττ,where v is the position of eiϕ in the diagonal matrix. The position v of eiϕ is divided into two cases. If v is odd, the u1(ϕ) operation will be applied to the lowest qubit:(22)u1ϕ=diag1,eiϕ.Figure 5
Quantum circuit with one iteration in Grover–Long method [35]; q0 denotes the highest qubit and qn−1 denotes the lowest qubit.Ifv is even, X, u1(ϕ), X operations will be applied to the lowest qubit.Besides,I0 is a conditional phase shift operation which performs a phase inversion on |0〉:(23)I0=eiϕ00+∑τ=12n−1ττ=diageiϕ,1,…,12n,ϕ=2arcsinsinπ/4J+2sinη,where sinη=M/N and J represents the number of iteration.Having obtained the state |β〉p (see equation (20)) through the amplitude estimation, we introduce a quantum minimum search algorithm [37] to find k nearest neighbor samples from Class C¯p with the time complexity of OkMp, and its quantum circuit is shown in Figure 6.Figure 6
Quantum circuit of findingk nearest neighbor samples.Suppose the setK=K1,K2,…,Kk represents the k nearest neighbor samples, we should prepare ⌈k⌉ auxiliary qubits. As shown in Figure 6, the operator Ws represents Ws|β〉p|0⊗k〉 = |β〉p|K1〉|K2〉⋯|Kk〉, and u1(ϕ) is the operator defined in equation (22). Let d0=su¯,v¯1; we can mark Kx when d0>su¯,v¯Kx,x∈1,k. Next, we can replace d0 after one iteration, where d0 is minsu¯,v¯Kx, x ∈ [1, k]. We repeat the above steps several times until all samples in Class C¯p are compared. Finally, all index of k nearest neighbor samples in Class C¯p can be obtained according to the similarity.


### 3.4. Updating Weight Vector

After the above steps, we obtain the nearest neighbor samples (i.e.,Hj and MjC¯p) of the random sample ū. Then, we update the weight vector according to the updating weight vector formula as follows:(24)WTi=WTi−∑j=1kdiffi,u¯,Hj+∑C¯p∉classu¯pC¯p1−pclassu¯∑j=1kdiffi,u¯,MjC¯p,where i ∈ [1, N].


### 3.5. Feature Selection

After iterating the above steps, i.e., similarity calculation, we find the nearest neighbor samples and update weight vectorT times, and we jump out of the algorithm’s loop. Then, we get a final weight vector WT. And the average weight vector is(25)WT¯=1TWT.Then, we make feature selection based on the finalWT¯ and threshold τ. Here, τ can be chosen to retain relevant features and discard irrelevant features [38], that is to say, those features whose weight is greater than τ will be selected, and those less than τ will be discarded. Here, the value of τ is determined with regards to the user’s requirements and the characteristics of the problem itself (e.g., the distribution of samples and the number of features).


## 3.1. State Preparation

In order to store classical information in quantum states, we need to normalize the sample sets:(4)Cp⟶C¯p=v¯q=v¯q1,v¯q2,…,v¯qNT,where(5)v¯qi=vqi∑i=1Nvqi2,i=1,2,…,N.Obviously,v¯qi is a real number, and v¯qi∈0,1. Then, we prepare the initial quantum states as below:(6)ϕpq=1Nq∑i=0N−1i11−v¯qi20+v¯qi1,where ϕpq corresponds to the quantum state of the q-th sample that belongs to Class C¯p and v¯qi represents the i-th eigenvalue of the q-th sample. Assume our initial state is q0⊗n10n=⌈log2N⌉; the construction scheme of the quantum state ϕpq includes the following steps.First, we perform Hadamard and CMP operations for |0〉⊗n and get a new state:(7)0⊗n⟶Hand CMP operations1N∑i=0N−1i,and its circuit diagram is shown in Figure 1, where the definition of CMP operation is(8)CMPiN0=iN0,i<N,iN1,i≥N.Figure 1
Quantum circuit of getting1/N∑i=0N−1i; H is the Hadamard operation and ○ represents the control qubit conditional being set to zero.The function of CMP operation is to cut the quantum state larger thanN, and its circuit diagram is shown in Figure 2. |i〉 and |N〉 represent a single qubit. The implementation of CMP operation needs to repeatedly implement such a circuit n times. After measurement, if the lowest register is |1〉, it means that i > N.Figure 2
Quantum circuit of CMP operation; • represents the control qubit conditional being set to one.Next, we perform the unitary rotation operationRy:(9)Ry2sin−1v¯qi=1−v¯qi2−v¯qiv¯qi1−v¯qi2,on the last qubit to obtain our target quantum state ϕpq:(10)1Nq∑i=0N−1i11−v¯qi20+v¯qi1.


## 3.2. Similarity Calculation

After the state preparation, the information of the samples is encoded into the quantum superposition stateϕpq. In this paper, we use the cosine distance to define the similarity between the random sample ū and other sample (e.g., v¯q):(11)su¯,v¯q=˙cosθ2=u¯v¯q2u¯2⋅v¯q2.Referring to equations (4) and (5), u¯2 and v¯q2 are 1, and equation (11) can be simplified as follows:(12)su¯,v¯q=u¯v¯q2.First, |ϕ〉 (i.e., the sample ū) is randomly selected from ϕpq which is the l-th sample in Class C¯p, as shown in the following equation:(13)ϕ=1Nl∑i=0N−1i11−u¯i20+u¯i1.Then, a swap operation is performed on |ϕ〉 to get(14)φ=1Nl∑i=0N−1i1−u¯i20+u¯i11.Next, aswap test (its circuit is given in Figure 3) is performed on φ,ϕpq, and we obtain(15)ψ=120φϕpq+ϕpqφ+121φϕpq−ϕpqφ.Figure 3
Quantum circuit ofswap test operation; the symbol of two crosses connected by a line represents the swap operation.From equation (15), we know the probability of measurement result being |1〉 is(16)Pql1=ψ11⊗I⊗Iψ=121φϕpq−ϕpqφ11⊗I⊗I=121φϕpq−ϕpqφ=12−12φϕpq2.In addition, the inner product between |φ〉 and ϕpq (i.e., the prepared state) can be calculated as follows:(17)φϕpq=1N∑iu¯i∗v¯qi=1Nu¯v¯q.Combining equation (16) with equation (17), we can get the similarity between samples ū and v¯q:(18)su¯,v¯q=1−2PqlC¯p1N2.SinceN is a constant value and u¯v¯q is the angle cosine between the random sample ū and other sample v¯q (e.g., in Class C¯p), then the smaller su¯,v¯q is, the smaller cosine distance is, which indicates that these two samples are more similar.Then, we can rewrite equation (15) as follows:(19)αp=1Mp∑q=1Mpq1−su¯,v¯q0+su¯,v¯q1.


## 3.3. Finding the Nearest Neighbor Samples

First, the quantum amplitude estimation method [34] is applied to store the similarity of the sample ū and v¯q in the last qubit:(20)βp=1Mp∑q=1Mpqsu¯,v¯q,where p∈1,2,…,P, and its quantum circuit diagram is given in Figure 4.Figure 4
Quantum circuit of amplitude estimation operation; GJ represents J iterations of Grover–Long method [35] and FM−1 represents the inverse Fourier transform [36].In the Grover–Long method [35], one iteration can be divided into four operations, i.e., G = −WI0W−1O, and its quantum circuit is shown in Figure 5. O is an oracle operation which performs a phase inversion on the targets:(21)O=eiϕvv+∑τ=0,τ≠v2n−1ττ,where v is the position of eiϕ in the diagonal matrix. The position v of eiϕ is divided into two cases. If v is odd, the u1(ϕ) operation will be applied to the lowest qubit:(22)u1ϕ=diag1,eiϕ.Figure 5
Quantum circuit with one iteration in Grover–Long method [35]; q0 denotes the highest qubit and qn−1 denotes the lowest qubit.Ifv is even, X, u1(ϕ), X operations will be applied to the lowest qubit.Besides,I0 is a conditional phase shift operation which performs a phase inversion on |0〉:(23)I0=eiϕ00+∑τ=12n−1ττ=diageiϕ,1,…,12n,ϕ=2arcsinsinπ/4J+2sinη,where sinη=M/N and J represents the number of iteration.Having obtained the state |β〉p (see equation (20)) through the amplitude estimation, we introduce a quantum minimum search algorithm [37] to find k nearest neighbor samples from Class C¯p with the time complexity of OkMp, and its quantum circuit is shown in Figure 6.Figure 6
Quantum circuit of findingk nearest neighbor samples.Suppose the setK=K1,K2,…,Kk represents the k nearest neighbor samples, we should prepare ⌈k⌉ auxiliary qubits. As shown in Figure 6, the operator Ws represents Ws|β〉p|0⊗k〉 = |β〉p|K1〉|K2〉⋯|Kk〉, and u1(ϕ) is the operator defined in equation (22). Let d0=su¯,v¯1; we can mark Kx when d0>su¯,v¯Kx,x∈1,k. Next, we can replace d0 after one iteration, where d0 is minsu¯,v¯Kx, x ∈ [1, k]. We repeat the above steps several times until all samples in Class C¯p are compared. Finally, all index of k nearest neighbor samples in Class C¯p can be obtained according to the similarity.


## 3.4. Updating Weight Vector

After the above steps, we obtain the nearest neighbor samples (i.e.,Hj and MjC¯p) of the random sample ū. Then, we update the weight vector according to the updating weight vector formula as follows:(24)WTi=WTi−∑j=1kdiffi,u¯,Hj+∑C¯p∉classu¯pC¯p1−pclassu¯∑j=1kdiffi,u¯,MjC¯p,where i ∈ [1, N].


## 3.5. Feature Selection

After iterating the above steps, i.e., similarity calculation, we find the nearest neighbor samples and update weight vectorT times, and we jump out of the algorithm’s loop. Then, we get a final weight vector WT. And the average weight vector is(25)WT¯=1TWT.Then, we make feature selection based on the finalWT¯ and threshold τ. Here, τ can be chosen to retain relevant features and discard irrelevant features [38], that is to say, those features whose weight is greater than τ will be selected, and those less than τ will be discarded. Here, the value of τ is determined with regards to the user’s requirements and the characteristics of the problem itself (e.g., the distribution of samples and the number of features).


## 4. Example

Suppose that there are four samples(see Table1); S0 = (1, 0, 0, 1, 0, 0), S1 = (1, 0, 0, 0, 1, 0), S2 = (0, 1, 0, 0, 0, 1), S3 = (0, 1, 0, 1, 0, 0), S4 = (0, 0, 1, 0, 1, 0), and S5 = (0, 0, 1, 0, 0, 1), and thus n is 3, and they belong to two classes: A = {S0, S1}, B = {S2, S3}, and C = {S4, S5}, which is illustrated in Figure 7.Table 1
The feature values of four samples.
F
0
F
1
F
2
F
3
F
4
F
5
S
0
1
0
1
0
0
0
S
1
1
0
0
0
1
0
S
2
0
1
0
0
0
1
S
3
0
1
0
1
0
0
S
4
0
0
1
0
1
0
S
5
0
0
1
0
0
1
Each row represents all the feature values of a certain sample, while each column denotes a certain feature value of all the samples.Figure 7
The simple example with six samples in classes A, B, and C.First, the four initial quantum states are prepared as follows:(26)ψS0=0000⊗310,ψS1=0010⊗310,ψS2=0100⊗310,ψS3=0110⊗310,ψS4=1000⊗310,ψS5=1000⊗310.Next, we takeψS0 as an example, and then the H⊗3 operation is applied on the third and fourth qubits:(27)0000⊗310⟶H⊗312000∑i=03i10.Then, we performRy rotation (see equation (9)) on the last qubit, and we can get(28)ϕS0=12000∑i=03i11−v¯0i20+v¯0i1.The other quantum states are prepared in the same way and they are listed as follows:(29)ϕS0=12000∑i=03i11−v¯0i20+v¯0i1,ϕS1=12001∑i=03i11−v¯1i20+v¯1i1,ϕS2=12010∑i=03i11−v¯2i20+v¯2i1,ϕS3=12011∑i=03i11−v¯3i20+v¯3i1,ϕS4=12100∑i=03i11−v¯4i20+v¯4i1,ϕS5=121001∑i=03i11−v¯5i20+v¯5i1.Second, we randomly select a sample (assumeϕS0 is ū) and perform similarity calculation with other samples (i.e., ϕS1, ϕS2, ϕS3, ϕS4, ϕS5). Next, we take ϕS0 and ϕS1 as an example and perform a swap operation between the last two qubits of ϕS0:(30)ϕS0⟶swapφ=12000∑i=03i1−v¯0i20+v¯0i11.After that, theswap test operation is applied on (|φ〉, ϕS1):(31)120φϕS1+ϕS1φ+121φϕS1−ϕS1φ.We perform aswap test operation to obtain a quantum state that encodes similarity in amplitude:(32)αA=12∑q=12q1−su¯,v¯q0+su¯,v¯q1,αB=12∑q=12q1−su¯,v¯q0+su¯,v¯q1,αC=12∑q=12q1−su¯,v¯q0+su¯,v¯q1.Then, through the amplitude estimation, we can obtain the quantum states:(33)βA=12∑q=12qv¯q−u¯,βB=12∑q=12qv¯q−u¯,βC=12∑q=12qv¯q−u¯.Next, we perform an oracle operation on the quantum states obtained in the above steps to obtain thek nearest neighbor samples.


## 5. Simulation Experiment

Quantum Cloud Services (QCSTM) is Rigetti’s quantum-first cloud computing platform. At the end of 2017, a 19-qubit processor named “Acorn” was launched, which can be used in QCS through a quantum programming toolkit named Forest [39]. The chip of “Acorn” is made of 20 superconducting qubits but for some technical reasons, qubit 3 is offline and cannot interact with its neighbors, so it is treated as a 19-qubit device whose coupling map is shown in Figure 8.Figure 8
The coupling map picture: Rigetti’s 19-qubit processor “Acorn.” Lines indicate the two-qubit connection ruled by a controlledZ operation.In order to obtain the result and also verify our algorithm, we choose Rigetti to perform the quantum processing. However, since the Rigetti platform limits the length of the entire circuit and noise has a great influence on the preparation of quantum states [40], we only show one of the ideal experiment circuits of similarity calculation in QReliefF algorithm running on Rigetti platform. We successfully stored the characteristic information in the sample into the amplitude of the quantum state and then extracted the amplitude information into the quantum state through the phase estimation algorithm. Figure 9 gives the schematic diagram of our experimental circuit. The corresponding code of the circuit in Rigetti is shown in Algorithm 3. After running Algorithm 3 8 times, the result can be seen in Figure 10. We can get |1〉 with the average probability of 0.435125. Then, we successfully stored the characteristic information in the sample into the amplitude of the quantum state. According to equation (32), we can get su¯,v¯q≈0.435, i.e., su¯,v¯q≈0.435, and then we extracted the amplitude information into the quantum state through the phase estimation algorithm.Figure 9
One of the ideal experiment circuits of similarity calculation in QReliefF algorithm running on Rigetti platform. q[0] − q [7] represents the randomly selected quantum state ϕS0, q [9] − q [16] represents ϕS1, and q [17] is the resultant qubit. X is the Not operation, and Ry is Ry operation which can be expressed as a matrix in equation (9).Algorithm 3: Similarity calculation in QReliefF algorithm running on Rigetti.
(1)
# Define the new gate from a matrix
(2)
theta = Parameter(“theta”)
(3)
cry = np.array([
(4)
[1, 0, 0, 0]
(5)
[0, 1, 0, 0]
(6)
[0, 0,quil_sqrt(1 − theta ∗ theta), −theta ∗ theta]
(7)
[0, 0,theta ∗ theta, quil_sqrt(1 − theta ∗ theta)]
(8)
])
(9)
gate_definition = DefGate(“CRY”, cry, [theta])
(10)
CRY = gate_definition.get_constructor()
(11)
# Create our program and use the new parametric gate
(12)
p = Program(
(13)
gate_definition, X(1), H(2), H(4), H(5), X(2), X(5)
(14)
CCNOT(2, 5, 18), X(2), X(5), CRY(1) (18, 0)
(15)
SWAP(0, 1), X(10), H(11), H(12), H(13), X(14)
(16)
X(11), X(12), CCNOT(11, 12, 17), X(11), X(12)
(17)
CRY(1) (17, 9), H(19), CSWAP(19, 0, 9)
(18)
CSWAP(19, 1, 10), CSWAP(19, 2, 11)
(19)
CSWAP(19, 4, 12), CSWAP(19, 5, 13)
(20)
CSWAP(19, 6, 14), CSWAP(19, 7, 15)
(21)
CSWAP(19, 8, 16), H(19)
(22)
)
(23)
# print the circuit
(24)
print(p)
(25)
# get a QPU, 20q − Acorn is just a string naming the device
(26)
qc = get_qc(“20q − Acorn”)
(27)
# run and measure
(28)
result = qc.run_and_measure(p, trials = 1024)Figure 10
The measurement result of |0〉 and |1〉 after running Algorithm 3 8 times on Rigetti.After all the steps have been performed, we obtain the quantum statesS1 (H), S2 (M(B)), and S5 (M(C)) of the nearest neighbor samples of the quantum state S0 (ū) in each class of the random sample which can be seen in Figure 11. Then, the weight vectors are updated according to equation (24) and the result of WT is listed in the second row of Table 2 after the first iteration. The algorithm iterates T times (in our example, T=4) as above steps and obtains all the WT results as shown in Table 2. After T-th iterations, WT = [4, 4, 4, −2, 0, −2], and then WT¯=1,1,1,−1/2,0,−1/2. In this paper, the value of τ in the example is assumed to be 0.5 according to the updated result of WT in Table 2. Since the threshold τ = 0.5, the selected features are F0, F1, and F2, i.e., the first, second, and third features. The result of quantum feature selection is consistent with the classical ReliefF algorithm after being verified by Python.Figure 11
Finding the nearest neighbor samples (S1, S2, and S5) of the sample S0.Table 2
The updated result of WT.
Iteration times (T)
Weight vector (WT)
1
[1, 1, 1, 0, 0, −1]
2
[2, 2, 2, −1, 0, −1]
3
[3, 3, 3, −1, 0, −2]
4
[4, 4, 4, −2, 0, −2]In the final weight value comparison, considering the large amount of data in the complex system and the corresponding eigenvalues, the calculation amount required for the comparison after the final result is obtained is also large. In order to meet the requirements of big data and result accuracy, we adopted an optimized quantum maximum and minimum value search algorithm [37] when comparing weights in the last step to help us quickly and accurately select the features we want, so as to better solve the multiclassification problem in complex systems.In circumstances when we can exactly estimate the ratio of the number of solutionsM and the searched space N, this algorithm can improve the successful probability close to 100%. Furthermore, it shows an advantage in complexity with large databases and in the operation complexity of constructing oracles.


### 5.1. Efficiency Analysis

In order to evaluate the efficiency of QReliefF algorithm, three algorithms (i.e., classical Relief, classical ReliefF, and quantum Relief algorithms) are selected to compare with our algorithm from three indicators: complexity of similarity calculation (CSC), complexity of finding the nearest neighbor (CFNN), and resource consumption (RC).In the classic Relief algorithm, it takesO(N) time to calculate the distance between randomly selected samples and any other samples, and then it finds the nearest neighbors related to M. This process needs to iterate T times, so CSC is O(TMN). Since T is a constant, CSC in the classic Relief algorithm is O(MN). As we know there are totally M samples, each with N features, CFNN is O(M) and RC in the classic Relief algorithm is O(MN) bits. The classical ReliefF algorithm is similar to the classical Relief algorithm. Since it finds k nearest neighbors at once time, the time complexity is O(kTMN). Then, we can simplify CSC to O(MN) because k and T are constants. Besides, CFNN for finding k nearest neighbors is O(M). In terms of resource consumption, there are M samples, and each sample has N features, so the resource consumption of the classic ReliefF algorithm is O(MN) bits.In QRelief and QReliefF algorithms, the quantum property is used to calculate the distance fromO(N) to O(1), so their CSCs are all O(TM). Since T is constant, their CSCs can be simplified to O(M). CFNN of QRelief is OkM, and then it can be simplified to OM as k is constant, while CFNN of QReliefF is kM because it uses the quantum Grover–Long method to find k nearest neighbor samples which holds a quadratic acceleration. Since k is constant, CFNN of QReliefF is OM. RC of similarity calculation, finding the nearest neighbor samples and updating weight vector are O(TMlogN), O(TN) and O(N), respectively. Therefore, the total complexity is O(TMlogN + TN + N); since T is constant, RC of QRelief and QReliefF is O(MlogN + N). For multifeature big data in complex systems with edge computing, there is M ≫ N, so M≫N/N−logN, and then RC of QRelief and QReliefF can be simplified into O(MlogN).For convenience, we list the efficiency comparison of classic Relief algorithm, ReliefF algorithm, quantum Relief algorithm, and our algorithm in terms of CSC, CFNN, and RC in Table3. Obviously, our algorithm is superior to classical algorithms (i.e., Relief and ReliefF) in terms of CSC, CFNN, and RC and better than quantum algorithm (i.e., QRelief) in terms of CFNN.Table 3
Efficiency comparison between classical Relief, classical ReliefF, QRelief, and QReliefF algorithms.
Multiclassification
CSC
CFNN
RC
Relief
No
O(MN)
O(M)
O(MN)
ReliefF
Yes
O(MN)
O(M)
O(MN)
QRelief
No
O(M)
O(M)
O(MlogN)
QReliefF
Yes
O(M)
O
M
O(MlogN)


## 5.1. Efficiency Analysis

In order to evaluate the efficiency of QReliefF algorithm, three algorithms (i.e., classical Relief, classical ReliefF, and quantum Relief algorithms) are selected to compare with our algorithm from three indicators: complexity of similarity calculation (CSC), complexity of finding the nearest neighbor (CFNN), and resource consumption (RC).In the classic Relief algorithm, it takesO(N) time to calculate the distance between randomly selected samples and any other samples, and then it finds the nearest neighbors related to M. This process needs to iterate T times, so CSC is O(TMN). Since T is a constant, CSC in the classic Relief algorithm is O(MN). As we know there are totally M samples, each with N features, CFNN is O(M) and RC in the classic Relief algorithm is O(MN) bits. The classical ReliefF algorithm is similar to the classical Relief algorithm. Since it finds k nearest neighbors at once time, the time complexity is O(kTMN). Then, we can simplify CSC to O(MN) because k and T are constants. Besides, CFNN for finding k nearest neighbors is O(M). In terms of resource consumption, there are M samples, and each sample has N features, so the resource consumption of the classic ReliefF algorithm is O(MN) bits.In QRelief and QReliefF algorithms, the quantum property is used to calculate the distance fromO(N) to O(1), so their CSCs are all O(TM). Since T is constant, their CSCs can be simplified to O(M). CFNN of QRelief is OkM, and then it can be simplified to OM as k is constant, while CFNN of QReliefF is kM because it uses the quantum Grover–Long method to find k nearest neighbor samples which holds a quadratic acceleration. Since k is constant, CFNN of QReliefF is OM. RC of similarity calculation, finding the nearest neighbor samples and updating weight vector are O(TMlogN), O(TN) and O(N), respectively. Therefore, the total complexity is O(TMlogN + TN + N); since T is constant, RC of QRelief and QReliefF is O(MlogN + N). For multifeature big data in complex systems with edge computing, there is M ≫ N, so M≫N/N−logN, and then RC of QRelief and QReliefF can be simplified into O(MlogN).For convenience, we list the efficiency comparison of classic Relief algorithm, ReliefF algorithm, quantum Relief algorithm, and our algorithm in terms of CSC, CFNN, and RC in Table3. Obviously, our algorithm is superior to classical algorithms (i.e., Relief and ReliefF) in terms of CSC, CFNN, and RC and better than quantum algorithm (i.e., QRelief) in terms of CFNN.Table 3
Efficiency comparison between classical Relief, classical ReliefF, QRelief, and QReliefF algorithms.
Multiclassification
CSC
CFNN
RC
Relief
No
O(MN)
O(M)
O(MN)
ReliefF
Yes
O(MN)
O(M)
O(MN)
QRelief
No
O(M)
O(M)
O(MlogN)
QReliefF
Yes
O(M)
O
M
O(MlogN)


## 6. Conclusion and Discussion

With the rapid development of edge computing technology and quantum machine learning algorithms, researchers began to pay attention to the combination and application of these two fields. In this paper, we use quantum technology to solve the multiclassification problem of feature selection in the complex systems with edge computing and propose a quantum ReliefF algorithm. Compared to the classic ReliefF algorithm, our algorithm reduces the complexity of similarity calculation fromO(MN) to O(M) and the complexity of finding the nearest neighbor from O(M) to OM. In addition, from the perspective of resource consumption, our algorithm consumes O(MlogN) qubit, while the classic ReliefF algorithm consumes O(MN) bit. Obviously, our algorithm is superior in terms of computational complexity and resource consumption.It should be noted that our work aims to improve the algorithm efficiency, while the privacy protection of sensitive data is not taken into account. At present, data security has become a focus of attention in the field of artificial intelligence, and some solutions for data privacy protection in complex systems with edge computing have been proposed [41–44]. In our future work, how to improve the efficiency of quantum machine learning algorithms while ensuring the privacy protection of sensitive data, such as [45–48], will become our direction.



---

*Source: 8216874-2020-03-31.xml*