Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2203.14451 · Advanced Quantum Technologies

A Quantum Algorithm for Solving Eigenproblem of the Laplacian Matrix of a Fully Connected Weighted Graph

Hailing Liu, Lin‐Chun Wan, Chao‐Hua Yu, Shi‐Jie Pan, Su‐Juan Qin, Fei Gao, Qiaoyan Wen

Published Apr 28, 2023• 14 citations
arXivHTMLPDF

Abstract

Abstract 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, an efficient quantum algorithm is proposed to solve it. Specifically, the optimal Hamiltonian simulation technique based on the block‐encoding framework is adopted 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 this entire algorithm is to construct a block‐encoding of the Laplacian matrix. To achieve this, how to construct block‐encoding of operators containing the information of the weight matrix and the degree matrix, respectively are shown in detail, and the block‐encoding of the Laplacian matrix is further obtained. Compared with its classical counterpart, this algorithm has a polynomial speedup on the number of vertices and an exponential speedup on the dimension of each vertex. It is also shown that this algorithm can be extended to solve the eigenproblem of symmetric (non‐symmetric) normalized Laplacian matrix.

DOI
10.1002/qute.202300031

Related papers

Efficient and Explicit Block Encoding of Finite Difference Discretizations of the Laplacian

Andreas Sturm, Niclas Schillo

The data input model is a fundamental component of every quantum algorithm, as its efficiency is crucial for achieving potential speed-ups over classical methods. For quantum linear algebra tasks that utilize quantum eigenvalue or singular value transformations, block encoding is the established technique for accessing matrix data. A key application of this is solving partial differential equations, where the Laplacian operator and its finite difference discretization serve as foundational examples. In this article, we present an efficient and explicit block encoding method for the Laplacian with periodic boundary conditions that enhances existing approaches in key aspects. We detail the construction of the quantum algorithm and illustrate how it leverages the unique structure of finite difference discretizations. Furthermore, we analytically derive the scaling of the sub-normalization factor and of the success probability of the block encoding with respect to the problem dimension, the grid width of the finite difference grid and the regularity of the exact solution, and we give resource estimates.

arXiv:2509.02429•ACM Transactions on Quantum Computing•Aug 1, 2026•9 citations

Laplacian Eigenmaps with variational circuits: a quantum embedding of graph data

Slimane Thabet, Jean-François Hullo

With the development of quantum algorithms, high-cost computations are being scrutinized in the hope of a quantum advantage. While graphs offer a convenient framework for multiple real-world problems, their analytics still comes with high computation and space. By mapping the graph data into a low dimensional space, in which graph structural information is preserved, the eigenvectors of the Laplacian matrix constitute a powerful node embedding, called Laplacian Eigenmaps. Computing these embeddings is on its own an expensive task knowing that using specific sparse methods, the eigendecomposition of a Laplacian matrix has a cost of O($rn^2$), $r$ being the ratio of nonzero elements. We propose a method to compute a Laplacian Eigenmap using a quantum variational circuit. The idea of our algorithm is to reach the eigenstates of the laplacian matrix, which can be considered as a hamiltonian operator, by adapting the variational quantum eigensolver algorithm. By estimating the $d$ first eigenvectors of the Laplacian at the same time, our algorithm directly generates a $d$ dimension quantum embedding of the graph. We demonstrate that it is possible to use the embedding for graph machine learning tasks by implementing a quantum classifier on the top of it. The overall circuit consists in a full quantum node classification algorithm. Tests on 32 nodes graph with a quantum simulator shows that we can achieve similar performances as the classical laplacian eigenmap algorithm. Although mathematical properties of this approximate approach are not fully understood, this algorithm opens perspectives for graph pre-processing using noisy quantum computers.

arXiv:2011.05128•Nov 10, 2020•5 citations

Quantum Speedup for Graph Sparsification, Cut Approximation, and Laplacian Solving

Simon Apers, Ronald de Wolf

