Complexity of Simulation

Feynman's 1982 motivation for the quantum computer was simulation: "Nature isn't classical, and if you want to make a simulation of nature, you'd better make it quantum mechanical." Complexity theory makes this precise. Simulating quantum dynamics is $\mathsf{BQP}$ -complete — exactly as hard as universal quantum computation — while finding ground states is $\mathsf{QMA}$ -hard, and the special structure of stoquastic systems explains when classical methods can succeed. This lesson maps simulation tasks onto the complexity classes we have built.

Two distinct simulation tasks

It is essential to separate two questions that are often conflated:

Dynamics (real-time evolution): given a local Hamiltonian $H$ and a time $t$ , approximate $e^{-iHt}\ket{\psi_0}$ — or, more modestly, expectation values $\bra{\psi(t)} O \ket{\psi(t)}$ .
Statics (ground state / thermal): find or characterize the lowest-energy state of $H$ , or sample from the thermal state $e^{-\beta H}/Z$ .

Their complexities differ. Dynamics is $\mathsf{BQP}$ -complete (efficiently solvable on a quantum computer); ground-state energy estimation is $\mathsf{QMA}$ -hard (likely intractable even for a quantum computer in the worst case, per the local Hamiltonian lesson).

Dynamics is BQP-complete

In $\mathsf{BQP}$ (upper bound). A quantum computer can approximate $e^{-iHt}$ for a $k$ -local $H = \sum_j H_j$ efficiently. Trotter–Suzuki product formulas split the evolution,

e^{-iHt} \approx \left( \prod_j e^{-iH_j t/r} \right)^{r},

with error $O(t^2/r)$ per the first-order formula (higher-order formulas and modern methods — qubitization, LCU, quantum signal processing — achieve near-optimal cost scaling linearly in $t$ and logarithmically in $1/\varepsilon$ ). Each $e^{-iH_j t/r}$ acts on $k$ qubits and compiles to $O(1)$ gates, so total gate count is $\mathrm{poly}(n, t, 1/\varepsilon)$ .

$\mathsf{BQP}$ -hard (lower bound). Conversely, any polynomial quantum circuit can be encoded as the time-evolution of a suitable local Hamiltonian (a continuous-time version of Kitaev's clock construction, or a universal Hamiltonian on a spin chain). So simulating local-Hamiltonian dynamics is at least as hard as $\mathsf{BQP}$ . Together: simulating quantum dynamics is $\mathsf{BQP}$ -complete — it is the natural complete problem capturing what quantum computers do.

When classical simulation succeeds

Worst-case hardness does not mean every system is hard. Several structural conditions make classical simulation efficient:

Limited entanglement (1D, gapped). Ground states of gapped 1D local Hamiltonians obey an area law for entanglement entropy and are well approximated by matrix product states; DMRG simulates them in polynomial time. Tensor networks generalize this to higher dimensions with varying success.
Stabilizer / Clifford dynamics. By the Gottesman–Knill theorem, circuits of only Clifford gates ( $H$ , $S$ , CNOT) on stabilizer inputs are classically simulable in polynomial time despite producing massive entanglement — entanglement alone is not sufficient for quantum advantage.
Stoquastic Hamiltonians (no sign problem). If, in some local basis, all off-diagonal matrix elements of $H$ are real and non-positive, then the Gibbs weights $e^{-\beta H}$ are non-negative and quantum Monte Carlo sampling avoids the sign problem. Such ground-state problems lie in $\mathsf{StoqMA} \subseteq \mathsf{AM}$ , below full $\mathsf{QMA}$ , and are often tractable in practice.

The sign problem as a complexity statement

The infamous sign problem of quantum Monte Carlo — that non-stoquastic Hamiltonians produce negative or complex sampling weights, destroying the Monte Carlo estimator's convergence — is not a defect of a particular algorithm but a reflection of complexity. A general efficient cure for the sign problem would let classical Monte Carlo solve $\mathsf{QMA}$ -hard ground-state problems, implying $\mathsf{QMA} \subseteq \mathsf{AM}$ and collapsing the polynomial hierarchy. So the sign problem is, in a precise sense, as hard as the hardest quantum problems — it cannot be universally solved unless complexity classes collapse.

Takeaways

Simulation cleaves into dynamics ( $\mathsf{BQP}$ -complete, the quantum computer's home turf) and statics ( $\mathsf{QMA}$ -hard, generally intractable). Classical methods win exactly when structure — low entanglement, Clifford form, or stoquasticity — removes the quantum hardness, and the boundaries of those islands are drawn by the same complexity classes. The sign problem is the computational shadow of $\mathsf{QMA}$ -hardness on classical Monte Carlo.