Computational Complexity in Electronic Structure

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.

14 pages, 2 figures, 1 table. Comments welcome

References in corpus (13)

• Matrix Product States, Projected Entangled Pair States, and variational renormalization group methods for quantum spin systems
• Simulated Quantum Computation of Molecular Energies
• Computational complexity and fundamental limitations to fermionic quantum Monte Carlo simulations
• Polynomial-time quantum algorithm for the simulation of chemical dynamics
• Simulating chemistry using quantum computers
• Structure of Fermionic Density Matrices: Complete N-representability Conditions
• N-representability is QMA-complete
• Realizable Hamiltonians for Universal Adiabatic Quantum Computers
• Using Quantum Computers for Quantum Simulation
• Quantum computing applied to calculations of molecular energies: CH2 benchmark
• The computational difficulty of finding MPS ground states
• Computational Difficulty of Computing the Density of States
• Significant Conditions on the Two-electron Reduced Density Matrix from the Constructive Solution of N-representability

Cited by in corpus (26)

• Quantum computational chemistry
• Quantum Chemistry in the Age of Quantum Computing
• Quantum information processing with superconducting circuits: a review
• Quantum optimization using variational algorithms on near-term quantum devices
• Quantum algorithms for electronic structure calculations: particle/hole Hamiltonian and optimized wavefunction expansions
• Quantum Implementation of Unitary Coupled Cluster for Simulating Molecular Electronic Structure
• From transistor to trapped-ion computers for quantum chemistry
• Adiabatic Quantum Simulation of Quantum Chemistry
• Pattern Learning Electronic Density of States
• Optimizing qubit resources for quantum chemistry simulations in second quantization on a quantum computer
• Introduction to Quantum Algorithms for Physics and Chemistry
• Tensors in computations
• Ultrafast ab-initio Quantum Chemistry Using Matrix Product States
• Spin-free quantum computational simulations and symmetry adapted states
• Quantum chemistry and charge transport in biomolecules with superconducting circuits
• Neural network backflow for ab-initio quantum chemistry
• What the foundations of quantum computer science teach us about chemistry
• Computational complexity of time-dependent density functional theory
• Density functionals and Kohn-Sham potentials with minimal wavefunction preparations on a quantum computer
• Computational complexity of non-equilibrium steady states of quantum spin chains
• Dequantizing the Quantum Singular Value Transformation: Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture
• Limitations of Hartree-Fock with quantum resources
• On the NP-completeness of the Hartree-Fock method for translationally invariant systems
• Statistical learnability of nuclear masses
• Entanglement spectrum of matchgate circuits with universal and non-universal resources
• Chemically Motivated Simulation Problems are Efficiently Solvable by a Quantum Computer