Quantum advantage, explained
It exists exactly when the entanglement graph's treewidth grows.
A precise dividing line
Quantum advantage is usually defined loosely — quantum hardware doing something classical hardware cannot do efficiently. Treewidth makes it precise: advantage exists if and only if the treewidth of the circuit's entanglement graph grows with the input size. Bounded treewidth means a classical computer keeps up; growing treewidth means it cannot.
This is sharper than the qubit-count framing. It explains why some large-qubit demonstrations were simulated classically after the fact (their effective treewidth was low enough) and why the genuinely hard instances are the ones engineered to drive treewidth up.
Advantage as a regime, not a device
In the thesis's reading, advantage is not a property of a machine but of a computation's structure. The shadow (the classical simulation) tracks the mirror (the quantum process) up to the point where their coupling — the treewidth — diverges. Past that point the shadow cannot follow.
Questions
Is quantum advantage the same as quantum supremacy?
Roughly — 'supremacy' was the original term for a demonstration that classical simulation is infeasible. The treewidth criterion gives both a single, checkable definition.
Why were some 'supremacy' circuits later simulated classically?
Because their effective treewidth, after accounting for circuit structure, was lower than thought. Better contraction orders found smaller widths.