Case Study 2: Is My Circuit Classically Simulable?

"Before asking whether a quantum computer helps, ask whether a laptop already suffices. The question is cheap and the answer is often yes."

Executive Summary

A team prepares a quantum demonstration. Before submitting, someone asks the question that should always be asked first: can a classical computer already do this?

The answer turns out to be yes — twice, for two different reasons — and finding out costs about thirty seconds each time. This case study builds the check, applies it to four circuits, and derives the general test. It ends by being precise about what the check can and cannot establish, because the asymmetry there is the most misused fact in quantum computing.

Skills applied: stabilizer simulation and Gottesman–Knill (§11.4); matrix product states and bond dimension (§11.5); the simulation-method comparison (§11.1).

The Question

Chapter 1 §1.5's five-question test asked "what is the classical baseline?" This is that question, sharpened to something you can execute:

Can any classical simulation method run my circuit in reasonable time?

If yes, the quantum hardware provides no advantage for it — whatever else the run demonstrates.

There are three cheap classical escapes, and a circuit only has to fall into one:

The Check

def classical_escapes(circuit, time_budget_s=10.0):
    """Which classical methods can run this circuit within a time budget?"""
    results = {}
    for method in ("statevector", "stabilizer", "matrix_product_state",
                   "extended_stabilizer"):
        sim = AerSimulator(method=method)
        try:
            t0 = time.perf_counter()
            sim.run(transpile(circuit, sim), shots=64, seed_simulator=1234).result()
            elapsed = time.perf_counter() - t0
            results[method] = elapsed if elapsed < time_budget_s else None
        except Exception:
            results[method] = None
    return results

Thirty seconds of runtime, and it answers the question directly.

Four Circuits

Circuit 1: A 40-qubit GHZ state

"We entangled forty qubits."

  stabilizer:  runs in milliseconds

Classically simulable, trivially. GHZ preparation is H plus CNOTs — pure Clifford — and Gottesman–Knill makes it $O(n^2)$. Chapter 7 §7.3 ran a thousand-qubit version in four seconds.

This does not make the experiment worthless. Preparing a high-fidelity 40-qubit entangled state on real hardware is a genuine engineering achievement and a legitimate benchmark. But it is a hardware characterization, not a computation, and describing it as the latter is the error.

Circuit 2: A shallow variational ansatz, 30 qubits

"Thirty qubits, beyond statevector simulation."

  statevector:          fails (memory)
  matrix_product_state: runs in ~100 ms

Classically simulable, for a completely different reason: a linear-entanglement ansatz at depth 2 keeps entanglement local, so the bond dimension stays small and MPS cost stays $O(n\chi^2)$.

This is a live issue in quantum machine learning. Shallow variational circuits are frequently MPS-simulable, which means a QML result on such a circuit has a classical competitor that is not merely faster but exact. Chapter 33 §33.5 returns to this.

Circuit 3: The same ansatz at depth 20

  statevector:          fails
  matrix_product_state: slow, and slowing rapidly with depth

Not obviously simulable. Depth builds entanglement, the bond dimension grows, and MPS loses its advantage. This is the regime where the question becomes genuinely open.

Circuit 4: A random circuit with many T gates

  stabilizer:           FAILS -- non-Clifford
  extended_stabilizer:  exponential in T count
  matrix_product_state: high entanglement, bond dimension explodes
  statevector:          the only exact option, capped at ~30 qubits

No cheap escape. High entanglement and non-Clifford gates. This is precisely the structure that random-circuit-sampling experiments use, and precisely why they are hard to simulate.

The Test, Generalized

Two properties, and a circuit needs both to be hard:

              |  low entanglement  |  high entanglement
  ------------|--------------------|--------------------
  Clifford    |  easy (stabilizer) |  easy (stabilizer)
  non-Clifford|  easy (MPS)        |  HARD

Entanglement alone is not enough — a 1000-qubit GHZ state is maximally entangled and trivially simulable. Non-Cliffordness alone is not enough — a shallow circuit of arbitrary single-qubit rotations is MPS-simulable at any width.

