A quantum algorithm for solving eigenproblem of the Laplacian matrix of a fully connected weighted graph

Solving eigenproblem of the Laplacian matrix of a fully connected weighted graph has wide applications in data science, machine learning, and image processing, etc. However, this is very challenging because it involves expensive matrix operations. Here, we propose an efficient quantum algorithm to solve it based on a assumption that the element of each vertex and its norms can be effectively accessed via a quantum random access memory data structure. Specifically, we adopt the optimal Hamiltonian simulation technique based on the block-encoding framework to implement the quantum simulation of the Laplacian matrix. Then, the eigenvalues and eigenvectors of the Laplacian matrix are extracted by the quantum phase estimation algorithm. The core of our entire algorithm is to construct the block-encoding of the Laplacian matrix. To achieve this, we propose in detail how to construct the block-encodings of operators containing the information of the weight matrix and the degree matrix respectively, and further obtain the block-encoding of the Laplacian matrix. Compared with its classical counterpart, our algorithm has a polynomial speedup on the number of vertices and an exponential speedup on the dimension of each vertex. We also show that our algorithm can be extended to solve the eigenproblem of symmetric (non-symmetric) normalized Laplacian matrix.

In the era of big data, graph learning [17] has attracted considerable attention owing to its wide applications in data science, machine learning, and image processing, etc. In the process of dealing with problems related to graph learning, such as graph networks [18,19], image processing [20,21], and reinforcement learning [22], it is necessary to solve the eigenproblem of the Laplacian matrix of a fully connected weighted graph to avoid dropping crucial nonlocal information. In general, the Laplacian matrix L is given by the difference between the degree matrix D and the weight matrix W (L = D − W ). For a fully connected weighted graph, W is a dense matrix, thus L is also a dense matrix. However, solving the eigenproblem of a dense matrix L is very challenging because it involves expensive matrix operations. Therefore, it is imperative for us to design an efficient algorithm to solve this problem.
Fuelled by the success of quantum algorithms, some * qsujuan@bupt.edu.cn † gaof@bupt.edu.cn scholars proposed to solve the eigenproblem of L with quantum algorithm. Kerenidis et al. [23] proposed a quantum algorithm for solving the eigenproblem of the symmetric normalized Laplacian matrix, and successfully applied it to the spectral clustering algorithm. However, as the authors point out, their algorithm cannot efficiently access D and the norm of the rows vectors of W . This makes their algorithm cannot be directly used to solve the eigenproblem of L of a fully connected weighted graph. Subsequently, Li et al. [24] designed a quantum algorithm to solve the eigenproblem of L and also applied it to accelerate the spectral clustering algorithm. However, their quantum algorithm can only handle the sparse matrix L.
In 2016, Huang et al. proposed a quantum Laplacian eigenmap algorithm, which has a significant speedup compared with its classical counterparts [25]. However, this algorithm relies on a strong assumption that the classically stored information of W and D can be superposition accessed by a quantum random access memory [26]. In fact, the data usually given is the vertex set of a graph in most scenarios [18-21, 27, 28], W and D need to be obtained by complex computations. This makes the classical complexity of implementing this strong assumption theoretically would exceed the complexity of the quantum algorithm itself. In short, the existing quantum algorithm cannot efficiently solve the eigenproblem of L of a fully connected weighted graph.
In this paper, we design an efficient quantum algorithm to solve eigenproblem of the Laplacian matrix L of a fully connected weighted graph without the above strong assumptions. The starting point of our quantum algorithm was the assumption of having superposition access arXiv:2203.14451v2 [quant-ph] 28 May 2022 to the element of each vertex and its norms. This makes our proposed algorithm more suitable for practical scenarios. Specifically, we adopt the optimal Hamiltonian simulation technique based on the block-encoding framework [29][30][31] to implement the quantum simulation of L, which reduce the algorithm's dependence on simulation error. Then we employ the quantum phase estimation algorithm [32] to extract the eigenvalues and eigenvectors of L. The core of our entire algorithm is to construct the block-encoding of L. To achieve it, we design the specific controlled unitary operators to prepare the quantum states to construct the block-encodings of operators containing the information of W and D respectively, and further obtain the block-encoding of L. Compared with its classical counterpart, our algorithm has a polynomial speedup on the number of vertices and an exponential speedup on the dimension of each vertex. In particular, our algorithm can also be used to solve eigenproblem of W , which is also of great significance [33][34][35][36]. We also show that our algorithm can be extended to solve the eigenproblem of symmetric (non-symmetric) normalized Laplacian matrix.
The remainder of the paper is organized as follows. In Sec. II, we give a brief overview of the graph Laplacian matrix. In Sec. III, we propose a quantum algorithm to solve eigenproblem of the Laplacian matrix of a fully connected weighted graph. In Sec. IV, we generalized the algorithm to solve eigenproblem of symmetric (nonsymmetric) normalized Laplacian matrix. In Sec. V, we give some discussions. Finally, we present our conclusion in Sec. VI.

