Tensor-Network Contraction and Quantum Advantage Benchmarks

A quantum circuit looks impossible to a classical computer: $n$ qubits span a Hilbert space of dimension $2^n$ , and $53$ qubits already demand $2^{53}$ complex amplitudes — more numbers than a supercomputer can hold. Yet that count is a red herring. A circuit is, read literally, a tensor network: each $k$ -qubit gate is a rank- $2k$ tensor, each wire an index, and the amplitude of an output bitstring is the sum over all the internal indices — the contraction of the network. The cost is fixed not by $2^n$ but by the order in which indices are eliminated, because every partial sum builds an intermediate whose size is exponential only in the bonds it straddles. The largest such intermediate, minimized over all orders, has a name from graph theory: the treewidth of the circuit's line graph. This one reframing turned the debate over quantum computational advantage into a quantitative contest with a shared scoreboard. When Google's Sycamore ran a random circuit sampling task in 2019 and estimated $10{,}000$ years of classical effort, the counter-attack was not a bigger supercomputer but a better contraction order plus slicing — cutting a handful of bonds to trade an unaffordable memory footprint for embarrassingly parallel time, dropping the estimate to days then hours. The referee is cross-entropy benchmarking, whose fidelity $F_{\mathrm{XEB}}$ is itself computed by contracting tensor networks — benchmark and attack run the same engine, which is why contraction complexity is the currency of the field.

Key takeaways

A quantum circuit's amplitudes are exactly the contraction of a tensor network whose tensors are the gates; the classical cost is governed not by the qubit count $n$ but by the treewidth of the interaction graph, which sets the largest intermediate tensor.
Finding a good contraction order is NP-hard; simulators approximate it with hypergraph partitioning, tree decompositions, and simulated-annealing path search, reaching time $2^{O(\mathrm{tw})}$ .
Slicing fixes $k$ bonds to constants, splitting one contraction into $2^k$ independent subproblems — cutting peak memory by up to $2^k$ and giving perfect parallelism at a price of at most $2^k$ in work.
For a $\sqrt n\times\sqrt n$ grid of depth $d$ the treewidth is $\Theta(\min(d,\sqrt n)\,\sqrt n)$ , so shallow 2D supremacy circuits are exponentially hard but with a slow $\sqrt n$ exponent — the loophole classical simulators exploit.
Linear cross-entropy benchmarking, $F_{\mathrm{XEB}} = 2^n\langle p_U(x)\rangle - 1$ , scores how strongly samples concentrate on high-probability Porter–Thomas bitstrings: ideal gives $1$ , uniform noise $0$ , and a real device sits at its global fidelity ( $\approx 0.2\%$ for Sycamore).
Key idea: the classical hardness of simulating a quantum circuit is set by the treewidth of its interaction graph, not its qubit count — contraction time scales as $2^{O(\mathrm{tw})}$ , and slicing converts memory into parallel time, so the quantum-versus-classical frontier is fixed by how large a treewidth current hardware can generate against current contraction algorithms.

The core insight

The classical hardness of simulating a quantum circuit is controlled by the treewidth of its interaction graph, not by its qubit count: contraction time scales as $2^{\,O(\mathrm{tw})}$ , and slicing converts an unaffordable memory footprint into parallel time, so the quantum-versus-classical frontier is fixed by how large a treewidth current hardware can generate against current contraction algorithms.

Where this lives today

Both attack and defense are live research. On the classical side, hyper-optimized contraction is a mature software stack: cotengra and quimb search vast spaces of paths with hypergraph partitioning (KaHyPar) and annealing, and Pan and Zhang's 2022 result reproduced the full Sycamore sampling distribution in roughly $15$ hours on $512$ GPUs — a task Google had estimated at millennia — with later work pushing XEB spoofing to seconds. On the quantum side, hardware answered by inflating treewidth: China's Zuchongzhi processors (2021) reached $56$ – $60$ qubits, and Google's 2024 "beyond-classical" sampling used $67$ – $70$ qubits at greater depth, pushing the treewidth into a regime where the best known contractions would take astronomically long. The open frontier is verification itself: computing $F_{\mathrm{XEB}}$ for the newest experiments requires the same expensive contractions they are meant to outrun, so the field now asks whether XEB can even be validated where it certifies advantage. Contraction complexity — how large a treewidth hardware can make against how clever the contraction gets — remains the single number the contest is scored on.

