  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.