II. REVIEW OF THE GRAPH LAPLACIAN MATRIX
Given a weighted undirected graph G = (V, E) with the vertex set V = {x i |x i ∈ R m } n i=1 and the edge set E. The weight matrix W ∈ R n×n of the graph G is defined as follows: Specifically, the element w ij > 0 represents that vertex x i is connected to vertex x j , otherwise w ij = 0. For w ij , i = j, we take the Gaussian similarity function w ij = exp(−λ x i −x j 2 ) as an example which has a wide range of applications, where λ > 0 is any given real number [37,38]. It is worth noting that we can also choose other forms of nonlinear similar functions [27,28], such as sigmoid and cosine similar function.
Next the degree matrix D of the graph G is defined as a diagonal matrix D = diag(d ii ) ∈ R n×n , where d ii = n j=1 w ij . Given W and D, the graph Laplacian matrix L is defined as where L is a symmetric positive semi-definite matrix. In addition, there are two common normalized Laplacian matrices as follows: where L s (L r ) is a symmetric (non-symmetric) matrix. For more information about L, see Refs. [27,28].
Solving eigenproblem of L of a fully connected weighted graph has wide applications in graph networks [18,19], image processing [20,21], and reinforcement learning [22], etc. For a fully connected weighted graph, W is a dense matrix, thus L is also a dense matrix. And the multiplicity of the zero eigenvalue of L is equal to 1 and the eigenvector corresponding to zero eigenvalue is 1 = (1, · · · , 1) T ∈ R n [28]. It provides no extra information. Therefore, we consider extracting 1 ≤ d ≤ (n − 1) non-zero eigenvalues and the corresponding eigenvectors of L, and its classical complexity is O(mn 2 + dn 3 ) [39]. This is quite time consuming when the size of the vertex set is large. Therefore, it is imperative for us to design an efficient algorithm to solve it.