The physical picture

Draw the circuit as a graph in space and time: qubit wires run left to right, gates sit where two wires meet, and the whole diagram is a tensor network waiting to be summed. Contracting it collapses the graph one bond at a time, and each merge inflates a tensor whose storage cost is its surface area — the legs it still dangles into the rest of the network. A clever order keeps every intermediate small; a careless order inflates one monstrous $2^n$ balloon and you are back to full state-vector simulation. The first figure shows the correspondence and the quantity that decides the cost: the open bonds a contraction front cuts.

Figure

A depth-3 circuit on 5 qubits redrawn as a tensor network: every gate becomes a tensor and every wire an index, so the amplitude of an output bitstring is the sum over all internal indices — the amber contraction front here cuts w = 5 open bonds, so its intermediate tensor holds 2⁵ = 32 complex numbers, while a real Sycamore front reaches w ≈ 53

Slicing is the second idea, the one that actually fit supremacy-scale contractions onto real hardware. It works like a hard integral you cannot store: freeze a few variables to fixed values, solve the many easy sub-integrals, and add the answers. Pinning $k$ bonds replaces one impossible sum with $2^k$ smaller, independent contractions — at most a factor $2^k$ in work but up to $2^k$ less peak memory, and because the slices never talk, a thousand GPUs each chew their own slice. Geometry decides how much you need: a 1D chain has treewidth $\sim 1$ (MPS territory, polynomial cost), a shallow 2D grid $\sim\sqrt n\,d$ , and a deep all-to-all circuit $\sim n$ (as hard as brute force). Advantage designers push depth and connectivity to inflate the treewidth while staying inside the coherence budget. The second figure is the scoreboard those choices are measured on.

Figure

Classical cost of reproducing the Sycamore sampling task collapsed as contraction algorithms improved: from Google's ≈ 3×10¹¹ s (about 10,000 years) 2019 estimate, down to ≈ 20 days (Huang 2020), down to ≈ 15 hours on 512 GPUs (Pan–Zhang 2022) — while the device itself sampled in 200 s at XEB fidelity ≈ 0.2 percent

The core equations

The starting point is an identity, not an approximation: the amplitude is literally a tensor contraction. Insert a resolution of the identity on every wire between layers, and the unitary factorizes into gate tensors tied by summed indices:

\langle x | U | 0^n\rangle = \sum_{\{i\}} \prod_{g} \big(T_g\big)_{i_a\,i_b\,\cdots} \qquad (1)

where: $U$ — the full unitary, factored into gates $g$ ; $T_g$ — the tensor for gate $g$ (a $2\times2\times2\times2$ array for a two-qubit gate); $i_a,i_b,\dots$ — wire indices (bonds), summed over $\{0,1\}$ ; $x$ — the output bitstring fixing the open legs. Reading: the edges are the summed indices; the amplitude is what remains once every edge is eliminated. The cost depends entirely on the order. Each pairwise contraction is a matrix multiply whose flop count is the product of the bond dimensions it touches; memory is set by the widest intermediate:

\text{time} = O\!\Big(\sum_{v\in\text{order}} \textstyle\prod_{e\in\partial v} \dim(e)\Big),\qquad \text{memory} = O\!\big(2^{\,w}\big) \qquad (2)

