Abstract
In quantum chemistry, the price paid by all known efficient model chemistries is either the truncation of the Hilbert space or uncontrolled approximations. Theoretical computer science suggests that these restrictions are not mere shortcomings of the algorithm designers and programmers but could stem from the inherent difficulty of simulating quantum systems. Extensions of computer science and information processing exploiting quantum mechanics has led to new ways of understanding the ultimate limitations of computational power. Interestingly, this perspective helps us understand widely used model chemistries in a new light. In this article, the fundamentals of computational complexity will be reviewed and motivated from the vantage point of chemistry. Then recent results from the computational complexity literature regarding common model chemistries including Hartree-Fock and density functional theory are discussed.
Introduction: The Fundamental Hardness of Chemistry
Quantum chemists have spent decades developing "model chemistries"—such as Hartree-Fock (HF) or Density Functional Theory (DFT)—to bypass the exponential cost of solving the Schrödinger equation exactly. While these methods are generally successful, they occasionally suffer from convergence issues or catastrophic failures. A central question arises: are these failures simply the result of suboptimal algorithm design, or do they reflect a fundamental mathematical barrier? By applying the lens of computational complexity, we can categorize the inherent difficulty of chemical simulations, providing a rigorous framework to understand when and why our traditional methods hit a wall.
Methodology: Computational Reduction and Mapping
The study of complexity in chemistry relies on computational reduction. This technique proves that if a chemical problem could be solved efficiently, it would also solve a known "hard" problem, such as the Traveling Salesman Problem. To bridge the gap between physical systems and computational models, researchers use techniques like the Jordan-Wigner transformation and orbital pair pseudo-spin mapping to translate electronic structures into systems of quantum spins (qubits).
The Taxonomy of Complexity
Problems are categorized into specific complexity classes based on the resources required to solve or verify them. Key classes include P (solvable in polynomial time on a classical computer), BQP (solvable on a quantum computer), and NP (solutions verifiable on a classical computer). In the quantum realm, QMA (Quantum Merlin-Arthur) represents the quantum analogue of NP, encompassing problems where a quantum "proof" can be verified by a quantum computer.
Complexity of Common Model Chemistries
Recent theoretical work has successfully categorized the "worst-case" complexity of the three pillars of quantum chemistry:
- Hartree-Fock (HF): Finding the global minimum energy in HF theory is NP-complete. This implies that, in the worst case, optimizing HF orbitals is as difficult as the most challenging optimization problems in computer science.
- N-representability (2-RDM Methods): A common simplification involves using 2-body Reduced Density Matrices (2-RDMs). However, determining if a given 2-RDM corresponds to a valid $N$-electron state is QMA-complete, making it one of the hardest problems a quantum computer could verify.
- Density Functional Theory (DFT): While DFT is the workhorse of modern chemistry, the "Universal Functional" that enables its efficiency is itself QMA-complete to compute. This explains the proliferation of functional approximations; a single, efficient, and exact functional likely does not exist.
Implications and Future Directions
These results provide a formal justification for the compromises made in quantum chemistry. To achieve efficiency, one must either restrict the search space (truncation) or utilize uncontrolled approximations. Crucially, the categorization of these problems as NP-hard or QMA-hard suggests that even perfect quantum computers (BQP) will not be a "silver bullet" for every chemical problem, as BQP is not expected to solve QMA-complete problems efficiently.
Future research aims to bridge the gap between these "worst-case" scenarios and the "average-case" molecules typically encountered in the lab. Furthermore, the "Quantum PCP Theorem" remains a frontier, potentially determining if even approximating these energies remains QMA-hard. Extending these rigorous classifications to excited states and reaction dynamics will be essential for a complete computational theory of chemistry.
Summary updated