1
|
Li Y, Cui X, Xiong Z, Liu B, Wang BY, Shu R, Qiao N, Yung MH. Quantum Molecular Docking with a Quantum-Inspired Algorithm. J Chem Theory Comput 2024. [PMID: 39073856 DOI: 10.1021/acs.jctc.4c00141] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 07/30/2024]
Abstract
Molecular docking (MD) is a crucial task in drug design, which predicts the position, orientation, and conformation of the ligand when it is bound to a target protein. It can be interpreted as a combinatorial optimization problem, where quantum annealing (QA) has shown a promising advantage for solving combinatorial optimization. In this work, we propose a novel quantum molecular docking (QMD) approach based on a QA-inspired algorithm. We construct two binary encoding methods to efficiently discretize the degrees of freedom with an exponentially reduced number of bits and propose a smoothing filter to rescale the rugged objective function. We propose a new quantum-inspired algorithm, hopscotch simulated bifurcation (hSB), showing great advantages in optimizing over extremely rugged energy landscapes. This hSB can be applied to any formulation of an objective function under binary variables. An adaptive local continuous search is also introduced for further optimization of the discretized solution from hSB. Concerning the stability of docking, we propose a perturbation detection method to help rank the candidate poses. We demonstrate our approach on a typical data set. QMD has shown advantages over the search-based Autodock Vina and the deep-learning DIFFDOCK in both redocking and self-docking scenarios. These results indicate that quantum-inspired algorithms can be applied to solve practical problems in drug discovery even before quantum hardware become mature.
Collapse
Affiliation(s)
- Yunting Li
- Central Research Institute, Huawei Technologies, Shenzhen 518129, China
- State Key Laboratory of Surface Physics and Department of Physics, Fudan University, Shanghai 200433, China
| | - Xiaopeng Cui
- Central Research Institute, Huawei Technologies, Shenzhen 518129, China
| | - Zhaoping Xiong
- Laboratory of Health Intelligence, Huawei Cloud Computing Technologies Co., Ltd, Guizhou 550025, China
| | - Bowen Liu
- Central Research Institute, Huawei Technologies, Shenzhen 518129, China
| | - Bi-Ying Wang
- Central Research Institute, Huawei Technologies, Shenzhen 518129, China
| | - Runqiu Shu
- Central Research Institute, Huawei Technologies, Shenzhen 518129, China
| | - Nan Qiao
- Laboratory of Health Intelligence, Huawei Cloud Computing Technologies Co., Ltd, Guizhou 550025, China
| | - Man-Hong Yung
- Central Research Institute, Huawei Technologies, Shenzhen 518129, China
- Shenzhen Institute for Quantum Science and Engineering, Southern University of Science and Technology, Shenzhen 518055, China
- International Quantum Academy, Shenzhen 518048, China
- Guangdong Provincial Key Laboratory of Quantum Science and Engineering, Southern University of Science and Technology, Shenzhen 518055, China
- Shenzhen Key Laboratory of Quantum Science and Engineering, Southern University of Science and Technology, Shenzhen 518055, China
| |
Collapse
|
2
|
Ghamari D, Covino R, Faccioli P. Sampling a Rare Protein Transition Using Quantum Annealing. J Chem Theory Comput 2024; 20:3322-3334. [PMID: 38587482 DOI: 10.1021/acs.jctc.3c01174] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 04/09/2024]
Abstract
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.
Collapse
Affiliation(s)
- Danial Ghamari
- Physics Department, Trento University, Via Sommarive 14, Povo 38123, Trento, Italy
- INFN-TIFPA, Via Sommarive 14, Povo 38123, Trento, Italy
| | - Roberto Covino
- Frankfurt Institute for Advanced Studies, Ruth-Moufang-Straße 1 Frankfurt am Main, Frankfurt D-60438, Germany
- Department of Biochemistry, University of Bayreuth, Universitätsstraße 30, Bayreuth 95447, Germany
| | - Pietro Faccioli
- INFN-TIFPA, Via Sommarive 14, Povo 38123, Trento, Italy
- Bicocca Quantum Technology Center and Physics Department, University of Milan Bicocca, Piazza della Scienza 2/A, Milan 20126, Italy
| |
Collapse
|
3
|
Gusev VV, Adamson D, Deligkas A, Antypov D, Collins CM, Krysta P, Potapov I, Darling GR, Dyer MS, Spirakis P, Rosseinsky MJ. Optimality guarantees for crystal structure prediction. Nature 2023; 619:68-72. [PMID: 37407679 DOI: 10.1038/s41586-023-06071-y] [Citation(s) in RCA: 2] [Impact Index Per Article: 2.0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 07/19/2022] [Accepted: 04/04/2023] [Indexed: 07/07/2023]
Abstract
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 materials1,2. Researchers have developed efficient heuristics to identify structural minima on the potential energy surface3-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 programming6,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 annealers8-10, opening a path to overcome the combinatorial explosion of atomic configurations.
Collapse
Affiliation(s)
- Vladimir V Gusev
- Leverhulme Research Centre for Functional Materials Design, Materials Innovation Factory, University of Liverpool, Liverpool, UK
- Department of Computer Science, University of Liverpool, Liverpool, UK
| | - Duncan Adamson
- Leverhulme Research Centre for Functional Materials Design, Materials Innovation Factory, University of Liverpool, Liverpool, UK
| | - Argyrios Deligkas
- Leverhulme Research Centre for Functional Materials Design, Materials Innovation Factory, University of Liverpool, Liverpool, UK
- Department of Computer Science, Royal Holloway, University of London, London, UK
| | - Dmytro Antypov
- Leverhulme Research Centre for Functional Materials Design, Materials Innovation Factory, University of Liverpool, Liverpool, UK
| | | | - Piotr Krysta
- Department of Computer Science, University of Liverpool, Liverpool, UK
| | - Igor Potapov
- Department of Computer Science, University of Liverpool, Liverpool, UK
| | | | - Matthew S Dyer
- Leverhulme Research Centre for Functional Materials Design, Materials Innovation Factory, University of Liverpool, Liverpool, UK
- Department of Chemistry, University of Liverpool, Liverpool, UK
| | - Paul Spirakis
- Leverhulme Research Centre for Functional Materials Design, Materials Innovation Factory, University of Liverpool, Liverpool, UK.
- Department of Computer Science, University of Liverpool, Liverpool, UK.
| | - Matthew J Rosseinsky
- Leverhulme Research Centre for Functional Materials Design, Materials Innovation Factory, University of Liverpool, Liverpool, UK.
- Department of Chemistry, University of Liverpool, Liverpool, UK.
| |
Collapse
|
4
|
Wang J, Ebler D, Wong KYM, Hui DSW, Sun J. Bifurcation behaviors shape how continuous physical dynamics solves discrete Ising optimization. Nat Commun 2023; 14:2510. [PMID: 37130854 PMCID: PMC10154334 DOI: 10.1038/s41467-023-37695-3] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 05/29/2022] [Accepted: 03/28/2023] [Indexed: 05/04/2023] Open
Abstract
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.
Collapse
Affiliation(s)
- Juntao Wang
- Theory Lab, Central Research Institute, 2012 Labs, Huawei Technologies Co. Ltd., Hong Kong SAR, China
- Department of Physics, Hong Kong University of Science and Technology, Hong Kong SAR, China
| | - Daniel Ebler
- Theory Lab, Central Research Institute, 2012 Labs, Huawei Technologies Co. Ltd., Hong Kong SAR, China.
| | - K Y Michael Wong
- Department of Physics, Hong Kong University of Science and Technology, Hong Kong SAR, China
| | - David Shui Wing Hui
- Theory Lab, Central Research Institute, 2012 Labs, Huawei Technologies Co. Ltd., Hong Kong SAR, China
| | - Jie Sun
- Theory Lab, Central Research Institute, 2012 Labs, Huawei Technologies Co. Ltd., Hong Kong SAR, China.
| |
Collapse
|
5
|
Micheletti C, Hauke P, Faccioli P. Polymer Physics by Quantum Computing. PHYSICAL REVIEW LETTERS 2021; 127:080501. [PMID: 34477421 DOI: 10.1103/physrevlett.127.080501] [Citation(s) in RCA: 3] [Impact Index Per Article: 1.0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Received: 04/20/2021] [Revised: 06/21/2021] [Accepted: 07/06/2021] [Indexed: 06/13/2023]
Abstract
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.
Collapse
Affiliation(s)
- Cristian Micheletti
- Scuola Internazionale Superiore di Studi Avanzati (SISSA), Via Bonomea 265, I-34136 Trieste, Italy
| | - Philipp Hauke
- Physics Department of Trento University and INO-CNR BEC Center, Via Sommarive 14, I-38123 Povo (Trento), Italy
| | - Pietro Faccioli
- Physics Department of Trento University and INFN-TIFPA, Via Sommarive 14, I-38123 Povo (Trento), Italy
| |
Collapse
|
6
|
Cao Y, Romero J, Olson JP, Degroote M, Johnson PD, Kieferová M, Kivlichan ID, Menke T, Peropadre B, Sawaya NPD, Sim S, Veis L, Aspuru-Guzik A. Quantum Chemistry in the Age of Quantum Computing. Chem Rev 2019; 119:10856-10915. [PMID: 31469277 DOI: 10.1021/acs.chemrev.8b00803] [Citation(s) in RCA: 283] [Impact Index Per Article: 56.6] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 01/14/2023]
Abstract
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.
Collapse
Affiliation(s)
- Yudong Cao
- Department of Chemistry and Chemical Biology , Harvard University , Cambridge , Massachusetts 02138 , United States.,Zapata Computing Inc. , Cambridge , Massachusetts 02139 , United States
| | - Jonathan Romero
- Department of Chemistry and Chemical Biology , Harvard University , Cambridge , Massachusetts 02138 , United States.,Zapata Computing Inc. , Cambridge , Massachusetts 02139 , United States
| | - Jonathan P Olson
- Department of Chemistry and Chemical Biology , Harvard University , Cambridge , Massachusetts 02138 , United States.,Zapata Computing Inc. , Cambridge , Massachusetts 02139 , United States
| | - Matthias Degroote
- Department of Chemistry and Chemical Biology , Harvard University , Cambridge , Massachusetts 02138 , United States.,Department of Chemistry , University of Toronto , Toronto , Ontario M5G 1Z8 , Canada.,Department of Computer Science , University of Toronto , Toronto , Ontario M5G 1Z8 , Canada
| | - Peter D Johnson
- Department of Chemistry and Chemical Biology , Harvard University , Cambridge , Massachusetts 02138 , United States.,Zapata Computing Inc. , Cambridge , Massachusetts 02139 , United States
| | - Mária Kieferová
- Zapata Computing Inc. , Cambridge , Massachusetts 02139 , United States.,Department of Physics and Astronomy , Macquarie University , Sydney , NSW 2109 , Australia.,Institute for Quantum Computing and Department of Physics and Astronomy , University of Waterloo , Waterloo , Ontario N2L 3G1 , Canada
| | - Ian D Kivlichan
- Department of Chemistry and Chemical Biology , Harvard University , Cambridge , Massachusetts 02138 , United States.,Department of Physics , Harvard University , Cambridge , Massachusetts 02138 , United States
| | - Tim Menke
- Department of Physics , Harvard University , Cambridge , Massachusetts 02138 , United States.,Research Laboratory of Electronics , Massachusetts Institute of Technology , Cambridge , Massachusetts 02139 , United States.,Department of Physics , Massachusetts Institute of Technology , Cambridge , Massachusetts 02139 , United States
| | - Borja Peropadre
- Zapata Computing Inc. , Cambridge , Massachusetts 02139 , United States
| | - Nicolas P D Sawaya
- Intel Laboratories , Intel Corporation , Santa Clara , California 95054 United States
| | - Sukin Sim
- Department of Chemistry and Chemical Biology , Harvard University , Cambridge , Massachusetts 02138 , United States.,Zapata Computing Inc. , Cambridge , Massachusetts 02139 , United States
| | - Libor Veis
- J. Heyrovský Institute of Physical Chemistry , Academy of Sciences of the Czech Republic v.v.i. , Doleǰskova 3 , 18223 Prague 8, Czech Republic
| | - Alán Aspuru-Guzik
- Department of Chemistry and Chemical Biology , Harvard University , Cambridge , Massachusetts 02138 , United States.,Zapata Computing Inc. , Cambridge , Massachusetts 02139 , United States.,Department of Chemistry , University of Toronto , Toronto , Ontario M5G 1Z8 , Canada.,Department of Computer Science , University of Toronto , Toronto , Ontario M5G 1Z8 , Canada.,Canadian Institute for Advanced Research , Toronto , Ontario M5G 1Z8 , Canada.,Vector Institute for Artificial Intelligence , Toronto , Ontario M5S 1M1 , Canada
| |
Collapse
|
7
|
McClean JR, Babbush R, Love PJ, Aspuru-Guzik A. Exploiting Locality in Quantum Computation for Quantum Chemistry. J Phys Chem Lett 2014; 5:4368-80. [PMID: 26273989 DOI: 10.1021/jz501649m] [Citation(s) in RCA: 27] [Impact Index Per Article: 2.7] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 05/26/2023]
Abstract
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.
Collapse
Affiliation(s)
- Jarrod R McClean
- †Department of Chemistry and Chemical Biology, Harvard University, Cambridge, Massachusetts 02138, United States
| | - Ryan Babbush
- †Department of Chemistry and Chemical Biology, Harvard University, Cambridge, Massachusetts 02138, United States
| | - Peter J Love
- ‡Department of Physics, Haverford College, Haverford, Pennsylvania 19041, United States
| | - Alán Aspuru-Guzik
- †Department of Chemistry and Chemical Biology, Harvard University, Cambridge, Massachusetts 02138, United States
| |
Collapse
|