where: $\partial v$ — the open bonds on the intermediate built at step $v$ ; $\dim(e)$ — the dimension of bond $e$ ( $=2$ for qubits); $w$ — the maximum open-bond count over the order, the contraction width. Reading: memory grows as $2^w$ , so the whole game is to keep $w$ small. The width is not free: minimized over all orders it equals a fixed graph invariant — the Markov–Shi theorem:

w_{\min} = \mathrm{tw}\big(L(G)\big) + 1,\qquad \text{time}_{\min} = 2^{\,\mathrm{tw}(L(G))+O(1)}\,|G| \qquad (3)

where: $w_{\min}$ — the optimal contraction width; $L(G)$ — the line graph of the network $G$ ; $\mathrm{tw}$ — treewidth, the width of the best tree decomposition. Reading: simulation is fixed-parameter tractable in treewidth — cheap when $\mathrm{tw}$ is small, hopeless when $\mathrm{tw}\sim n$ , and $n$ alone does not tell you which. Even with an optimal order, peak memory may exceed any machine. Slicing rescues it by pinning a chosen set of bonds to constants and summing afterward — an exponential memory cut for an at-most-exponential time cost, with perfect parallelism.

C_{\text{sliced}} = \chi \cdot C_{\text{sub}},\qquad M_{\text{sliced}} = M_{\text{full}}/\chi,\qquad \chi = 2^{k} \qquad (4)

where: $\chi$ — the number of slices (product of sliced bond dimensions); $k$ — the sliced bond count; $C_{\text{sub}}$ — the cost of one slice; $M_{\text{full}}$ — the unsliced memory. Reading: memory falls by $\chi$ with certainty, work rises by at most $\chi$ (usually far less, since slicing also lowers the width), and the slices run with zero communication. To score the contest you need a figure of merit. Linear cross-entropy benchmarking measures how strongly a sample set concentrates on the ideal distribution's high-probability bitstrings:

F_{\mathrm{XEB}} = 2^{n}\,\big\langle p_U(x)\big\rangle_{x\sim\text{exp}} - 1,\qquad p_U(x)=\big|\langle x|U|0\rangle\big|^2 \qquad (5)

where: $p_U(x)$ — the ideal probability of bitstring $x$ (itself a contraction); $\langle\cdot\rangle$ — the average over sampled strings; $n$ — the qubit count. Reading: $F_{\mathrm{XEB}}=1$ ideal, $0$ uniform noise, and the device's global fidelity in between. That fidelity is not free either — it is the product of the survival probability of every gate, startlingly small for a supremacy circuit:

F_{\mathrm{XEB}} \approx \prod_{g}(1-e_g) \approx e^{-\sum_g e_g} \qquad (6)

where: $e_g$ — the error rate of gate $g$ ; the product runs over all gates plus readout. Reading: hundreds of gates at sub-percent error leave fidelity near $0.2\%$ — the target a spoofer must match. Finally, the geometry tying it together — the treewidth of the experiments' grids:

\mathrm{tw}\big(\sqrt n \times \sqrt n \text{ grid, depth } d\big) = \Theta\big(\min(d,\sqrt n)\,\sqrt n\big) \qquad (7)

where: $\sqrt n$ — the linear grid dimension; $d$ — the number of two-qubit layers. Reading: for shallow depth the treewidth grows like $\sqrt n\,d$ , so cost is $2^{\Theta(\sqrt n\,d)}$ — exponential, but with an exponent growing only as $\sqrt n$ , which is why 53 qubits was contestable.

Derivation AWhy optimal contraction cost is exponential in treewidth

The goal is the central complexity statement of the subject: with the best contraction order, the time to simulate a circuit is $2^{O(\mathrm{tw})}$ times a polynomial, where $\mathrm{tw}$ is the treewidth of the line graph — so classical cost is a property not of the qubit count but of a graph invariant. We build the bridge both ways: a tree decomposition of width $w$ yields an order of the same width, and any order yields a decomposition, so the minimum over orders is exactly the treewidth, and the per-step cost then gives the exponential.

