Case Study: Why Clifford Circuits Are Not Enough

Executive Summary

A startup demonstrates a 60-qubit circuit producing highly entangled states with results verified against theory, and claims a computation "beyond classical simulation." A reviewer simulates the entire thing on a laptop in under a second.

Nobody cheated. The circuit was Clifford, and the Gottesman–Knill theorem says Clifford circuits — however large, however entangled — are efficiently simulable classically. This case study works through why, what it implies about the popular claim that "entanglement is the source of quantum power," and where the actual boundary lies.

Skills applied

• Identifying the Clifford group and its generators (§6.10).
• Applying the Gottesman–Knill theorem to classify a circuit (§6.11).
• Understanding the stabilizer formalism as a compressed state representation.
• Reasoning about $T$-count as the true measure of quantum hardness.

Background

The Clifford group

The Clifford group is generated by $\{H, S, \text{CNOT}\}$. Its defining property: it maps Pauli operators to Pauli operators under conjugation.

$$HXH = Z, \quad HZH = X, \quad SXS^\dagger = Y, \quad \text{CNOT}(X\otimes I)\text{CNOT} = X\otimes X$$

Every Clifford gate permutes the Pauli group. That is the whole reason the theorem works.

The stabilizer trick

An $n$-qubit stabilizer state is specified not by $2^n$ amplitudes but by $n$ commuting Pauli operators that stabilize it (each has eigenvalue $+1$ on the state). For example, $|\Phi^+\rangle$ is the unique state stabilized by $\{XX, ZZ\}$.

Storage: $n$ stabilizers × $2n$ bits (an $X$ and $Z$ exponent per qubit) + sign = $O(n^2)$ bits. Compare $2^n$ complex amplitudes.

Applying a Clifford gate updates the tableau in $O(n)$ time — you conjugate each stabilizer, which is a Pauli-to-Pauli map, i.e. bit manipulation. Measurement in the computational basis takes $O(n^2)$.

The theorem. A circuit of Clifford gates on a stabilizer input, with computational-basis measurements, is simulable in polynomial time and space.

Phase 1: Classify the startup's circuit

Their circuit used $H$, CNOT, $S$, and Pauli gates, then measured. Every gate is Clifford. Therefore, regardless of the 60 qubits and the genuine entanglement:

import stim                                    # a fast stabilizer simulator

circuit = stim.Circuit()
for q in range(60):
    circuit.append("H", [q])
for q in range(59):
    circuit.append("CNOT", [q, q+1])
circuit.append("M", range(60))

sample = circuit.compile_sampler().sample(shots=1000)   # milliseconds

Sixty qubits, deeply entangled, simulated instantly. The demonstration is real quantum hardware doing real quantum mechanics — and no evidence of computational advantage whatsoever.

Phase 2: The lesson about entanglement

This is the case study's central point, and it contradicts the most common popular explanation of quantum computing.

A 60-qubit GHZ state is maximally entangled across every bipartition. It is also a stabilizer state, and it is classically simulable in microseconds. Therefore:

Entanglement is necessary but nowhere near sufficient for quantum advantage.

If entanglement alone were the resource, Clifford circuits would be hard to simulate. They are not. Something else is doing the work.

What is missing

Stabilizer states form a discrete, finite set — a measure-zero subset of Hilbert space. Clifford circuits move you around inside that set but never out of it. The magic is precisely the ability to leave: to reach states whose amplitudes are not confined to the stabilizer polytope. That requires a non-Clifford gate, conventionally $T$.

Phase 3: The $T$-count boundary

Add $T$ gates and simulation cost grows, but gracefully at first. The best-known classical algorithms simulate a Clifford+$T$ circuit in time roughly

$$O\!\left(2^{\alpha t}\,\text{poly}(n)\right), \qquad \alpha \approx 0.23{-}0.4$$

where $t$ is the $T$-count — the number of non-Clifford gates — and $n$ is the qubit count. Note what is not in that exponent: $n$.

So a 1,000-qubit Clifford circuit is easy and a 20-qubit circuit with 200 $T$ gates is hard. The hardness parameter is $T$-count, not qubit count.

Finding. The startup's press release cited the wrong number. Sixty qubits is a hardware achievement; zero $T$ gates is a computational disqualification.

Phase 4: Consequences you will actually hit

Benchmarking. Random Clifford circuits are useless for demonstrating advantage. This is why quantum-supremacy experiments use random circuits containing non-Clifford gates — the $\sqrt{\text{iSWAP}}$-type entanglers and the $T$-like single-qubit rotations are what make classical simulation expensive.

Error correction. Stabilizer codes (Chapters 24–25) are built entirely from Clifford operations, which is precisely why syndrome extraction can be simulated and designed classically at scale — you can simulate a million-qubit surface code because the code is Clifford. The logical computation on top of it cannot be, which is where magic-state distillation enters.

Resource estimation. Fault-tolerant cost estimates are quoted in $T$-count for exactly this reason. When a paper says "Shor's algorithm on RSA-2048 needs $\sim10^{10}$ $T$ gates," that number is the meaningful one; the qubit count is secondary.

Verification. Because Clifford circuits are simulable, they make excellent test circuits: run them on hardware, compare against exact classical results, and you have an honest benchmark of device fidelity with no advantage claim attached. Randomized benchmarking works precisely this way.

Phase 5: Rewriting the claim

An honest version of the startup's announcement:

"We prepared and verified 60-qubit entangled stabilizer states with measured fidelity X, demonstrating coherent control across the full device. As a Clifford circuit this is efficiently simulable classically by design, which is what allowed us to verify it exactly — the result characterizes our hardware, not a computational advantage."

That is a genuinely good result, stated correctly. Everything interesting about it survives the correction.

Discussion Questions

1. A 60-qubit GHZ state is maximally entangled and classically simulable. Reconcile this with the standard claim that entanglement powers quantum computing.
2. The classical cost of Clifford+$T$ scales as $2^{\alpha t}\text{poly}(n)$. Why is the qubit count only polynomial, and what does that mean for "how many qubits until advantage?"
3. Stabilizer codes are Clifford. Explain why that is simultaneously essential for error correction and the reason magic-state distillation is unavoidable.
4. Design a benchmark circuit that is classically verifiable but still exercises non-Clifford hardware capability. What is the tension?

Your Turn: Extensions

• Install stim and simulate 1,000-qubit Clifford circuits; time it and compare against a state-vector simulator at 25 qubits.
• Add $T$ gates one at a time to a 20-qubit Clifford circuit and measure how simulation time grows.
• Take a Toffoli's Clifford+$T$ decomposition and count $T$s; use it to estimate the $T$-count of a modular exponentiation circuit.
• Read the Gottesman–Knill proof sketch and identify exactly where the Pauli-to-Pauli property is used.

Key Takeaways

• Clifford circuits, however large and however entangled, are classically simulable in polynomial time (Gottesman–Knill).
• Entanglement is necessary but not sufficient for quantum advantage — the popular explanation is incomplete in a way that matters.
• Stabilizer states are stored in $O(n^2)$ bits rather than $2^n$ amplitudes, and Clifford gates update that representation in $O(n)$.
• $T$-count, not qubit count, is the parameter that governs classical simulation hardness.
• The same fact makes Clifford circuits ideal verification tools and makes magic-state distillation the central cost of fault tolerance.