Computational Complexity in Electronic Structure
arXiv:1208.3334 · doi:10.1039/C2CP42695A
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.
arXiv comment14 pages, 2 figures, 1 table. Comments welcome
References in corpus (27)
- 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
- Fermionic quantum computation
- Efficient quantum algorithms for simulating sparse Hamiltonians
- Simulation of Electronic Structure Hamiltonians Using Quantum Computers
- Polynomial-time quantum algorithm for the simulation of chemical dynamics
- Simulating Physical Phenomena by Quantum Networks
- Simulating chemistry using quantum computers
- Quantum Algorithms for Fermionic Simulations
- The computational complexity of PEPS
- Computational Complexity of interacting electrons and fundamental limitations of Density Functional Theory
- Structure of Fermionic Density Matrices: Complete N-representability Conditions
- N-representability is QMA-complete
- Mapping local Hamiltonians of fermions to local Hamiltonians of spins
- Realizable Hamiltonians for Universal Adiabatic Quantum Computers
- Generalized Jordan-Wigner Transformations
- Quantum phase transitions in transverse field spin models: from statistical physics to quantum information
- Hamiltonian complexity
- Using Quantum Computers for Quantum Simulation
- Polynomial-Time Simulation of Pairing Models on a Quantum Computer
- Quantum computing applied to calculations of molecular energies: CH2 benchmark
- The computational difficulty of finding MPS ground states
- Interacting boson problems are QMA-hard
- Adiabatic Quantum Simulators
- 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