You need both, which is why:

• T-count is the currency of fault-tolerant resource estimation (Chapter 23) — $T$ gates are what break Clifford simulability, and they are also what is expensive to implement fault-tolerantly.
• Circuit depth matters as much as width for advantage claims — depth is what builds the entanglement that breaks MPS.
• Shallow, structured circuits are suspect as advantage demonstrations, however many qubits they use.

⚠️ Common Pitfall — A circuit that resists MPS is not thereby hard.

The inference runs one way only, and this is the single most misused fact in the area.

"MPS simulated it quickly" is conclusive. Your circuit is classically easy. That is a genuine, publishable finding about the circuit.

"MPS was slow" is not conclusive. It means that method, with that contraction order, at that bond-dimension truncation, struggled. A different tensor-network method, a smarter contraction, or simply more classical compute may succeed.

The historical record is unambiguous here: several prominent quantum-advantage claims have been substantially narrowed or eliminated by improved classical simulation within months of publication. The pattern is so regular that Chapter 1 §1.5 made "has it survived a classical counterattack" one of the five questions.

Proving a problem is easy requires one algorithm. Proving it is hard requires ruling out all of them.

🔬 Honest Assessment — What this check is actually for.

Not for proving quantum advantage. Nothing in this chapter can do that.

It is for avoiding embarrassment, and it is remarkably effective at that. Running classical_escapes() before you submit costs thirty seconds and answers the first question any competent reviewer will ask. Discovering that your 40-qubit demonstration is a Clifford circuit after publication is considerably worse than discovering it before.

It is also a genuine research tool. "This circuit family becomes MPS-hard at depth $d$" is a real and useful result, and it is measurable with the code above.

The honest summary of what you can conclude:

Result	Conclusion
Some classical method runs it fast	No quantum advantage here. Solid.
No method you tried runs it fast	Unknown. You have ruled out some methods, not all.
It is Clifford	No advantage, provably, at any size.
It is shallow and structured	Suspect. Test MPS explicitly.

Lessons

1. Ask "can a laptop do this?" before submitting. Thirty seconds.
2. Three escapes: statevector below ~30 qubits, stabilizer for Clifford at any size, MPS for bounded entanglement.
3. Clifford circuits are simulable at any size — a 1000-qubit GHZ state included. High-fidelity preparation is still an achievement; it is a characterization, not a computation.
4. Shallow variational circuits are frequently MPS-simulable, which matters a great deal for QML claims.
5. Hardness needs both high entanglement and non-Clifford gates. Either alone is escapable.
6. Hence T-count and depth, not qubit count, are the quantities that determine hardness.
7. The inference is one-way. MPS-fast proves easy; MPS-slow proves nothing.
8. Run the check to avoid embarrassment, not to prove advantage. It cannot do the second.

Questions

1. Implement classical_escapes() and run it on the four circuits above. Confirm each falls where the chapter says.

2. Take your project's ansatz at depths 1 through 8 and find the depth at which MPS stops being fast. Is that depth larger or smaller than the depth you were planning to use?

3. Construct a circuit that is Clifford except for exactly one $T$ gate. Which methods handle it? Measure extended_stabilizer's runtime as you add $T$ gates one at a time — is the growth exponential?

4. A 50-qubit circuit of arbitrary single-qubit rotations with no two-qubit gates: is it simulable? By which method, and at what cost? What does the answer say about entanglement as the resource?

5. The pitfall says several advantage claims were narrowed by better classical simulation. Find one, read both the original claim and the classical response, and summarize what changed in three sentences.

6. Design a circuit family with a tunable parameter that moves it from easy to hard. What is the parameter, and can you locate the transition experimentally?

7. Hardest. The check tests four methods. A serious classical-simulation effort would use tensor network contraction with optimized contraction ordering, which can dramatically outperform naive MPS. Estimate what that means for the reliability of a negative result from this check — and propose what you would add to make the check more honest about its own limitations.