III. A QUANTUM ALGORITHM FOR SOLVING EIGENPROBLEM OF THE LAPLACIAN MATRIX OF A FULLY CONNECTED WEIGHTED GRAPH
To design an efficient quantum algorithm to solve eigenproblem of L of a fully connected weighted graph, we adopt the optimal Hamiltonian simulation technology based on the block-encoding framework [29][30][31] to realize the quantum simulation of L and then perform quantum phase estimation algorithm [32] to extract the eigenvalues and eigenvectors of L. The core of our entire algorithm is to construct the block-encoding of L. To achieve it, we construct the block-encodings of operators containing the information of W and D respectively, and further obtain the block-encoding of L.
The entire section consists of five subroutines: we review the optimal Hamiltonian simulation technology based on the block-encoding framework in Sec. III A, quantum algorithms for preparing the quantum states to construct the block-encodings of operators containing the information of W and D in Sec. III B and Sec. III C, respectively, a quantum algorithm for obtaining the blockencoding of L to implement the quantum simulation of L in Sec. III D, and a quantum algorithm to extract the eigeninformation of L in Sec. III E. For convenience, we define the base of the logarithm function as 2, which can be abbreviated as log x.
Assume that the vertex set V = {x i |x i ∈ R m } n i=1 is stored in a quantum random access memory (QRAM) data structure [40], i.e., the element x ij of each vertex x i is stored in the ith leaf of the binary tree, and the internal node of the tree stores the modulo sum of the elements in the subtree rooted in it. Then there exists a quantum algorithm that can perform the following map with ε x -precision in O[poly log(mn/ε x )] time: In addition, this structure can perform the unitary operator O in time O[poly log(mn)]: This data structure has also been successfully applied to quantum data compression [41], quantum linear systems with displacement structures [42] and so on.
A. Review of the optimal Hamiltonian simulation technology based on the block-encoding framework In this section, we review the optimal Hamiltonian simulation technology based on the block-encoding framework [29][30][31]. We first give the framework of blockencoding.
Definition1 (Block-encoding). Assume that A is an s-qubits operator, α, A ∈ R + , and a ∈ N, then we say that the (s + a)-qubits unitary U is an (α, a, A ) blockencoding of A if it satisfies Meanwhile, Low and Chuang [29] also proposed a block-encoding framework of a purified density operator, as follows: Lemma1 (Block-encoding of density operators). Suppose that ρ is an s-qubits density operator and G is an (a + s)-qubits unitary operator that acts on the input state |0 ⊗a |0 ⊗s prepares a purification |0 ⊗a |0 ⊗s → |ρ , s.t. Tr a (|ρ ρ|) = ρ. Then (G † ⊗I s )(I a ⊗SW AP s )(G⊗I s ) is an (1, a + s, 0)-block-encoding of ρ.
Subsequently, András Gilyén et al. [30] proposed to implement a block-encoding of a linear combination of block-encoded operators. It is shown as follows: Definition2 (State preparation pair). Let y ∈ C m and y 1 ≤ β. The pair of unitaries (P L , P R ) is called an − y j | ≤ ε y and for all j ∈ m + 1, · · · , 2 b , we have c * j d j = 0. Lemma2 (Linear combination of block-encoded matrices). Let A = m j=1 y j A j be an s-qubits operator and ε A ∈ R + . Assume that (P L , P R ) is an (β, b, ε y )-statepreparation-pair for y ∈ C m , W = m j=1 |j j| ⊗ U j + ((I − m j=1 |j j|) ⊗ I a ⊗ I s ) is an (s + a + b)-qubits unitary operator such that for all j = 1, · · · , m, we have that U j is an (α, a, ε A )-block-encoding of A j . Then we can implement an (αβ, a +b, αε y +αβε A )-block-encoding of A, with a single use of W , P R and P † L .
The core of this technique is to construct the blockencoding of an operator. To realize the quantum simulation of L = D − W , next we will design quantum algorithms to construct the block-encodings of operators containing the information of W and D, respectively.
B. Prepare the quantum state to construct the block-encoding of an operator containing the information of W We know that the elements of W are where i, j = 1, 2, · · · , n.
] is a scalar that depends on the size of x i , i = 1, · · · , n, we take the Taylor expansion of exp(2λx i · x j ) to get According to Taylor's theorem [43], by keeping only the low-order terms of the Taylor expansion, we can get a finite-dimensional approximated of exp(2λx i · x j ), i.e., A detailed analysis of the errors of low order approximation with Taylor expansion, see Ref. [44]. Combine Eq. (7) with Eq.(9), we can obtain where a k = (2λ) k /k!, k = 0, 1, · · · , p. It is worth noting that other forms of nonlinear similarity functions can also obtain corresponding low-order approximations by Taylor expansion, whose forms are similar to w ij , such as sigmoid and cosine similarity functions. Note that when x i = 1, according to Eq.(10), we have Once λ is given, exp(−2λ) is a constant that can be absorbed into a k , namelyã k = [exp(−2λ)(2λ) k ]/k!. However, when x i = 1, its value will affects the value of Therefore, next we will design the corresponding quantum algorithms to construct the block-encodings of operators containing the information of W in two cases, as follows: The specific steps of the quantum algorithm are as follows.
The quantum circuit of the controlled unitary operator RU . Here the subscripts 1, 2, 3 represent the index of the registers. The third register has p log m qubits which comes from p sub-registers with log m qubits, namely, |0 k 3 = |0 log m k 3 (k = 1, · · · , p) and H denotes Hadamard gate, and U k , k = 0, 1, · · · , p, represent k consecutive executions of the unitary operator U .
for a detailed analysis about 0 . For convenience, we use· to represent the estimated value caused by the quantum algorithm in the following sections. (I. 2) The complexty of algorithm in the case of x i = 1, i = 1, · · · , n In step (I.1), the complexity is O{poly log[n(p + 1)/εã]}, which is derived from log n Hadamard gates generating the first register and O{poly log[(p + 1)/εã]} with gate complexity generating the second register.
In step (I.2), according to the quantum circuit of R U in Fig. 1, it need O(p) calls of the unitary operator U . Thus the complexity of R U is O(p · poly log(mn/ε x )). Next we analyze the error that produces the state |Φ as follows: where the final inequality is proved in Appendix A.
(II.2) A quantum algorithm in the case of x i = 1, i = 1, · · · , n To facilitate the introduction of the algorithm, we first list the lemma required.
Lemma3 [45] (Quantum Multiply-Adder (QMA)) Let integers a and b be m-bit string. Then there is a quantum algorithm with O[poly(m)] single-and two-qubit gates can realize Note that for accuracy defined as m = 2 −m , the complexity of QMA is given by The specific algorithm proceeds as following steps: (II.1) Prepare the quantum state The quantum circuit of implementing R O in Fig. 2. (II.3) Apply Lemma3 to the third and fourth registers respectively, and undo the redundant registers, we have (II.5) Use Lemma3 for the third and fourth registers and uncompute redundant registers, we obtain (II.6) Add one qubit and rotate it from |0 to The quantum circuit of the controlled unitary operator RO. The subscripts 1, · · · , 5 represent the index of the registers. Here, each sub-register in the third and fourth registers has log(mn) qubits, i.e., |0 = |0 log(mn) , and each sub-register in the fifth register has log m qubits, i.e., |0 5 = |0 log m 5 and H denotes Hadamard gate, and O k , k = 0, 1, · · · , p, represent k consecutive executions of the unitary operator O.
The above operation is denoted as a controlled rotation operator R. Then we uncompute the third register to obtain (II.7) Apply the quantum amplitude amplification algorithm [46] to produce Note that (II.9) Take partial trace for the second and fifth registers, we get According to Lemma1, the process of generating the state |Ψ can be regard as an (a 1 + s 1 )-qubits unitary operator G 1 which implement G 1 |0 ⊗a1 |0 ⊗s1 → |Ψ , s.t. Tr 2,5 (|Ψ Ψ|) = ρ 1 , where a 1 = log(p + 1) + (p + 2) log(mn) + p log m + 1, s 1 = log n. Then V 1 := (G † 1 ⊗ I 1,3,4,0 )(I 2,5 ⊗ SWAP 1,3,4,0 )(G 1 ⊗ I 1,3,4,0 ) is a (1, a 1 + s 1 , 2 1 )-block-encoding of ρ 1 , where 1 is the error that produces the state |Ψ . See (II.2) for detailed analysis for 1 . The whole quantum circuit is shown in Fig. 3. (II. 2) The complexty of algorithm in the case of x i = 1, i = 1, · · · , n The complexity of algorithm is dominated by the controlled unitary operators R O and R U , and quantum amplitude amplification algorithm of step (II.7). According to the quantum circuits of R O and R U , we can obtain that the complexity of R O and R U is O(p · poly log(mn)) and O(p · poly log(mn/ε x )), respectively.
Next we analyze the complexity of step (II.7). According to Eq.(25), we can get the probability amplitude of the auxiliary qubit |0 is The equation above is established by the Taylor expansion of order p of [exp(λ x i 2 )] 2 , i.e., Thus, we need perform O( √ aC) repetitions of quantum amplitude amplification algorithm to obtain the quantum state of Eq. (26).
Besides, we can obtain That means that Υ = O(n). Finally, we analyze the error that produces the quantum state |Ψ as follows: where x i > 1 and a detailed analysis of the last inequality is given in Appendix A. In particular, for 0 < x i < 1, we also give a detailed analysis in Appendix A.
To ensure that the error of producing |Ψ is 1 , let ε a = ε x , we get Thus, we can obtain 1/ε x = √ anp 2 (max i x i ) p / 1 . Putting this all together, the complexity is C. Prepare the quantum state to construct the block-encoding of an operator containing the information of D The elements of D are d ii = n j=1 w ij , i = 1, · · · , n, that is, the sum of each row of W . Thus, d ii can be regarded as the inner product of the row vector of W and the vector 1 = (1, · · · , 1) T ∈ R n . To achieve this, we first give the lemma required.
Lemma4 [47] (Distance / Inner Products Estimation of two vectors) Assume that the unitary operators U |i |0 = |i |x i and V |j |0 = |j |x j can be performed in time T , and the norms x i and x j are known. Then there is a quantum algorithm can compute with probability at least 1 − 2δ for any δ with complexity The process of the quantum algorithm (1). Prepare the quantum state (2). The Distance Estimation algorithm of Lemma4 is applied to the second, third and fourth registers, we get (3). Perform exp(−λx) gate (See the detailed analysis in Appendix B) for the fourth register to produce (41) In fact, according to Eq.(1), we have w ij = 0 when i = j. However, for Eq.(41), we have w ij = 1, i = j. Therefore, we need to perform quantum amplitude amplification algorithm to discard w ij = 1, i = j.
2. The complexity of the algorithm In step(1), we perform 2 log n Hadamard gates on the second and third registers of the initial state |0 1 |0 log n 2 |0 log n 3 |0 log(mn) 4 |0 5 |0 log(mn) 6 to produce the quantum state of Eq. (39). Thus, the complexity of step(1) is 2 log n.
In step(2), according to Lemma4, the complexity is where 1−2δ 1 is the probability of success of the algorithm with any δ 1 and ε d is the error of x i − x j 2 . In step(3), the complexity of the exp(−λx) gate is O[poly log(1/ε d )] (with details given in Appendix B) which is smaller than O(1/ε d ) caused by the step(2). Therefore we can ignore the complexity of these gates.
In step(4), the probability amplitude of the target states of Eq.(42) is p = (n 2 − n)/n 2 = O(1). Thus, we perform O(1) times of quantum amplitude amplification algorithm to produce the state in Eq. (43).
In step(5)-step (6), it contains one Hadamard gate and a controlled rotation operator R w which has complexity O(1).
In step (7), we analyze the error in calculating ϕ|ψ is where ω = x i − x j 2 , the second inequality comes from the Lagrange's mean value theorem [48], ξ takes value fromω to ω.
According to Lemma4, we can get that the complexity is where υ = log(1/δ 1 ) log(1/δ 2 ), 1 − 2δ 2 is the probability of success of the algorithm with any δ 2 and λε d is the error of ϕ|ψ .
Finally, we analyze the error that produces the quantum state |φ is where the second equation comes from Eq.(47), the third equation follows from the Lagrange's mean value theorem [48], ξ 0 takes value fromˆ ϕ|ψ to ϕ|ψ , and the last inequality holds by τ ≥ n(n − 1)r.
The complexity of each step of the algorithm is shown in Table. I.
To make the error of |φ equal to 2 , we have Thus we can obtain 1/ε d = λ/2 √ r 2 . Putting all complexity together and letting ε x = ε d ,  Here, we first implement the quantum simulation of L in the case of x i = 1, i = 1, · · · , n. Similarly, we provide a detailed analysis for the case of x i = 1 in Appendix C.
According to L = D − W , we have .
According to Lemma2, we can implement unitary G which is an (3, l + 2, ε y + 3ε l )-block-encoding of L, with a single use of Q, P L , and P R .