Abstract. Graph sparsification underlies a large number of algorithms, ranging from approximation algorithms for cut problems to solvers for linear systems in the graph Laplacian. In its strongest form, “spectral sparsification” reduces the number of edges to near-linear in the number of nodes, while approximately preserving the cut and spectral structure of the graph. In this work we demonstrate a polynomial quantum speedup for spectral sparsification and many of its applications. In particular, we give a quantum algorithm that, given a weighted graph with [Formula: see text] nodes and [Formula: see text] edges, outputs a classical description of an [Formula: see text]-spectral sparsifier in sublinear time [Formula: see text]. This contrasts with the optimal classical complexity [Formula: see text]. We also prove that our quantum algorithm is optimal up to polylog-factors. The algorithm builds on a string of existing results on sparsification, graph spanners, quantum algorithms for shortest paths, and efficient constructions for [Formula: see text]-wise independent random strings. Our algorithm implies a quantum speedup for solving Laplacian systems and for approximating a range of cut problems such as min cut and sparsest cut.

arXiv:1911.07306•SIAM Journal on Computing•Dec 15, 2022•26 citations

A quantum algorithm for the Kalman filter using block encoding

Hao Jie Shi, Guofeng Zhang, Ming Zhang

Quantum algorithms offer significant speed-ups over their classical counterparts in various applications. In this paper, we develop quantum algorithms for the Kalman filter widely used in classical control engineering using the block encoding method. The entire calculation process is achieved by performing matrix operations on Hamiltonians based on the block encoding framework, including addition, multiplication, and inversion, which can be completed in a unified framework compared to previous quantum algorithms for solving control problems. We demonstrate that the quantum algorithm exponentially accelerates the computation of the Kalman filter compared to traditional methods. The time complexity can be reduced from $O(n^3)$ to $O(κpoly\log(n/ε)\log(1/ε'))$, where $n$ represents the matrix dimension, $κ$ denotes the condition number for the matrix to be inverted, $ε$ indicates desired precision in block encoding, $ε'$ signifies desired precision in matrix inversion. This paper provides a comprehensive quantum solution for implementing the Kalman filter and serves as an attempt to broaden the scope of quantum computation applications. Finally, we present an illustrative example implemented in Qiskit (a Python-based open-source toolkit) as a proof-of-concept.

arXiv:2404.04554•Apr 6, 2024•5 citations

Quantum algorithms for the fractional Poisson equation via rational approximation

Yin Yang, Yue Yu, Long Zhang +1 more

This paper presents a quantum algorithm for solving the fractional Poisson equation \((-Δ)^s u = f\) with \(s \in (0,1)\) on bounded domains. The proposed approach combines rational approximation techniques with quantum linear system solvers to achieve exponential quantum advantage. The rational approximation represents the inverse fractional Laplacian as a weighted sum of standard resolvents, transforming the original nonlocal problem into a collection of shifted integer-order partial differential equations. These equations are consolidated into a single large linear system through a modified right-hand side construction that simplifies the quantum implementation. To enable practical implementation, we develop explicit quantum circuits via the Schrödingerization technique, which converts the non-unitary dynamics of the linear system into a higher-dimensional Schrödinger-type equation, allowing the use of standard Hamiltonian simulation. The circuit construction leverages the decomposition of shift operators to realize the discrete Laplacian and employs controlled operations to implement the select oracle. Under finite difference discretization, we provide detailed algorithmic procedures utilizing block-encoding techniques for the coefficient matrices. A comprehensive complexity analysis demonstrates that the quantum algorithm achieves a dependence on the inverse mesh size \(h^{-1}\) that is independent of the spatial dimension \(d\), in stark contrast to classical methods which suffer from exponential growth in high dimensions. This establishes an exponential quantum advantage for high-dimensional fractional problems, effectively overcoming the curse of dimensionality that limits classical approaches.

quant-pharXiv:2604.00603•Apr 2, 2026•0 citations

Quantum algorithms for the polynomial eigenvalue problems.

Changpeng Shao, Jin-Peng Liu

Polynomial eigenvalue problems (PEPs) arise in a variety of science and engineering applications, and many breakthroughs in the development of classical algorithms to solve PEPs have been made in the past decades. Here we attempt to solve PEPs in a quantum computer. Firstly, for generalized eigenvalue problems (GEPs) $A\x = \lambda B\x$ with $A,B$ symmetric, and $B$ positive definite, we give a quantum algorithm based on block-encoding and quantum phase estimation. In a more general case when $B$ is invertible, $B^{-1}A$ is diagonalizable and all the eigenvalues are real, we propose a quantum algorithm based on the Fourier spectral method to solve ordinary differential equations (ODEs). The inputs of our algorithms can be any desired states, and the outputs are superpositions of the eigenpairs. The complexities are polylog in the matrix size and linear in the precision. The dependence on precision is optimal. Secondly, we show that when $B$ is singular, any quantum algorithm uses at least $\Omega(\sqrt{n})$ queries to compute the eigenvalues, where $n$ is the matrix size. Thirdly, based on the linearization method and the connection between PEPs and higher-order ODEs, we provide two quantum algorithms to solve PEPs by extending the quantum algorithm for GEPs. We also give detailed complexity analysis of the algorithm for two special types of quadratic eigenvalue problems that are important in practice. Finally, under an extra assumption, we propose a quantum algorithm to solve PEPs when the eigenvalues are complex.

•Oct 28, 2020•0 citations
Abstract 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, an efficient quantum algorithm is proposed to solve it. Specifically, the optimal Hamiltonian simulation technique based on the block‐encoding framework is adopted 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 this entire algorithm is to construct a block‐encoding of the Laplacian matrix. To achieve this, how to construct block‐encoding of operators containing the information of the weight matrix and the degree matrix, respectively are shown in detail, and the block‐encoding of the Laplacian matrix is further obtained. Compared with its classical counterpart, this algorithm has a polynomial speedup on the number of vertices and an exponential speedup on the dimension of each vertex. It is also shown that this algorithm can be extended to solve the eigenproblem of symmetric (non‐symmetric) normalized Laplacian matrix.
The data input model is a fundamental component of every quantum algorithm, as its efficiency is crucial for achieving potential speed-ups over classical methods. For quantum linear algebra tasks that utilize quantum eigenvalue or singular value transformations, block encoding is the established technique for accessing matrix data. A key application of this is solving partial differential equations, where the Laplacian operator and its finite difference discretization serve as foundational examples. In this article, we present an efficient and explicit block encoding method for the Laplacian with periodic boundary conditions that enhances existing approaches in key aspects. We detail the construction of the quantum algorithm and illustrate how it leverages the unique structure of finite difference discretizations. Furthermore, we analytically derive the scaling of the sub-normalization factor and of the success probability of the block encoding with respect to the problem dimension, the grid width of the finite difference grid and the regularity of the exact solution, and we give resource estimates.
With the development of quantum algorithms, high-cost computations are being scrutinized in the hope of a quantum advantage. While graphs offer a convenient framework for multiple real-world problems, their analytics still comes with high computation and space. By mapping the graph data into a low dimensional space, in which graph structural information is preserved, the eigenvectors of the Laplacian matrix constitute a powerful node embedding, called Laplacian Eigenmaps. Computing these embeddings is on its own an expensive task knowing that using specific sparse methods, the eigendecomposition of a Laplacian matrix has a cost of O(rn2rn^2rn2), rrr being the ratio of nonzero elements. We propose a method to compute a Laplacian Eigenmap using a quantum variational circuit. The idea of our algorithm is to reach the eigenstates of the laplacian matrix, which can be considered as a hamiltonian operator, by adapting the variational quantum eigensolver algorithm. By estimating the ddd first eigenvectors of the Laplacian at the same time, our algorithm directly generates a ddd dimension quantum embedding of the graph. We demonstrate that it is possible to use the embedding for graph machine learning tasks by implementing a quantum classifier on the top of it. The overall circuit consists in a full quantum node classification algorithm. Tests on 32 nodes graph with a quantum simulator shows that we can achieve similar performances as the classical laplacian eigenmap algorithm. Although mathematical properties of this approximate approach are not fully understood, this algorithm opens perspectives for graph pre-processing using noisy quantum computers.
Abstract. Graph sparsification underlies a large number of algorithms, ranging from approximation algorithms for cut problems to solvers for linear systems in the graph Laplacian. In its strongest form, “spectral sparsification” reduces the number of edges to near-linear in the number of nodes, while approximately preserving the cut and spectral structure of the graph. In this work we demonstrate a polynomial quantum speedup for spectral sparsification and many of its applications. In particular, we give a quantum algorithm that, given a weighted graph with [Formula: see text] nodes and [Formula: see text] edges, outputs a classical description of an [Formula: see text]-spectral sparsifier in sublinear time [Formula: see text]. This contrasts with the optimal classical complexity [Formula: see text]. We also prove that our quantum algorithm is optimal up to polylog-factors. The algorithm builds on a string of existing results on sparsification, graph spanners, quantum algorithms for shortest paths, and efficient constructions for [Formula: see text]-wise independent random strings. Our algorithm implies a quantum speedup for solving Laplacian systems and for approximating a range of cut problems such as min cut and sparsest cut.
Quantum algorithms offer significant speed-ups over their classical counterparts in various applications. In this paper, we develop quantum algorithms for the Kalman filter widely used in classical control engineering using the block encoding method. The entire calculation process is achieved by performing matrix operations on Hamiltonians based on the block encoding framework, including addition, multiplication, and inversion, which can be completed in a unified framework compared to previous quantum algorithms for solving control problems. We demonstrate that the quantum algorithm exponentially accelerates the computation of the Kalman filter compared to traditional methods. The time complexity can be reduced from O(n3)O(n^3)O(n3) to O(κpolylog⁡(n/ε)log⁡(1/ε′))O(κpoly\log(n/ε)\log(1/ε'))O(κpolylog(n/ε)log(1/ε′)), where nnn represents the matrix dimension, κκκ denotes the condition number for the matrix to be inverted, εεε indicates desired precision in block encoding, ε′ε'ε′ signifies desired precision in matrix inversion. This paper provides a comprehensive quantum solution for implementing the Kalman filter and serves as an attempt to broaden the scope of quantum computation applications. Finally, we present an illustrative example implemented in Qiskit (a Python-based open-source toolkit) as a proof-of-concept.
This paper presents a quantum algorithm for solving the fractional Poisson equation (−Δ)su=f(-Δ)^s u = f(−Δ)su=f with s∈(0,1)s \in (0,1)s∈(0,1) on bounded domains. The proposed approach combines rational approximation techniques with quantum linear system solvers to achieve exponential quantum advantage. The rational approximation represents the inverse fractional Laplacian as a weighted sum of standard resolvents, transforming the original nonlocal problem into a collection of shifted integer-order partial differential equations. These equations are consolidated into a single large linear system through a modified right-hand side construction that simplifies the quantum implementation. To enable practical implementation, we develop explicit quantum circuits via the Schrödingerization technique, which converts the non-unitary dynamics of the linear system into a higher-dimensional Schrödinger-type equation, allowing the use of standard Hamiltonian simulation. The circuit construction leverages the decomposition of shift operators to realize the discrete Laplacian and employs controlled operations to implement the select oracle. Under finite difference discretization, we provide detailed algorithmic procedures utilizing block-encoding techniques for the coefficient matrices. A comprehensive complexity analysis demonstrates that the quantum algorithm achieves a dependence on the inverse mesh size h−1h^{-1}h−1 that is independent of the spatial dimension ddd, in stark contrast to classical methods which suffer from exponential growth in high dimensions. This establishes an exponential quantum advantage for high-dimensional fractional problems, effectively overcoming the curse of dimensionality that limits classical approaches.
Polynomial eigenvalue problems (PEPs) arise in a variety of science and engineering applications, and many breakthroughs in the development of classical algorithms to solve PEPs have been made in the past decades. Here we attempt to solve PEPs in a quantum computer. Firstly, for generalized eigenvalue problems (GEPs) $A\x = \lambda B\x$ with A,BA,BA,B symmetric, and BBB positive definite, we give a quantum algorithm based on block-encoding and quantum phase estimation. In a more general case when BBB is invertible, B−1AB^{-1}AB−1A is diagonalizable and all the eigenvalues are real, we propose a quantum algorithm based on the Fourier spectral method to solve ordinary differential equations (ODEs). The inputs of our algorithms can be any desired states, and the outputs are superpositions of the eigenpairs. The complexities are polylog in the matrix size and linear in the precision. The dependence on precision is optimal. Secondly, we show that when BBB is singular, any quantum algorithm uses at least Ω(n)\Omega(\sqrt{n})Ω(n​) queries to compute the eigenvalues, where nnn is the matrix size. Thirdly, based on the linearization method and the connection between PEPs and higher-order ODEs, we provide two quantum algorithms to solve PEPs by extending the quantum algorithm for GEPs. We also give detailed complexity analysis of the algorithm for two special types of quadratic eigenvalue problems that are important in practice. Finally, under an extra assumption, we propose a quantum algorithm to solve PEPs when the eigenvalues are complex.