Step 1. Take a tree decomposition $(\mathcal{T},\{B_t\})$ of $L(G)$ : each node $t$ carries a bag $B_t$ of edges of $G$ , the bags cover every edge, and for each edge the bags containing it form a connected subtree; the width is $w=\max_t|B_t|-1$ . Why: the bag tracks which indices are simultaneously alive, and connectivity forbids an index from being resurrected after it is summed.

Step 2. Turn the tree into an order: process leaves to root, contracting at each node every index confined to its subtree. The indices still open lie in the bag, so the intermediate has at most $w+1$ legs. Why: the bag literally bounds the open-bond count, so bag size and contraction width are the same quantity.

Step 3. Bound the per-step cost: each contraction touches at most $w+1$ dimension-2 bonds, costing at most $2^{\,w+1}$ multiply-adds. Why: this is where the exponential enters — the width sits in the exponent, while $n$ appears only through the polynomial step count.

Step 4. Sum over the $O(|G|)$ nodes: $\sum_t \text{cost}_t \le |\mathcal{T}|\,2^{\,w+1} = 2^{\,w+O(1)}|G|$ , and minimizing over decompositions replaces $w$ by $\mathrm{tw}(L(G))$ . Why: the prefactor $|G|$ is harmless; the treewidth in the exponent is the whole story.

Step 5. Prove optimality: any order induces a tree decomposition of equal width, so no order beats the treewidth — the bound is tight up to the additive constant. Why: the converse turns an upper bound into the exact classical cost, making it a fair scoreboard. *Why this works end-to-end: contraction is fixed-parameter tractable in treewidth with time $2^{\mathrm{tw}(L(G))+O(1)}|G|$ , and the bag size equals the maximum open-bond count at every step — so the two quantities are the same thing measured from opposite sides.*

Go deeper · Derivation B · 2 minSlicing converts memory into parallel time

Derivation BSlicing converts memory into parallel time

The aim is to show that cutting $k$ bonds shrinks peak memory by $2^k$ while inflating total work by at most $2^k$ , with zero communication between subproblems — the maneuver that broke terabyte-scale intermediates into GPU-sized pieces and made supremacy-scale contractions runnable on existing clusters. We split the grand sum over all internal indices into an outer sum over a chosen set of bonds and an inner contraction that no longer contains them.

Step 1. Choose $k$ slice bonds and pin each to a definite value rather than summing it: $\langle x|U|0\rangle = \sum_{s\in\{0,1\}^k} \mathcal{C}(G\,|\,\text{sliced bonds}=s)$ . Why: the outer sum is a plain sum of numbers, so the pieces couple only through the final addition of their scalar results.

Step 2. For each $s$ , form $G_s$ by deleting the sliced edges (their values absorbed into adjacent tensors); the $2^k$ subnetworks are identical and independent. Why: this buys perfect parallelism — a thousand workers each take a batch of $s$ values and never exchange a byte until the end.

Step 3. Track memory: the sliced bonds no longer appear in any intermediate of $G_s$ , so the width drops from $w$ to $w'$ and per-slice memory is $2^{w'} \le M_{\text{full}}/2^{\,\Delta}$ . Why: choosing which bonds to slice is the art — a good choice removes the bonds forcing the widest intermediate, so the memory cut $\Delta$ is large.

Step 4. Track time: $\text{time} = 2^{k}\cdot\text{time}(G_s)$ worst case, but the lowered width shrinks each slice so the real overhead is modest. Why: because slicing also reduces $w'$ , the product $2^k\cdot 2^{w'}$ is often barely above $2^w$ — you pay little and gain parallelism.