E. Extract the eigeninformation of L
In this section, we use quantum phase estimation algorithm to extract the 1 ≤ d ≤ (n − 1) non-zero eigenvalues and eigenvectors of L.
Suppose that the eigendecomposition form of L is where {γ j } n j=1 and {|u j } n j=1 are the eigenvalues and the corresponding eigenvectors of L, respectively.
Our algorithm works as the following steps.
(1) The steps of the quantum algorithm 1. Perform Hadamard and CNOT gates on the initial states |0 log n 1 |0 log n 2 |0 log n 3 to produce the quantum state 2. Take partial trace for the second register to get Although we don't know the information of the state |u j , j = 1, · · · , n in advance, we have 3. Run the quantum phase estimation algorithm by simulating exp(−iLt) to reveal the eigenvalues and eigenvectors of L 1 n n j=1 |u j u j | ⊗ |γ j γ j |.
(2) The complexity of the algorithm In step 1, the complexity is O(poly log n), which comes from Hadamard and CNOT gates.
In step 3, according to Ref. [3], it takes t = O(1/ ) times to yields the eigeninformation of L with accuracy . Therefore, the complexity of the algorithm is where c 1 and c 2 are shown in Eq. (36) and Eq. (59), which represent the complexity of generating the blockencodings of W and D, respectively. In step 4, to reveal the 1 ≤ d ≤ (n − 1) minimized nonzero eigenvalues and the corresponding eigenvectors of L, we need to run O(d) times of the algorithm for find the minimum that output the minimum values with probability larger than 1/2 with the query complexity O( √ n) [11,50]. Thus the total complexity is O(d √ n). Putting all the complexity together, we can obtain the complexity of the whole quantum algorithm is When a, p, C, λ, √ r and max i x i are all O(1), and letting 1/ 1 = 1/ 2 = 1/ = O(poly log n), our quantum algorithm takes time It is shown that our algorithm achieve a polynomial speedup on n and an exponential speedup on m compared with the classical algorithm whose complexity is O(mn 2 + dn 3 ).
In addition, our algorithm can also extract the eigeninformation of W , which is of great significant [33][34][35][36]. See the detailed analysis in Appendix D.

