 |
Center for Nonlinear Studies |
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)