Source-linked AI summary
Computational Complexity of interacting electrons and fundamental limitations of Density Functional Theory
Norbert Schuch, Frank Verstraete
TL;DR
The paper asks whether DFT can have a generally applicable, efficiently computable universal functional for interacting electrons. It uses complexity reductions from QMA-hard Hamiltonians to the Hubbard model and connects that model to the Schrödinger equation. The resulting hardness establishes fundamental computational limits on such an efficient DFT description.
Problem
The paper examines the computational difficulty of approximating ground-state energies for interacting-electron systems and the resulting limits on efficiently computing DFT’s universal functional.
Method
The authors reduce QMA-complete Hamiltonian problems through perturbative gadgets to the Hubbard model with local magnetic fields, then relate that model to the Schrödinger equation.
Results
The reductions establish polynomial-precision hardness for the Hubbard model and support the claimed computational limitations on an efficient universal functional.
Takeaways & Limitations
An efficiently computable universal functional would provide an efficient route to solving ground-state problems that are hard for QMA.
Abstract
from arXiv · showhide
One of the central problems in quantum mechanics is to determine the ground state properties of a system of electrons interacting via the Coulomb potential. Since its introduction by Hohenberg, Kohn, and Sham, Density Functional Theory (DFT) has become the most widely used and successful method for simulating systems of interacting electrons, making their original work one of the most cited in physics. In this letter, we show that the field of computational complexity imposes fundamental limitations on DFT, as an efficient description of the associated universal functional would allow to solve any problem in the class QMA (the quantum version of NP) and thus particularly any problem in NP in polynomial time. This follows from the fact that finding the ground state energy of the Hubbard model in an external magnetic field is a hard problem even for a quantum computer, while given the universal functional it can be computed efficiently using DFT. This provides a clear illustration how the field of quantum computing is useful even if quantum computers would never be built.
APPENDIX: NP-completeness of Hartree-Fock
The appendix shows that deciding the Hartree–Fock ground-state energy is NP-complete at polynomial precision, using an encoding of Ising spin glasses into fermionic systems.
- Complexity result: Approximating the Hartree–Fock ground-state energy is NP-complete for polynomial accuracy and two-particle interactions.The problem remains in NP for exponentially small accuracy gaps, while NP-completeness requires b−a < 1/poly(N) and r=2.
- Membership in NP: A Hartree–Fock state is characterized by coefficients u_ij, allowing its energy to be computed efficiently and placing the decision problem in NP.
- NP-hardness: NP-hardness follows by mapping the problem to the ground-state problem of Ising spin glasses.
- Reduction: The reduction embeds 2L^2 classical spins into 2N fermionic modes, using double-occupancy penalties to encode one effective spin per mode pair.The penalty term λn^2_i n^2_i+1 has λ=O(N^2).
- Precision: Because the encoded classical spin system has a constant gap and perturbative corrections are O(1/λ^2), polynomial precision suffices for NP-hardness.
1. Second order perturbation theory
The perturbative framework projects a Hamiltonian with a high-energy sector onto an effective low-energy Hamiltonian, with errors controlled by the perturbation-to-gap ratio.
- Setup: The Hamiltonian is decomposed into low- and high-energy sectors, with H_1 separated by a gap Δ≫v from H_0.The perturbation V has norm bounded by v.
- Effective theory: To second order, the effective low-energy Hamiltonian is H_eff=H_0+V_0−V_01H_1^-1V_10.
- Construction: A unitary rotation U=e^S is chosen to make the total Hamiltonian approximately block diagonal.
- Error control: The low-energy spectrum is approximated by the block-diagonal Hamiltonian up to an operator-norm error O(v^3/Δ^2).
- Scaling caveat: For an extensive N-qubit system, the error bound depends on N because the perturbation strength scales as v∝N.
2. Gadgets
The gadget construction progressively transforms arbitrary Pauli couplings into Heisenberg interactions while controlling errors through strong local fields and perturbative scaling.
- Gadget composition: Each gadget layer can be applied simultaneously because second-order processes do not produce cross-gadget terms.The transition term excites one qubit, and returning to the ground subspace requires hopping within the same gadget.
- Pauli coupling gadget: A three-qubit mediator gadget generates a tunable Pauli coupling λ_T A⊗B from two restricted couplings and a strong local field.The coupling strength is tuned through the field-state parameter φ.
- Pauli coupling gadget: Choosing λ_P=N^4q and B_P=N^8q gives total error O(1/Nq), below the target precision O(1/q).
- Interaction reductions: The next gadgets reduce unequal Pauli couplings to Ising interactions and then to XX-type interactions using strong fields in selected directions.
- Heisenberg reduction: The XX-type interaction is converted into an antiferromagnetic Heisenberg interaction by a strong Z field, with an additional local-field correction.
- Overall construction: Combining the gadgets reduces each Pauli coupling to a line of 16 Heisenberg couplings with variable local fields.The authors note that higher-order perturbation theory could reduce field magnitudes and chain length.
3. Erasure gadget
The erasure gadget converts a sparse Heisenberg lattice into a full 2D lattice by energetically decoupling selected qubits, while preserving polynomial precision.
- Erasure construction: Strong fields H=B_e(1−σ_z)/2 are applied to qubits that should be erased from the sparse lattice.
- Effective Hamiltonian: Projecting out the erased qubits yields the sparse-lattice Heisenberg Hamiltonian with an error O(∥V∥^2/B_e).
- Error control: With ∥V∥≤Nλ_H and suitable B_e, the total error is O(1/Nq).
4. Reduction from Heisenberg to Hubbard model
The Hubbard model with local magnetic fields is obtained from the Heisenberg model through perturbative reductions and mode transformations. In the half-occupancy, large-U regime, the Hubbard model reproduces effective antiferromagnetic Heisenberg couplings.
- 4. Reduction from Heisenberg to Hubbard model: The Hubbard lattice modes are ordered rowwise with spin-up before spin-down before applying the Jordan-Wigner transform.This produces a one-dimensional ordering of the model's fermionic modes.
- 4. Reduction from Heisenberg to Hubbard model: At half occupancy, each site contains one electron, allowing the ground-state subspace to be interpreted as a system of spin-1/2 particles.The condition is enforced in the regime U ≫ t and magnetic-field strength.
- 4. Reduction from Heisenberg to Hubbard model: Second-order hopping processes connect the relevant two-site states and generate the effective spin interaction.The magnetic term contributes at first order, while the hopping contribution is evaluated through second-order perturbation theory.
- 4. Reduction from Heisenberg to Hubbard model: The resulting effective interaction is, up to a constant, the antiferromagnetic Heisenberg Hamiltonian with coupling 2t^2/U.The construction chooses U as a polynomially large function of the system size to control the reduction.
- 4. Reduction from Heisenberg to Hubbard model: Applying the gadgets together introduces no cross-terms at second order because transitions returning to the ground subspace occur within individual gadgets.The stated parameter scaling ensures the associated errors remain controlled.
5. Reduction of the Hubbard model to the Schr¨odinger equation
The Hubbard model is embedded into a Schrödinger equation by constructing an exactly solvable lowest-band hopping model and engineering magnetic and Coulomb terms. Projection onto the lowest band yields the desired Hubbard parameters with controlled polynomially small energy error.
- 5. Reduction of the Hubbard model to the Schr¨odinger equation: The reduction targets Hubbard parameters t = N^-τ, U = const. × N^-ζ, B_max = O(N^-τ), and energy precision O(N^-2ζ+2), with 0 < ζ < τ − 3.These scalings specify the accuracy and parameter regime required for the construction.
- 5. Reduction of the Hubbard model to the Schr¨odinger equation: An exactly solvable Kronig-Penney construction produces a lowest Bloch band whose Wannier functions realize the hopping Hamiltonian on a lattice.The construction begins in one dimension and is extended using a separable three-dimensional potential to obtain a two-dimensional lattice.
- 5. Reduction of the Hubbard model to the Schr¨odinger equation: The spin degree of freedom is added as an additional Wannier-function index before engineering the magnetic potential.The resulting magnetic matrix elements reproduce local spin fields while suppressing unwanted intersite contributions.
- 5. Reduction of the Hubbard model to the Schr¨odinger equation: The Coulomb interaction is tuned by spatial rescaling so that its on-site matrix element supplies the Hubbard repulsion.The on-site Coulomb coefficient is given as 0.8984(...)N^-ζ plus a controlled error term.
- 5. Reduction of the Hubbard model to the Schr¨odinger equation: The Coulomb prefactor c_U = 28.7496(...) can be computed to accuracy ε in time 1/poly(ε), supporting an efficient reduction.The numerical evaluation uses a bounded integrand and derivatives.
- 5. Reduction of the Hubbard model to the Schr¨odinger equation: Combining the construction steps gives t = N^-τ, U = 0.8984(...)N^-ζ, the desired magnetic fields, and total energy error O(N^-2ζ+2).The parameterized effective Hamiltonian is the target Hubbard model.
- 5. Reduction of the Hubbard model to the Schr¨odinger equation: The hardness result applies to spin-density functional theory, which omits coupling between the magnetic field and electron orbital motion.The authors note that orbital coupling would produce Peierls phases contributing only from fourth-order perturbation theory onward.