126
Part Three · B · Algorithms

Quantum simulation overview (detail in Part 5)

In a 1981 lecture at MIT, published the next year, Richard Feynman pointed out that simulating quantum physics on a classical computer seems to require resources that grow exponentially with the size of the system, and he ended with a line that became a slogan: nature isn’t classical, dammit, and if you want to make a simulation of nature, you’d better make it quantum mechanical. Four decades of algorithms later, simulating quantum matter and molecules remains the most credible use of a quantum computer. Part 5 treats it in depth; this chapter is the map.

On the plate: the memory a classical computer needs to hold a quantum state.

The exponential wall

A state of nn qubits has 2n2^n complex amplitudes. At 16 bytes each, set n=n = 30. Thirty qubits fit in a laptop’s memory; around fifty fill the largest supercomputers; eighty exceed every computer that could be built. Classical methods escape the wall only when the state has special structure: little entanglement (tensor networks), a positive sign structure (quantum Monte Carlo), or weak correlation (density functional theory). Many important problems have none of these. Established

Analog and digital

Analog simulators build a controllable system whose Hamiltonian mimics the target: cold atoms in optical lattices, trapped-ion spin chains, Rydberg arrays. They reach hundreds of particles but each machine simulates a family of models, with limited ability to check errors. Digital simulators run Trotter or more advanced circuits (Chapter 118) on a universal processor, which is flexible and error-correctable but costly in gates. Iulia Georgescu, Sahel Ashhab and Franco Nori reviewed both in 2014. The problem classes: lattice models of electrons and magnets, quantum chemistry (Part 5), nuclear and particle physics, and dynamics far from equilibrium. Established

A taste: the Hubbard model

The Fermi–Hubbard model, electrons hopping on a lattice and paying energy UU to share a site, may hold the secret of high-temperature superconductors and is beyond exact classical solution at large sizes. On an 8-site ring, start a spin-up and a spin-down electron on the same site, with U=U = 8.0 (in units of the hopping). At U=0U = 0 they spread independently and the double occupancy falls to about 0.2. At U=8U = 8 it stays near 0.9: energy conservation forbids the pair from breaking up, so it moves as a bound “doublon” despite repulsion. Cold-atom experiments observed such repulsively bound pairs in 2006.

The current frontier: in October 2025 Google reported in Nature a measurement of an out-of-time-order correlator, a probe of how information scrambles, on 65 qubits, estimated at 13,000 times faster than the best classical simulation and checkable on another quantum device. Independent assessment of the classical cost is pending. Debated

What you now have

Feynman’s argument, the exponential memory wall, the structures that let classical methods escape it, analog versus digital simulation, the main problem classes, a Hubbard example with a bound pair, and the current claims at the frontier.

· · ·

Three questions to carry with you.

Why is simulation the most credible application?tap
The input is a physical Hamiltonian, not loaded data, and the classical cost is exponential for generic strongly correlated systems.
When can classical methods cope?tap
With low entanglement, no sign problem, or weak correlation.
Why does a repulsive pair stay together on a lattice?tap
Its energy U lies outside the band of two separated particles, so conservation of energy prevents it from splitting.

And one to work out. How many gigabytes (10⁹ bytes) hold a 30-qubit state at 16 bytes per amplitude?

GB ≈

Sources: R. P. Feynman, Int. J. Theor. Phys. 21, 467 (1982). I. M. Georgescu, S. Ashhab and F. Nori, Rev. Mod. Phys. 86, 153 (2014). K. Winkler et al., Nature 441, 853 (2006). Google Quantum AI and collaborators, Nature (October 2025), “Quantum Echoes”. Checked by code: two-particle Hubbard on an 8-ring, double occupancy 0.26, 0.20, 0.25, 0.18 at t = 1, 2, 4, 8 for U = 0; 0.89, 0.90, 0.94, 0.90 for U = 8.

Next · Chapter 127
Sampling advantage: random circuit sampling and boson sampling

In 2019 Google said 10,000 years. Classical methods fought back and won that round. Then the bar moved.

Turn the page