Combinatorial optimization as graph-theoretic problems are ubiquitous throughout mathematics, computer science, chemistry, physics, bioscience, machine learning, and complex systems. Many of these problems are NP-hard and rely on heuristic solutions. The availability of quantum computing architectures has opened the door for new opportunities to address these problems and explore quantum graph algorithms relevant to science areas. Graph algorithms are well known to be a promising research area for quantum computing. Motivated by a recently proposed graph-based electronic structure theory applied to quantum molecular dynamics (QMD) simulations, graph partitioning is used for reducing the calculation of the density matrix into smaller subsystems rendering the calculation more computationally efficient. We have shown that graph partitioning and community detection on the D-Wave 2000X quantum annealer equals or out-performs current state-of-the-art methods. Graph partitioning is important for data decomposition of distributed simulations running across nodes on HPC systems. Clustering or community detection provides for discovery of structure and relationships in graphs and data related to network problems and simulation outputs. These unsupervised machine learning techniques matched the best known results on benchmark networks, showed better results than state-of-the-art classical methods on random graphs, and excellent results for graphs from the electronic structure connectivity given by QMD density matrices. We introduce quantum annealing and present each graph algorithm as a quadratic unconstrained binary optimization (QUBO) formulation. Results are shown for quantum and quantum-classical approaches.

Quantum computing approaches to graph partitioning for electronic structure problems

Macromolecular Chemistry: The Second Century

[Author Benefits](https://scimeetings.acs.org/?utm_source=pubs_content_marketing&utm_medium=website&utm_campaign=0320_MCF_NPI_Launch_Spring_Homepage&ref=pubs_content_marketing)

[How to use SciMeetings](https://storage.googleapis.com/dl.morressier.com/acs/SciMeetings-ACSSpring2020-HowToGuide_M3020-Final.pdf)

[Frequently Asked Questions](https://storage.googleapis.com/dl.morressier.com/acs/SciMtng_ACSNMSp2020_FAQ_M3120_Final.pdf)

ACS Spring 2020 National Meeting & Expo

The official archive and repository for all ACS Meetings & Expositions abstracts and select posters or presentations.