Investigating the potential for a limited quantum speedup on protein lattice problems
arXiv:2004.01118 · doi:10.1088/1367-2630/ac29ff
Abstract
Protein folding is a central challenge in computational biology, with important applications in molecular biology, drug discovery and catalyst design. As a hard combinatorial optimisation problem, it has been studied as a potential target problem for quantum annealing. Although several experimental implementations have been discussed in the literature, the computational scaling of these approaches has not been elucidated. In this article, we present a numerical study of quantum annealing applied to a large number of small peptide folding problems, aiming to infer useful insights for near-term applications. We present two conclusions: that even naive quantum annealing, when applied to protein lattice folding, has the potential to outperform classical approaches, and that careful engineering of the Hamiltonians and schedules involved can deliver notable relative improvements for this problem. Overall, our results suggest that quantum algorithms may well offer improvements for problems in the protein folding and structure prediction realm.
arXiv comment45 pages, 18 figures
References in corpus (24)
- A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
- Adiabatic Quantum Computing
- Quantum Search by Local Adiabatic Evolution
- Defining and detecting quantum speedup
- Computational Role of Multiqubit Tunneling in a Quantum Annealer
- Demonstration of a scaling advantage for a quantum annealer over simulated annealing
- Error corrected quantum annealing with hundreds of qubits
- First order phase transition in the Quantum Adiabatic Algorithm
- How Powerful is Adiabatic Quantum Computation?
- Quantum Adiabatic Brachistochrone
- Error correcting codes for adiabatic quantum computation
- PETSc/TS: A Modern Scalable ODE/DAE Solver Library
- Towards Fault Tolerant Adiabatic Quantum Computation
- Prospects for Quantum Enhancement with Diabatic Quantum Annealing
- Size dependence of the minimum excitation gap in the Quantum Adiabatic Algorithm
- On the construction of model Hamiltonians for adiabatic quantum computation and its application to finding low energy conformations of lattice protein models
- Nonstoquastic Hamiltonians and Quantum Annealing of an Ising Spin Glass
- Tunneling and speedup in quantum optimization for permutation-symmetric problems
- Demonstration of Adiabatic Variational Quantum Computing with a Superconducting Quantum Coprocessor
- Role of Non-stoquastic Catalysts in Quantum Adiabatic Optimization
- Error suppression for Hamiltonian-based quantum computation using subsystem codes
- Non-commuting two-local Hamiltonians for quantum error suppression
- Coarse-grained lattice protein folding on a quantum annealer
- De-Signing Hamiltonians for Quantum Adiabatic Optimization