183
Part Five · Convergence

Why classical computers struggle: the exponential wall in molecular simulation

The FeMo cofactor of nitrogenase, the iron–molybdenum cluster that lets bacteria turn air into fertilizer, has been modelled with an active space of 113 electrons in 76 orbitals. The exact wavefunction in that space would need about 4×10354\times10^{35} numbers: more than all the computer memory that will ever exist. That is the exponential wall. Yet classical chemists have not given up, and their approximations keep improving. This chapter shows how high the wall is, where each method hits it, and why “exponential” does not automatically mean “quantum advantage”.

On the plate: the size of the exact problem as the active space grows.

Counting configurations

Full configuration interaction (FCI) writes the wavefunction as a combination of every way to place the electrons in the chosen orbitals. With MM spatial orbitals, NαN_\alpha spin-up and NβN_\beta spin-down electrons, the number of determinants is

D=(MNα)(MNβ)D = \binom{M}{N_\alpha}\binom{M}{N_\beta}

For half filling this grows roughly as 4M/M4^M/M. A 54-electron, 54-orbital space gives 3.8×10303.8\times10^{30}; FeMoco’s 113 electrons in 76 orbitals give 4.2×10354.2\times10^{35}. The largest exact FCI calculations handle around a trillion determinants. Choose the active space size M=M = 24 orbitals at half filling. Established

The methods and where they fail

Hartree–Fock costs about N4N^4, coupled cluster CCSD(T) about N7N^7, both polynomial, both excellent when one configuration dominates (Chapter 158). For strongly correlated systems, three families push further. The density matrix renormalization group (DMRG), a matrix-product-state method (Chapter 151), handles active spaces of 50–100 orbitals when entanglement is limited, and has been applied to FeMoco-sized models. Selected CI methods pick out the important determinants. Auxiliary-field quantum Monte Carlo (AFQMC) samples the wavefunction stochastically, with errors controlled by a trial state. Each fails in characteristic ways: DMRG when entanglement is high in every orbital ordering, selected CI when important determinants are too many, QMC through the sign problem. Established

The critique: is there an exponential advantage?

In 2023 Seunghoon Lee, Garnet Chan and colleagues examined the case for exponential quantum advantage in ground-state chemistry. Phase estimation needs an initial state with substantial overlap with the true ground state (Chapter 188). They argued that, for typical chemical systems, wherever such a state can be prepared efficiently, classical heuristics also tend to work; and where classical methods fail exponentially, preparing a good initial state may be hard too. They found no evidence of generic exponential speedup, while allowing that polynomial speedups, or advantages for specific systems, remain plausible. The wall is real; whether quantum computers climb it more cheaply than improving classical methods is open. Established for the wall; Debated for the advantage.

What you now have

The FCI dimension formula and its exponential growth, the FeMoco and CAS(54,54) numbers, cost scalings of HF, CCSD(T), DMRG, selected CI and AFQMC with their failure modes, and Lee et al.’s critique of exponential advantage.

· · ·

Three questions to carry with you.

How does the FCI dimension grow at half filling?tap
Roughly as 4^M / M for M orbitals.
When does DMRG fail?tap
When entanglement across every bipartition of the orbitals is high.
What is the core of Lee et al.’s critique?tap
Good initial states for phase estimation tend to exist where classical heuristics already succeed.

And one to work out. CAS(54e, 54o) has (5427)2=3.8×1030\binom{54}{27}^2 = 3.8\times10^{30} determinants. What is log⁡10\log_{10} of that?

log₁₀ D =

Sources: M. Reiher et al., Proc. Natl Acad. Sci. USA 114, 7555 (2017). Z. Li et al., Nat. Chem. 11, 1026 (2019) (DMRG on iron–sulfur clusters). S. Lee et al., Nat. Commun. 14, 1952 (2023). M. Motta and S. Zhang, WIREs Comput. Mol. Sci. 8, e1364 (2018) (AFQMC). Checked by code: C(76,57)·C(76,56) = 4.17 × 10³⁵; C(54,27)² = 3.79 × 10³⁰.

Next · Chapter 184
From a molecule to a Hamiltonian: the step-by-step translation

From a drawing of a molecule to a matrix a quantum computer can use, in 6 steps.

Turn the page