Classical simulation of quantum circuits
The cost is exponential in one graph invariant, not in the qubit count.
The reframing
A quantum circuit can be written as a tensor network: each gate is a tensor, each wire is an index, and the amplitude you want is the full contraction of the network. Simulating the circuit classically means contracting that network — and the cost of the optimal contraction order is exponential in the treewidth of the network's line graph.
This is the surprise: the difficulty is not set by the number of qubits or even the circuit depth directly, but by how entangled the circuit's interaction graph is, as measured by treewidth. A deep circuit on a low-treewidth architecture stays simulable; a shallow circuit that builds high treewidth does not.
Ross's Law
The thesis states it as a law: the cost of classically simulating a quantum circuit with entanglement graph G scales as exp(Θ(tw(G))). Quantum advantage exists if and only if that treewidth grows with input size. The exponent is the meter; advantage is the regime where the meter runs away.
Questions
Can every quantum circuit be simulated classically?
Yes, in principle — but the cost is exp(Θ(tw(G))). When treewidth stays bounded the simulation is efficient; when it grows with input size the cost becomes intractable, which is exactly where advantage lives.
Does more qubits mean harder to simulate?
Not directly. A million qubits in a low-treewidth arrangement can be easy; a few dozen in a high-treewidth arrangement can be hard. Treewidth, not qubit count, is the exponent.