IV. GENERALIZATION: SOLVE THE EIGENPROBLEM OF Ls AND Lr
In this section, we extend our quantum algorithm to solve the eigenproblem of L s and L r in Eq.(3). We assume that the eigendecomposition form of L s is where {µ i } n i=1 and {|v i } n i=1 are the eigenvalues and the corresponding eigenvectors of L s , respectively.
According to the properties of L s and L r [27], we know that the eigenvalues of L r are also {µ i } n i=1 and the corresponding eigenvectors are {D − 1 2 |v i } n i=1 . In particular, µ 1 = 0 is the unique zero eigenvalue of L s , and the corresponding eigenvector is |v 1 = D 1 2 1. Therefore, when we obtain the eigeninformation of L s , we can also get the eigeninformation of L r . Next we show that how to extract the eigeninformation of L s .
To achieve this, our core task is to first realize the quantum simulation of L s . According to Eq.(3), we have We have constructed the block-encodings of ρ 2 and L, respectively. Based on Lemma4 and Lemma8 of Ref. [31], we can design the block-encoding of L s . For ease of understanding , we write it as the following lemma, show below: Lemma5 (Block-encoding of A −c BA −c ) Let c ∈ (0, ∞), ς 1 ∈ (0, 1/2], and let A and B are Hermitian matrices, and A satisfy U is an (α 1 , b 1 , ζ 1 )-block-encoding of A that can be implemented using T U elementary gates and V is an (α 2 , b 2 , ζ 2 )-block-encoding of B that can be implemented using T V elementary gates. Then we can implement a unitary F that is an (4κ 2c α 2 , According to Lemma5, for L s , we get c = 1/2, A = ρ 2 , B = L. And we assume that ρ 2 and L satisfy the conditions of Lemma5. We have obtained that the unitary operator V 2 which is an (1, a 2 +s 2 , 2 2 )-blockencoding of ρ 2 and the unitary operator G which is an (3, l + 2, ε y + 3 l )-block-encoding of L, respectively. Therefore, we can implement a unitary F that is an where f = 12κ 1 2 ς 1 + 4κ(ε y + 3 l ) and T L = max{c 1 , c 2 } is the complexity of produces the unitary operator G.
Finally, combining Theorem1 and Sec. III E, we can obtain the the d minimized nonzero eigenvalues of L s and the corresponding eigenvectors To obtain the eigeninformation of L r , we perform the quantum technique of Lemma30 in Ref. [31] to get the state for each |v i , i = 1, · · · , d, that is, the corre- In Refs. [23,25], scholars use the definition of L = BB T to design quantum algorithms to solve related problems, and has a significant speedup compared with its classical counterparts, where B is an incidence matrix to store the relationship between each node and its connected edges. As the introduction pointed out, their algorithm cannot efficiently solve the eigenproblems of L of a fully connected weighted graph. A straightforward idea is to design quantum algorithm to efficiently realize the strong assumption of Ref. [25], then obtain the eigeninformation of L s by using the existing technique of Ref. [25]. However, the strong above assumption also require access to the norms of the column vector of B and D, and an efficient quantum algorithm has not yet been found to implement it. In addition, the algorithm of Ref. [25] uses the Hermitian chain product technique [9] to realize the quantum simulation of L s . This makes the complexity of the algorithm have a cubic dependent on the inverse of the simulation error.
In our algorithm, we adopt the definition of L = D−W to design the quantum algorithm for the following three main reasons: (1) the strong assumption of Ref. [25] is avoided; (2) the eigeninformation of W is of great significant [33][34][35][36]; (3) solving the eigenproblem of L s and L r also requires access to D. In addition, we adopt the optimal Hamiltonian simulation technique based on the block-encoding framework [29][30][31] to implement the quantum simulation of L, which reduce the algorithm's dependence on simulation error.
In particular, our algorithm also solve the eigenproblem of W in Appendix D. We find that the Gaussian kernel matrix K satisfies K = W + I, thus our algorithm can also be used to solve the eigenproblem of K. Clearly, our algorithm is a quantum algorithm under the circuit model, while the quantum algorithms proposed in Refs. [51][52][53] are formulated with the generalized coherent states, which is the specialized language of quantum optics, to construct K. This makes them likely not universal quantum computing paradigm [54]. Compared to Ref. [54], our algorithm can not only process the scenario where the modulus length of each sample data point x i is not equal to 1, i.e., x i = 1, i = 1, 2, · · · , n, but also provide the optimal Hamiltonian simulation algorithm based on the block-encoding framework for K to reduce the algorithm's dependence on simulation error. Similarly, our algorithm can also be extended to solve arbitrary nonlinear kernel matrix, which has a wide range of applications in classification, dimensionality reduction, regression and so on. In addition, Sornsaeng et al. [53] proposed using the quantum matrix algebra toolbox [55] algorithm to quantum simulation of D, and achieved a certain acceleration effect. Compared with their algorithm, our algorithm has significant improvement in both simulation time and simulation error.

VI. CONCLUSION
In summary, we designed an efficient quantum algorithm to solve the eigenproblem of L of a fully connected weighted graph. Specifically, we designed special controlled unitary operators to construct the blockencodings of operators containing the information of W and D respectively, and further obtain the blockencoding of L. Then we employed the optimal Hamiltonian simulation technology based on the block-encoding framework to realize the quantum simulation of L. Finally, we adopted the quantum phase estimation algorithm to extract the eigenvalues and eigenvectors of L. It is shown that compared with the classical algorithm, our quantum algorithm achieve polynomial speedup in the number of vertices and exponential speedup in the dimension of each vertex. Additionally, we also extended our algorithm to solve the eigenproblem of W , L s and L r .
We expect that our quantum algorithm and the techniques mentioned, such as the quantum technique for constructing the block-encoding of an operator and the analysis of the error propagation of the quantum state, can provide new ideas for quantum algorithms to solve other problems. Furthermore, exploring the application of our quantum algorithms to real data is a goal worth considering in the future.
Besides, the advantages of our algorithms usually rely on a fault-tolerant quantum computer, which may take a long time horizon to implement. Recently, a few scholars have employed variational quantum algorithms [56,57] which can be implemented on the Noisy Intermediate-Scale Quantum (NISQ) devices [58] to solve several problems related to L. In 2020, Slimane et al. proposed a variational Laplacian eigenmap algorithm [59], and demonstrate that it is possible to use the embedding for graph machine learning tasks throught implementing a quantum classifier on the top of it. However, their algorithm cannot be used directly to deal with the case where the element of W is a Gaussian similarity function. In 2022, Li et al. designed a Laplacian eigenmap algorithm based on variational quantum generalized eigensolver [60] and their simulation results demonstrate that the proposed algorithm has good convergence. However, their algorithm employs the controlled SWAP test and maximum searching algorithm [61] to construct W , which cannot be implemented on NISQ devices. In addition, how to design a good strategy to suppress the barren plateau phenomenon in variational quantum algorithms [62] is also a thorny problem. Therefore, designing a variational quantum algorithm that can solve the above problems to solve eigenproblem of L may be an important direction of future work. . The controlled operator X denote the Pauli operator X. QF T and QF T † stand for the quantum Fourier transformation and the inverse quantum Fourier transformation, respectively. The operator Π + can implement the following transformation: Π + |λ |x |0 = |λ |x |λx . It can be represented as Π + = (I ⊗ I ⊗ QF T † ) · π ± · (I ⊗ I ⊗ QF T ), where π ± |a |b |φ(c) = |a |b |φ(c ± a · b) with |φ(c) = QF T |c and a, b, c are the input qubits.
Appendix C: Implement the quantum simulation of L in the case of xi = 1, i = 1, · · · , n In this section, we analyze the quantum simulation of implementing L in the case of x i = 1, i = 1, · · · , n. According to Eq. 16 in Sec. III B, we can obtain W =ã(nρ 0 − I). Due to Tr(L) = Tr(D), we havē In this section, we introduce that the algorithm to reveal the eigeninformation of W as follows: For the case of x i = 1, we can obtain W =ã(nρ 0 − I). Thus, we have W/n =ã(ρ 0 − I/n) =ãρ 0 −ãρ 3 .
For the case of |x i = 1, we can obtain W = Tr(W + I)ρ 1 − I. Due to Tr(W + I) = n, Thus, we have In short, Eq. D1 and Eq. D2 can be viewed as a linear combination of block-encoded operators, respectively. Similarly to Sec. III C, we can implement the quantum simulation of W . Then we can solve the eigenproblem of W by using the algorithm in Sec. III E.