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, an efficient quantum algorithm is proposed to...

Full description

Saved in:
Bibliographic Details
Published in:Advanced quantum technologies (Online) 2023-07, Vol.6 (7), p.n/a
Main Authors: Liu, Hai‐Ling, Wan, Lin‐Chun, Yu, Chao‐Hua, Pan, Shi‐Jie, Qin, Su‐Juan, Gao, Fei, Wen, Qiao‐Yan
Format: Article
Language:English
Subjects:
block‐encoding
fully connected weighted graph
Laplacian matrix
quantum algorithm
solving eigenproblem
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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. This paper presents how to solve eigenproblem of the Laplacian matrix of a fully connected weighted graph on quantum computer, and how much speedup quantum computing can achieve over classical computing in implementing this task. The results show that the algorithm has a polynomial acceleration in the number of vertices and an exponential acceleration in the dimension of each vertex.
ISSN:2511-9044
2511-9044
DOI:10.1002/qute.202300031