Lab Home | Phone | Search
Center for Nonlinear Studies  Center for Nonlinear Studies
 Colloquia Archive 
 Postdoc Seminars Archive 
 Quantum Lunch 
 CMS Colloquia 
 Q-Mat Seminars 
 Q-Mat Seminars Archive 
 Kac Lectures 
 Dist. Quant. Lecture 
 Ulam Scholar 
 Summer Research 
 Student Application 
 Past Visitors 
 PD Travel Request 
 History of CNLS 
 Maps, Directions 
 CNLS Office 
Tuesday, July 23, 2019
09:30 AM - 10:30 AM
CNLS Conference Room (TA-3, Bldg 1690)


Combinatorics Algorithms on Near-term Quantum Architectures

Sue Mniszewski, Prosper Akrobotu, Jason Terry
Los Alamos National Laboratory

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 the LANL mission 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 using quantum annealing on the D-Wave 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. This opens up the opportunity to use quantum computers for combinatorial chemistry (under the more general classification of chemoinformatics). We start by exploring the problem of isomer search, a very important problem in pharmaceutical drug research. This involves searching for all the chemical structures that are plausible with a given number of atoms and composition (minimal formula). This problem is far from being trivial and involves a large computational effort since the possible isomers (search space) rapidly increases with the number of atoms. Basically, this search space is the space of all possible graphs which increases as 2n(n+1)/2 where n is the number of nodes involved. We present the isomer search problem representation for alkanes of the form CnH2n+2 with carbon-carbon connectivity, the QUBO Hamiltonian formulation, and results using the D-Wave quantum annealer. We were able to enumerate all the known structural isomers of alkanes with fewer carbons than Nonane (C9H20) and find that the sampling time scales linearly with the number of carbon atoms. We show that by employing reverse annealing as well as a perturbed QUBO Hamiltonian significantly reduces the number of samples required to collect all isomers.

Host: Information Science and Technology Institute (ISTI)