Construction of Energy Functions for Lattice Heteropolymer Models: Efficient Encodings for Constraint Satisfaction Programming and Quantum Annealing

Sampling a Rare Protein Transition Using Quantum Annealing

Simulating spontaneous structural rearrangements in macromolecules with classical molecular dynamics is an outstanding challenge. Conventional supercomputers can access time intervals of up to tens of μs, while many key events occur on exponentially longer time scales. Path sampling techniques have the advantage of focusing the computational power on barrier-crossing trajectories, but generating uncorrelated transition paths that explore diverse conformational regions remains a problem. We employ a hybrid path-sampling paradigm that addresses this issue by generating trial transition paths using a quantum annealing (QA) machine. We first employ a classical computer to perform an uncharted exploration of the conformational space. The data set generated in this exploration is then postprocessed using a path integral-based method to yield a coarse-grained network representation of the reactive kinetics. By resorting to a quantum annealer, quantum superposition can be exploited to encode all of the transition pathways in the initial quantum state, thus potentially solving the path exploration problem. Furthermore, each QA cycle yields a completely uncorrelated trial trajectory. We previously validated this scheme on a prototypically simple transition, which could be extensively characterized on a desktop computer. Here, we scale up in complexity and perform an all-atom simulation of a protein conformational transition that occurs on the millisecond time scale, obtaining results that match those of the Anton special-purpose supercomputer. Despite limitations due to the available quantum annealers, our study highlights how realistic biomolecular simulations provide potentially impactful new ground for applying, testing, and advancing quantum technologies.

Optimality guarantees for crystal structure prediction

Crystalline materials enable essential technologies, and their properties are determined by their structures. Crystal structure prediction can thus play a central part in the design of new functional materials^1,2. Researchers have developed efficient heuristics to identify structural minima on the potential energy surface^3-5. Although these methods can often access all configurations in principle, there is no guarantee that the lowest energy structure has been found. Here we show that the structure of a crystalline material can be predicted with energy guarantees by an algorithm that finds all the unknown atomic positions within a unit cell by combining combinatorial and continuous optimization. We encode the combinatorial task of finding the lowest energy periodic allocation of all atoms on a lattice as a mathematical optimization problem of integer programming^6,7, enabling guaranteed identification of the global optimum using well-developed algorithms. A single subsequent local minimization of the resulting atom allocations then reaches the correct structures of key inorganic materials directly, proving their energetic optimality under clear assumptions. This formulation of crystal structure prediction establishes a connection to the theory of algorithms and provides the absolute energetic status of observed or predicted materials. It provides the ground truth for heuristic or data-driven structure prediction methods and is uniquely suitable for quantum annealers^8-10, opening a path to overcome the combinatorial explosion of atomic configurations.

Bifurcation behaviors shape how continuous physical dynamics solves discrete Ising optimization

Simulating physical dynamics to solve hard combinatorial optimization has proven effective for medium- to large-scale problems. The dynamics of such systems is continuous, with no guarantee of finding optimal solutions of the original discrete problem. We investigate the open question of when simulated physical solvers solve discrete optimizations correctly, with a focus on coherent Ising machines (CIMs). Having established the existence of an exact mapping between CIM dynamics and discrete Ising optimization, we report two fundamentally distinct bifurcation behaviors of the Ising dynamics at the first bifurcation point: either all nodal states simultaneously deviate from zero (synchronized bifurcation) or undergo a cascade of such deviations (retarded bifurcation). For synchronized bifurcation, we prove that when the nodal states are uniformly bounded away from the origin, they contain sufficient information for exactly solving the Ising problem. When the exact mapping conditions are violated, subsequent bifurcations become necessary and often cause slow convergence. Inspired by those findings, we devise a trapping-and-correction (TAC) technique to accelerate dynamics-based Ising solvers, including CIMs and simulated bifurcation. TAC takes advantage of early bifurcated "trapped nodes" which maintain their sign throughout the Ising dynamics to reduce computation time effectively. Using problem instances from open benchmark and random Ising models, we validate the superior convergence and accuracy of TAC.

Polymer Physics by Quantum Computing

Sampling equilibrium ensembles of dense polymer mixtures is a paradigmatically hard problem in computational physics, even in lattice-based models. Here, we develop a formalism based on interacting binary tensors that allows for tackling this problem using quantum annealing machines. Our approach is general in that properties such as self-avoidance, branching, and looping can all be specified in terms of quadratic interactions of the tensors. Microstates' realizations of different lattice polymer ensembles are then seamlessly generated by solving suitable discrete energy-minimization problems. This approach enables us to capitalize on the strengths of quantum annealing machines, as we demonstrate by sampling polymer mixtures from low to high densities, using the D-Wave quantum annealer. Our systematic approach offers a promising avenue to harness the rapid development of quantum machines for sampling discrete models of filamentous soft-matter systems.

Quantum Chemistry in the Age of Quantum Computing

Practical challenges in simulating quantum systems on classical computers have been widely recognized in the quantum physics and quantum chemistry communities over the past century. Although many approximation methods have been introduced, the complexity of quantum mechanics remains hard to appease. The advent of quantum computation brings new pathways to navigate this challenging and complex landscape. By manipulating quantum states of matter and taking advantage of their unique features such as superposition and entanglement, quantum computers promise to efficiently deliver accurate results for many important problems in quantum chemistry, such as the electronic structure of molecules. In the past two decades, significant advances have been made in developing algorithms and physical hardware for quantum computing, heralding a revolution in simulation of quantum systems. This Review provides an overview of the algorithms and results that are relevant for quantum chemistry. The intended audience is both quantum chemists who seek to learn more about quantum computing and quantum computing researchers who would like to explore applications in quantum chemistry.

Exploiting Locality in Quantum Computation for Quantum Chemistry

Accurate prediction of chemical and material properties from first-principles quantum chemistry is a challenging task on traditional computers. Recent developments in quantum computation offer a route toward highly accurate solutions with polynomial cost; however, this solution still carries a large overhead. In this Perspective, we aim to bring together known results about the locality of physical interactions from quantum chemistry with ideas from quantum computation. We show that the utilization of spatial locality combined with the Bravyi-Kitaev transformation offers an improvement in the scaling of known quantum algorithms for quantum chemistry and provides numerical examples to help illustrate this point. We combine these developments to improve the outlook for the future of quantum chemistry on quantum computers.