Case Study: Is This Problem Actually Hard Classically?

Executive Summary

Quantum simulation is the most defensible quantum application, and "defensible" is not "automatic." A great many proposed simulation targets are comfortably solved by existing classical methods, and proposing them wastes the credibility that the genuinely hard cases deserve.

This case study builds the triage: given a candidate system, determine whether DMRG, coupled cluster, or quantum Monte Carlo already handles it, and — if not — identify which property defeats them. Getting this right is what separates a serious quantum simulation proposal from a press release.

Skills applied

• Assessing entanglement scaling and area laws (§17.14).
• Recognizing the fermionic sign problem and where it bites (§17.15).
• Evaluating coupled-cluster applicability from correlation strength.
• Selecting the correct classical baseline for a quantum advantage claim.

Phase 1: The three classical champions

DMRG / tensor networks. Essentially exact for 1D systems with area-law entanglement. Cost scales with bond dimension $\chi$, which must grow as $e^{S}$ where $S$ is the entanglement entropy across a cut.

• Wins: 1D chains, ladders, quasi-1D, gapped systems, many 2D systems of modest width.
• Loses: genuinely 2D/3D systems with volume-law entanglement, where $\chi$ becomes exponential.

Coupled cluster (CCSD(T)). The "gold standard" of quantum chemistry. Polynomial cost, $O(N^7)$ for CCSD(T).

• Wins: weakly correlated molecules — most organic chemistry, most of the periodic table's main group, equilibrium geometries. Accuracy routinely ~1 kcal/mol.
• Loses: strong (static) correlation — stretched bonds, bond breaking, transition metals with near-degenerate d orbitals, open-shell systems, excited states. It can fail catastrophically and without warning, which is the dangerous part.

Quantum Monte Carlo. Statistically exact where applicable, polynomial cost.

• Wins: bosonic systems, spin systems on bipartite lattices, sign-problem-free fermionic models.
• Loses: systems with a fermionic sign problem — frustrated magnets, doped Hubbard models, most realistic fermionic systems away from half filling.

Phase 2: The triage flowchart

For a candidate system, ask in order:

1. Is it 1D or quasi-1D with an entanglement area law? → DMRG solves it. No quantum advantage.
2. Is it weakly correlated (single-reference, small $T_1$ diagnostic)? → CCSD(T) solves it. No quantum advantage.
3. Is it sign-problem-free? → QMC solves it. No quantum advantage.
4. Does it fail all three? → Candidate for genuine quantum advantage.

The systems surviving step 4 share a profile: 2D or 3D, strongly correlated, fermionic, and frustrated or doped. That is a narrow class — and it contains several of the most scientifically important open problems in physics and chemistry.

Phase 3: Working examples

The last row is worth dwelling on: protein folding appears on nearly every "quantum applications" slide, and it is dominated by classical force fields and conformational sampling, not by electronic-structure accuracy. It is a sampling problem, not a correlated-electron problem.

Phase 4: The doped 2D Hubbard model

The strongest single case, worth understanding in detail:

$$H = -t\sum_{\langle ij\rangle\sigma}\left(c^\dagger_{i\sigma}c_{j\sigma} + \text{h.c.}\right) + U\sum_i n_{i\uparrow}n_{i\downarrow}$$

Why each classical method fails:

• DMRG: the model is 2D, so entanglement across a cut grows with system width (volume law in the relevant regime); bond dimension becomes exponential.
• CCSD(T): at intermediate $U/t$ the system is strongly correlated and multireference; the single-reference expansion diverges.
• QMC: away from half filling the determinant weights change sign, and the variance grows exponentially with system size and inverse temperature.

And the stakes are real: the doped 2D Hubbard model is widely believed to contain the essential physics of high-temperature superconductivity, unresolved after nearly four decades.

Resource estimate: a $10\times10$ lattice needs ~200 qubits for the fermionic modes plus ancillas, with time evolution costing $10^{6}$–$10^{8}$ gates depending on method and accuracy — error-corrected, but far cheaper than a chemistry-scale QPE calculation. This is among the most plausible early fault-tolerant applications.

Phase 5: How to state a claim honestly

Weak: "We simulated H₂ on a quantum computer." (Solvable by hand; useful only as a hardware demonstration, and should be labelled as such.)

Weak: "Quantum computers will revolutionize drug discovery." (Most of drug discovery is classical MD, docking, and statistics; the electronic-structure fraction is small and often adequately handled.)

Strong: "The doped 2D Hubbard model at $U/t = 8$ resists DMRG (volume-law entanglement in 2D), coupled cluster (multireference character), and QMC (sign problem). A fault-tolerant quantum simulation with ~200 logical qubits could resolve the ground-state phase diagram. We estimate X logical qubits and Y Toffoli gates."

The strong version names the classical methods, states why each fails, and gives a resource estimate. That is the form a defensible claim takes.

Phase 6: The meta-lesson

The best classical algorithms are extremely good, and they improve. DMRG's reach in 2D has expanded considerably; QMC sign-problem mitigations continue to advance; machine-learned wavefunctions are a fast-moving area. A quantum advantage claim is a claim about the classical state of the art, and it therefore requires tracking that state of the art.

This is the same lesson as the Sycamore result from Chapter 1: the classical baseline moved and the claimed margin shrank. Assume yours will too, and build the margin accordingly.

Discussion Questions

1. Why does entanglement scaling determine whether DMRG succeeds? Connect area law to bond dimension.
2. The sign problem is NP-hard in general. Does that mean it can never be circumvented for specific models?
3. Protein folding appears on most quantum applications slides. Construct the strongest argument for including it, then rebut it.
4. Classical methods keep improving. How large a margin should a quantum advantage claim require to be credible over a 15-year horizon?

Your Turn: Extensions

• Compute entanglement entropy across a cut for 1D and 2D Heisenberg models and observe the scaling difference.
• Run CCSD(T) on N₂ at equilibrium and at 3× bond length; observe the breakdown.
• Find a published quantum-chemistry quantum-advantage claim and check its classical baseline against the triage.
• Estimate the bond dimension DMRG would need for a $10\times10$ Hubbard lattice.

Key Takeaways

• Most proposed quantum simulation targets are already solved by DMRG, coupled cluster, or QMC; proposing them is a credibility cost.
• Run the triage: area-law/1D → DMRG; weakly correlated → CCSD(T); sign-problem-free → QMC. Only systems failing all three are candidates.
• The surviving class is 2D/3D, strongly correlated, fermionic, frustrated or doped — narrow, but containing genuinely important open problems.
• The doped 2D Hubbard model is the strongest case: it defeats all three classical methods for identifiable reasons and is within reach of early fault-tolerant machines.
• A quantum advantage claim is a claim about the classical state of the art, which keeps improving. Name the methods, say why each fails, and leave margin.