Quantum Simulation & Advantage

classical simulation of quantum circuits

A quantum circuit is a tensor network; simulating it classically is contracting that network; and the cost of the cheapest contraction is exponential in the treewidth of the entanglement graph. That one chain is Ross's Law. These pages walk it from tensor contraction up to where quantum advantage must live.

• Classical simulation of quantum circuitsHow hard is it to simulate a quantum circuit on a classical computer? The answer is set by treewidth — the heart of Ross's Law.
• Tensor network contraction complexityThe cost of contracting a tensor network is exponential in the treewidth of its structure. Why contraction order is everything.
• Quantum advantage explainedQuantum advantage is the regime where classical simulation cost runs away — and that regime is defined by growing treewidth.
• Ross's law treewidth quantumThe central theorem of Shadow & Mirror — classical simulation cost is exp(Θ(tw(G))), and quantum advantage exists iff treewidth grows.
• Entanglement entropy area law treewidthArea-law entanglement is low effective treewidth. Why area laws make quantum states classically simulable.
• Matrix product states bond dimensionMPS are tensor networks with path structure; bond dimension is the exponential of entanglement. The 1D case of the treewidth meter.