Due to intense interest in the potential applications of quantum computing, it is critical to understand the basis for potential exponential quantum advantage in quantum chemistry. Here we gather the evidence for this case in the most common task in quantum chemistry, namely, ground-state energy estimation, for generic chemical problems where heuristic quantum state preparation might be assumed to be efficient. The availability of exponential quantum advantage then centers on whether features of the physical problem that enable efficient heuristic quantum state preparation also enable efficient solution by classical heuristics. Through numerical studies of quantum state preparation and empirical complexity analysis (including the error scaling) of classical heuristics, in both ab initio and model Hamiltonian settings, we conclude that evidence for such an exponential advantage across chemical space has yet to be found. While quantum computers may still prove useful for ground-state quantum chemistry through polynomial speedups, it may be prudent to assume exponential speedups are not generically available for this problem.
This content will become publicly available on July 1, 2025
- Award ID(s):
- 2142846
- NSF-PAR ID:
- 10529156
- Publisher / Repository:
- Cell
- Date Published:
- Journal Name:
- Cell Reports Physical Science
- ISSN:
- 2666-3864
- Page Range / eLocation ID:
- 102105
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
more » « less
Abstract -
One of the most fundamental problems that has no efficient solutions on classical computers is simulation of quantum systems. It has been long hypothesized that quantum computing devices are naturally more suitable for this task, but many aspects of practical implementations of such simulations remain unknown. One particularly important kind of these simulations is the simulation of molecular dynamics, i.e. prediction of time evolution for a system of interacting particles. In this work we show how a quantum annealer can be used to carry out such simulations by solving differential equations of motion, on the example of the hydrogen molecule. Although the considered system is simple, our method is well scalable and can be readily applied to more complicated systems as annealers with larger number of qubits become available. Importantly, the method is general and can be used to solve arbitrary systems of ordinary non-linear differential equations, which can be helpful not only in the field of computational chemistry, but in many other fields as well.more » « less
-
null (Ed.)Quantum computing is poised to dramatically change the computational landscape, worldwide. Quantum computers can solve complex problems that are, at least in some cases, beyond the ability of even advanced future classical-style computers. In addition to being able to solve these classical computer-unsolvable problems, quantum computers have demonstrated a capability to solve some problems (such as prime factoring) much more efficiently than classical computing. This will create problems for encryption techniques, which depend on the difficulty of factoring for their security. Security, scientific, and other applications will require access to quantum computing resources to access their unique capabilities, speed and economic (aggregate computing time cost) benefits. Many scientific applications, as well as numerous other ones, use grid computing to provide benefits such as scalability and resource access. As these applications may benefit from quantum capabilities - and some future applications may require quantum capabilities - identifying how to integrate quantum computing systems into grid computing environments is critical. This paper discusses the benefits of grid-connected quantum computers and what is required to achieve this.more » « less
-
more » « less
Abstract Quantum Approximate Optimization algorithm (QAOA) aims to search for approximate solutions to discrete optimization problems with near-term quantum computers. As there are no algorithmic guarantee possible for QAOA to outperform classical computers, without a proof that bounded-error quantum polynomial time (BQP) ≠ nondeterministic polynomial time (NP), it is necessary to investigate the empirical advantages of QAOA. We identify a computational phase transition of QAOA when solving hard problems such as SAT—random instances are most difficult to train at a critical problem density. We connect the transition to the controllability and the complexity of QAOA circuits. Moreover, we find that the critical problem density in general deviates from the SAT-UNSAT phase transition, where the hardest instances for classical algorithms lies. Then, we show that the high problem density region, which limits QAOA’s performance in hard optimization problems (reachability deficits), is actually a good place to utilize QAOA: its approximation ratio has a much slower decay with the problem density, compared to classical approximate algorithms. Indeed, it is exactly in this region that quantum advantages of QAOA over classical approximate algorithms can be identified.
-
null (Ed.)Chemistry is considered as one of the more promising applications to science of near-term quantum computing. Recent work in transitioning classical algorithms to a quantum computer has led to great strides in improving quantum algorithms and illustrating their quantum advantage. Because of the limitations of near-term quantum computers, the most effective strategies split the work over classical and quantum computers. There is a proven set of methods in computational chemistry and materials physics that has used this same idea of splitting a complex physical system into parts that are treated at different levels of theory to obtain solutions for the complete physical system for which a brute force solution with a single method is not feasible. These methods are variously known as embedding, multi-scale, and fragment techniques and methods. We review these methods and then propose the embedding approach as a method for describing complex biochemical systems, with the parts not only treated with different levels of theory, but computed with hybrid classical and quantum algorithms. Such strategies are critical if one wants to expand the focus to biochemical molecules that contain active regions that cannot be properly explained with traditional algorithms on classical computers. While we do not solve this problem here, we provide an overview of where the field is going to enable such problems to be tackled in the future.more » « less
