Quantum Simulation & Advantage

Ross’s Law

The central theorem: the exponent of classical simulation is treewidth.


The statement

Ross's 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 tw(G) grows with the input size.

Both directions matter. The upper bound says any circuit can be simulated in time exponential in its treewidth, via optimal tensor-network contraction. The lower bound says you cannot do essentially better — the width is not just an upper bound on cost but its true order.

Why it unifies the volume

Ross's Law is the quantum instance of the universal meter. The same exp(Θ(tw)) law that prices a circuit prices a graphical model, a constraint network, and — the thesis argues — physical and even cognitive substrates exhibiting the shadow–mirror–coupling architecture. One exponent, eight substrates.

Questions

What does exp(Θ(tw(G))) mean exactly?

The cost grows exponentially in the treewidth, and the treewidth is the tight order of that exponent — not merely an upper bound. Θ means matched upper and lower bounds.

Where can I read the full proof?

In the volume itself — the 895-page PDF linked from this page develops Ross's Law and its seven sibling constructions in full.

Read the volume (PDF, 895 pp)More in Quantum Simulation & Advantage