  Spectral graph theory is a branch of mathematics that studies the
relationships between the eigenvectors and eigenvalues of Laplacian and
adjacency matrices and their associated graphs. The Variational Quantum
Eigensolver (VQE) algorithm was proposed as a hybrid quantum/classical
algorithm that is used to quickly determine the ground state of a Hamiltonian,
and more generally, the lowest eigenvalue of a matrix $M\in \mathbb{R}^{n\times
n}$. There are many interesting problems associated with the spectral
decompositions of associated matrices, such as partitioning, embedding, and the
determination of other properties. In this paper, we will expand upon the VQE
algorithm to analyze the spectra of directed and undirected graphs. We evaluate
runtime and accuracy comparisons (empirically and theoretically) between
different choices of ansatz parameters, graph sizes, graph densities, and
matrix types, and demonstrate the effectiveness of our approach on Rigetti's
QCS platform on graphs of up to 64 vertices, finding eigenvalues of adjacency
and Laplacian matrices. We finally make direct comparisons to classical
performance with the Quantum Virtual Machine (QVM) in the appendix, observing a
superpolynomial runtime improvement of our algorithm when run using a quantum
computer.