Step 5. The payoff at Sycamore scale: slicing a few dozen bonds took intermediates from terabytes to gigabytes and turned one monster contraction into millions of independent jobs. Why: this is why the estimate fell from years to hours with no new hardware — the same flops, re-organized to fit and parallelize. *Why the accounting closes: deleting sliced bonds lowers the maximal bag size, and the slice count is exactly $2^{(\#\text{sliced bonds})}$ — so both the memory reduction and the parallelism factor are precisely $2^k$ .*

Go deeper · Derivation C · 1 minCross-entropy fidelity of ideal versus uniform sampling

Derivation CCross-entropy fidelity of ideal versus uniform sampling

The objective is to derive the two anchors that make linear XEB meaningful — $F_{\mathrm{XEB}}=1$ for ideal Porter–Thomas sampling and $0$ for uniform noise — from the statistics of Haar-random amplitudes, and to see why a noisy device interpolates linearly at its global fidelity. Deep random circuits scramble the input so thoroughly that each output probability behaves like the squared modulus of a random complex Gaussian, making the probabilities exponentially distributed and collapsing every average to a ratio of moments.

Step 1. For a Haar-random $U$ each probability $p_U(x)$ is exponentially distributed with mean $1/N$ , $N=2^n$ : the density is $P(p)=N e^{-Np}$ (Porter–Thomas). Why: the exponential tail means a few bitstrings are much likelier than average — the signal XEB detects.

Step 2. The moments are $\langle p\rangle = 1/N$ and $\langle p^2\rangle = 2/N^2$ . Why: the second moment is twice the square of the first, and that factor $2$ is the entire origin of the ideal $F_{\mathrm{XEB}}=1$ .

Step 3. Ideal sampling weights each string by an extra $p_U$ : $\langle 2^n p_U\rangle_{x\sim p_U} = N\,\langle p^2\rangle/\langle p\rangle = N\cdot(2/N^2)/(1/N) = 2$ , giving $F_{\mathrm{XEB}} = 1$ . Why: importance sampling by $p$ turns the average into a ratio of consecutive moments, which Porter–Thomas fixes at $2/N$ .

Step 4. Uniform sampling gives the plain mean $\langle 2^n p_U\rangle_{x\sim\text{unif}} = N\langle p\rangle = 1$ , so $F_{\mathrm{XEB}} = 0$ ; a depolarizing channel of fidelity $F$ mixes $F$ -ideal with $(1-F)$ -uniform, so $F_{\mathrm{XEB}}\approx F$ . Why: this linearity lets $F_{\mathrm{XEB}}$ read out the device fidelity, and it is exactly what a spoofer must match — a small number, not the full distribution. *Why the anchors are exact: the moment ratio $\langle p^2\rangle/\langle p\rangle = 2/N$ follows directly from the exponential (Porter–Thomas) density, and it is precisely this ratio that fixes $F_{\mathrm{XEB}}=1$ for ideal sampling and $F_{\mathrm{XEB}}=0$ for uniform noise.*

Limiting cases

Contraction cost sweeps from polynomial to intractable as the geometry changes, each regime set by the treewidth it produces:

Case	Result	Meaning
1D shallow (MPS regime)	$\text{cost} \sim n\,\chi^3,\ \chi = 2^{S}$	bond dimension $\chi$ bounded by entanglement $S$ ; area-law states have $\chi=O(1)$ , polynomial cost — DMRG territory
2D grid, depth $d$	$\text{cost} \sim 2^{\,\Theta(\min(d,\sqrt n)\sqrt n)}$	treewidth set by the smaller of depth and lateral cut; supremacy circuits — exponential but slow $\sqrt n$ exponent
Deep all-to-all	$\text{cost} \sim 2^{\,\Theta(n)}$	treewidth $\approx n$ ; no better than full state-vector — the genuine worst case
Amplitude vs. sampling	$C_{\text{sample}} \sim F_{\mathrm{XEB}}\,C_{\text{amp}}$	spoofing at fidelity $F_{\mathrm{XEB}}\ll 1$ is far cheaper than one exact amplitude

Common trapMore qubits does not mean more classical cost

The seductive error is to read " $n$ qubits" as " $2^n$ operations." That holds only for the worst-case deep, all-to-all circuit whose treewidth saturates at $n$ . Shallow or geometrically local circuits have treewidth far below $n$ — a 2D grid of depth $d$ has $\mathrm{tw}\sim\sqrt n\,d$ — so they are exponentially cheaper than the naive count, and that gap is what tensor-network simulators exploit. A subtler trap is to conflate a single amplitude with the sampling task: the benchmark asks not for one exact number but for many low-fidelity samples whose Porter–Thomas statistics match a device already at $F_{\mathrm{XEB}}\approx 0.2\%$ . Frugal and spoofing methods win by matching that tiny fidelity cheaply — so "how hard is one amplitude" is the wrong question for "is the experiment classically reproducible."

Worked examples

1 · Memory of a supremacy-scale contraction, and how much to slice

A random circuit runs on the Sycamore geometry: $n=53$ qubits on a $\sim\!7\times 8$ grid, depth $d=20$ . Estimate the peak memory of an optimal single-amplitude contraction, then find how many bonds to slice so each subproblem fits a 16 GB GPU.

Step 1. Estimate the treewidth. With $\sqrt n\approx 7.3$ and depth $d=20 > \sqrt n$ , equation (7) gives $\mathrm{tw}\sim\min(d,\sqrt n)\cdot\sqrt n = 7.3\times 7.3 \approx 53$ . Geometry sets the optimal width to $w\approx 53$ — the largest intermediate carries about 53 open bonds.

Step 2. Convert width to memory. A tensor of $w$ open bonds holds $2^{w}$ complex numbers; at $16$ bytes each, peak memory is $M_{\text{full}} = 2^{53}\times 16\ \text{B} \approx 1.4\times 10^{17}\ \text{B} \approx 130\ \text{PB}$ . Unsliced, the contraction needs $\sim 10^{17}$ bytes — beyond any single machine.

Step 3. Slice to fit. A 16 GB GPU holds $16\times 10^{9}/16 \approx 2^{30}$ complex numbers, so each slice may carry width $w' = 30$ . That needs $k = 53 - 30 = 23$ sliced bonds, giving $\chi = 2^{23}\approx 8.4\times 10^{6}$ slices. Slicing ~23 bonds turns one 130 PB contraction into $\sim 8\times 10^6$ GPU-sized jobs — the essence of how the estimate fell to cluster-hours.

Step 4. Sanity-check the time. Work rises by at most $2^{23}$ , but because those 23 bonds were forcing the widest intermediate, each slice's inner width falls below the naive $w'$ , so realistic runs pay far less than the worst case — landing near tens of hours, not centuries. The $2^{23}$ factor is a loose bound; width-lowering slices recover most of it, and every slice runs in parallel.

2 · The XEB fidelity of Sycamore from its error budget

Sycamore ran $\approx 430$ two-qubit gates at $e_2\approx 0.6\%$ , $\approx 1100$ single-qubit gates at $e_1\approx 0.15\%$ , and $53$ readouts at $e_r\approx 3.8\%$ . Estimate the global $F_{\mathrm{XEB}}$ using equation (6).

Step 1. Two-qubit contribution: $\sum e_2 = 430\times 0.006 = 2.58$ , so surviving weight is $e^{-2.58} = 0.076$ . The two-qubit gates alone drop fidelity to about $7.6\%$ .

Step 2. Single-qubit contribution: $\sum e_1 = 1100\times 0.0015 = 1.65$ , giving $e^{-1.65} = 0.19$ .

Step 3. Readout contribution: $\sum e_r = 53\times 0.038 = 2.01$ , giving $e^{-2.01} = 0.134$ . Readout costs a factor $\approx 0.13$ — comparable to the gates, which is why measurement fidelity matters.

Step 4. Multiply the independent survival factors: $F_{\mathrm{XEB}} \approx 0.076\times 0.19\times 0.134 = 1.9\times 10^{-3} \approx 0.2\%$ , matching the reported value. The device is right about two times in a thousand — and a classical sampler only has to match that $0.2\%$ , not the full ideal distribution, which is the entire leverage behind frugal spoofing.

Physics of the portrait

Tensor-network contraction is where quantum information theory, graph theory, and high-performance computing meet in a single number. It has no lone inventor — a synthesis assembled over half a century, from Penrose's picture-language, through a theorem tying it to treewidth, to the GPU clusters that made it the referee of quantum advantage.

Origins · 1 mintensor-network contraction and how this was discovered

tensor-network contraction

the graph-theoretic bridge from quantum circuits to treewidth · classical simulation and quantum advantage

The idea that a network of tensors can be summed by collapsing it edge by edge goes back to Roger Penrose, who in 1971 introduced a diagrammatic notation in which tensors are blobs, indices are legs, and contraction is the joining of legs — making the shape of a computation visible. For decades this lived in mathematical physics and, through matrix product states and DMRG, in 1D condensed-matter simulation. The decisive turn came in 2008, when Igor Markov and Yaoyun Shi proved that contraction cost is controlled by the treewidth of the line graph — making circuit simulation fixed-parameter tractable in a graph invariant rather than exponential in the qubit count. That theorem sat quietly until 2019, when Sycamore made it urgent: was $10{,}000$ years real, or an artifact of a bad algorithm? Johnnie Gray and Stefanos Kourtis built hyper-optimized path finders (cotengra, quimb), and Feng Pan and Pan Zhang, with slicing and secondary-storage staging, drove the estimate to hours on GPU clusters. What Penrose drew as a picture became the arbiter of the most-watched claim in modern computing.

History

1971

— Penrose introduces diagrammatic tensor notation, making contraction a visual operation

2008

— Markov and Shi prove contraction cost is governed by the treewidth of the line graph

2012

— Preskill coins the term quantum supremacy for a decisive quantum-versus-classical task

2019

— Google's Sycamore reports a random circuit sampling task at an estimated 10,000-year classical cost

2022

— Pan, Chen and Zhang reproduce the Sycamore sampling task in hours on GPU clusters

Going further

References. Markov & Shi, "Simulating quantum computation by contracting tensor networks," SIAM J. Comput. 38, 963 (2008) · Arute et al. (Google), "Quantum supremacy using a programmable superconducting processor," Nature 574, 505 (2019) · Boixo et al., "Characterizing quantum supremacy in near-term devices," Nature Physics 14, 595 (2018) · Gray & Kourtis, "Hyper-optimized tensor network contraction," Quantum 5, 410 (2021) · Huang et al., "Classical simulation of quantum supremacy circuits," arXiv:2005.06787 (2020) · Pan, Chen & Zhang, "Solving the sampling problem of the Sycamore quantum circuits," Phys. Rev. Lett. 129, 090502 (2022) · Preskill, "Quantum computing in the NISQ era and beyond," Quantum 2, 79 (2018). Standard textbook grounding: Nielsen & Chuang, Quantum Computation and Quantum Information; Preskill, Lecture Notes on Quantum Computation; Watrous, The Theory of Quantum Information; Kitaev, Shen & Vyalyi, Classical and Quantum Computation. Key numerical anchors used throughout: the amplitude-as-contraction identity (obtained by inserting basis resolutions); the width = treewidth statement and $2^{O(\mathrm{tw})}$ scaling; the slicing trade-off and slice count $2^{k}$ ; the Porter–Thomas moments $\langle p\rangle=1/N$ , $\langle p^2\rangle=2/N^2$ and the anchors $F_{\mathrm{XEB}}=1,0$ ; the Sycamore parameters ( $n=53$ , depth $20$ , $\sim\!430$ two-qubit gates, $F_{\mathrm{XEB}}\approx 0.2\%$ ) and revised classical runtimes. Grid treewidth follows standard planar-separator theory.

Prerequisites. Quantum circuit model and universal gate sets · Entanglement entropy and Schmidt decomposition · Computational complexity (P, NP, #P) · Graph theory: treewidth and tree decompositions. Leads to. Random circuit sampling and supremacy protocols · Matrix Product States and DMRG · Quantum Approximate Optimization Algorithm · Quantum Machine Learning Models.

Ask the tutor: Ask me to walk a small circuit through an explicit contraction order and count the open bonds at each step, or to work out how many bonds you would have to slice to fit a given circuit on your hardware.

Isn't simulating n qubits always exponential in n?

Only in the worst case. The cost is $2^{O(\mathrm{tw})}$ where $\mathrm{tw}$ is the treewidth of the interaction graph, and treewidth equals $n$ only for deep, all-to-all circuits. Shallow or local circuits have much smaller treewidth — a 2D grid of depth $d$ gives $\mathrm{tw}\sim\sqrt n\,d$ — so their largest intermediate is far below $2^n$ and they contract without ever forming the full state vector. The exponent is the treewidth, not the qubit count; the two coincide only in the hardest geometry.

What exactly is a "contraction order" and why does it matter so much?

A contraction order is the sequence in which you sum out the network's internal indices — equivalently the order in which you multiply pairs of tensors. It matters because every intermediate costs $2^{w}$ memory in the number $w$ of bonds it still touches, and different orders produce wildly different peak widths: the same network can cost $2^{20}$ or $2^{53}$ depending only on the order. Finding the best order is NP-hard, so simulators use hypergraph partitioning, greedy and Boltzmann-greedy heuristics, and simulated-annealing refinement to approach the treewidth-optimal width.

How does slicing avoid an exponential blow-up in time?

Slicing pins $k$ bonds to fixed values, creating $2^k$ independent subproblems summed at the end. Worst case this multiplies work by $2^k$ — but the bonds are chosen precisely because removing them lowers the contraction width. Since per-slice memory and time both fall as the width drops, the product of " $2^k$ more slices" and "each slice much cheaper" is often barely above the original cost. You gain a guaranteed $2^k$ memory cut and perfect parallelism for only a modest time overhead — that asymmetry is the whole trick.

Why is cross-entropy benchmarking the figure of merit rather than exact simulation?

Because reproducing a supremacy experiment means producing samples whose statistics match the device — not recomputing every amplitude — and the device is very noisy, at $F_{\mathrm{XEB}}\approx 0.2\%$ . Linear XEB measures how strongly a sample set concentrates on high-probability Porter–Thomas bitstrings: $1$ ideal, $0$ uniform noise, and the global fidelity in between. It degrades linearly with noise and can be estimated from a feasible number of samples — but computing it still requires contractions, the field's central tension.

Did classical simulation "disprove" quantum supremacy?

No — it re-grounded it. The original $10{,}000$ -year figure assumed Schrödinger–Feynman state-vector methods; tensor-network contraction with optimized ordering and slicing showed the real cost was days, then hours. That did not erase a quantum advantage, it quantified one and moved the line, forcing the next experiments to use more qubits and depth to push the treewidth back out of classical reach. The pattern is a ratchet: each hardware advance raises the treewidth, each algorithmic advance lowers the cost of a given treewidth, and the frontier is wherever the two currently cross.

Where do matrix product states fit into this picture?

Matrix product states (MPS) are the special case with 1D chain topology, where treewidth is essentially constant and the one relevant parameter is the bond dimension $\chi=2^{S}$ set by the entanglement entropy $S$ across a cut. For area-law states $\chi$ stays bounded and contraction is polynomial — the regime DMRG exploits. Supremacy circuits deliberately leave it by using 2D connectivity and enough depth to drive entanglement up, so no low-treewidth MPS description survives.