Approximate graph spectral decomposition with the Variational Quantum Eigensolver

Josh Payne; Mario Srouji

doi:10.1117/12.2542854

5 June 2020 Approximate graph spectral decomposition with the Variational Quantum Eigensolver

Josh Payne, Mario Srouji

Proceedings Volume 11391, Quantum Information Science, Sensing, and Computation XII; 113910I (2020) https://doi.org/10.1117/12.2542854
Event: SPIE Defense + Commercial Sensing, 2020, Online Only

Abstract

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 Eigen- solver (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 ∈ R^nxn. 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.*

Conference Presentation

Citation Download Citation

Josh Payne and Mario Srouji "Approximate graph spectral decomposition with the Variational Quantum Eigensolver", Proc. SPIE 11391, Quantum Information Science, Sensing, and Computation XII, 113910I (5 June 2020); https://doi.org/10.1117/12.2542854

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available