One way to simulate a quantum circuit on a classical computer without storing all $2^n$ amplitudes is to rewrite the circuit as a tensor network: a graph of small multi-index arrays that are multiplied together pairwise until one number, such as an output amplitude, is left. The order of those multiplications decides whether the job fits in memory. It is known that the best achievable peak cost equals the treewidth of the network's line graph, and that finding an order is the same problem as choosing an elimination order in sparse Gaussian elimination (Benchmarking treewidth as a practical component of tensor-network-based quantum simulation). Treewidth measures how tree-like a graph is. Eliminating a vertex joins all of its remaining neighbours into a clique, and the new "fill-in" edges this creates correspond to large intermediate tensors. Current ordering tools optimize over the whole graph at once. This proposal argues that the hard part of the problem sits in one identifiable place: the densest k-core of the line graph, meaning the largest subgraph in which every vertex keeps at least k neighbours. That core can be found in linear time by repeatedly peeling a minimum-degree vertex, the same peeling that subgraph-mining algorithms use to orient edges.
The practical claim is that this peeling pays off in three ways. First, the largest k-core is a certified lower bound on achievable contraction width. Second, it marks a boundary: outside it, cheap greedy elimination is enough, and all expensive search effort should go inside it. Third, how dense the core is predicts when tensor contraction stops being competitive. That prediction covers the solver switch reported by Dumitrescu et al. and the crossover to decision-diagram simulation reported by FeynmanDD. If the claim holds, practitioners get contraction orders as good as the best whole-graph optimizers at a fraction of the search time, plus a cheap way to tell in advance which simulation method to use.
Core Claim
The research file frames the tempting idea as using the degeneracy peeling order directly as the elimination order, on the grounds that it bounds every vertex's out-degree by the degeneracy $d$. This does not work, and the proposal is built around why. Out-degree $d$ bounds the clique created when a vertex is eliminated only in the original graph. Fill edges then raise the degrees of later vertices. A 2D grid has degeneracy 2 yet treewidth of order $\sqrt{n}$. Worse, peeling is just minimum-degree elimination with the fill updates removed. Classical minimum-degree ordering, and the greedy prefix that tools like Cotengra and RL-TNCO already use, dominate it by construction.
The correct relation runs the other way. Every subgraph of a graph with treewidth $t$ contains a vertex of degree at most $t$. Peeling finds exactly the subgraph whose minimum degree is largest, so
$$ d(L) \;\le\; \mathrm{tw}(L) \;=\; \text{optimal contraction width}, $$
where $L$ is the line graph of the tensor network and $d(L)$ is its degeneracy. The peeling therefore gives a lower bound computable in linear time, and a certificate whenever a heuristic order reaches it. It also locates the obstruction: the maximum core $C$, the set of vertices whose core number equals $d(L)$.
The hypothesis to test is that, on circuit networks, optimizing only inside $C$ loses little. Vertices outside $C$ would be eliminated by dynamic minimum-fill greedy, and the full search budget (dynamic programming over a linear order, a PACE-style exact solver, or recursive cuts) would be spent on $C$ plus the fill that the periphery pushes into it. The companion hypothesis is that the density of $C$ separates the regimes where different solvers win better than raw size or edge count does. That density is measured as $|E(C)|$ divided by the number of vertex pairs in $C$, together with the ratio between achieved width and $d(L)$.
Research Program
The first component is measurement. For each benchmark family we compute the k-core structure of the line graph as circuit depth and gate density grow. QAOA serves as the testbed, with depth $p$ from 2 to 5 on 3-, 4- and 5-regular problem graphs. We record $d(L)$, the size and edge density of the maximum core, and the best width found by any solver, and we follow the gap between them. The research file notes that no existing solver is parameterized by density or coreness. This gives the first data on whether the move from sparse to dense structure with increasing depth appears first in the core.
The second component is the core-first optimizer. Peripheral vertices are removed in dynamic minimum-fill order, with each elimination's fill added to the graph. We keep track of which fill edges land inside $C$; this is the only place where peripheral choices can hurt the core. The result is a smaller reduced core graph. This graph is handed to the same downstream optimizer each baseline uses: the linear-ordering plus dynamic-programming tree builder of Constructing Optimal Contraction Trees for Tensor Network Quantum Circuit Simulation, or the imbalanced-cut method of Improved Cut Strategy for Tensor Network Contraction Orders. Keeping the downstream optimizer fixed means any gain comes from the split, not from a better core solver.
The two stages can interfere. If peripheral fill raises the core's degeneracy, the greedy stage has damaged the instance. We will then fall back to eliminating only those peripheral vertices whose neighbourhoods are already cliques or near-cliques inside the current graph, since these eliminations add little or no fill.
The third component is regime prediction. We fit a small classifier, logistic regression or a depth-3 tree, that predicts which method is best within a fixed time budget. The candidates are greedy, linear-order dynamic programming, cuts, and exact treewidth solvers, plus the question of whether tensor contraction should give way to FeynmanDD. Core statistics are compared against size-only features ($n$, $m$, $m/n$). This tests whether the solver switch Dumitrescu et al. observed above contraction complexity 18 is really a core-density effect.
A secondary transfer study applies the same split to hub-heavy SuiteSparse matrices. Large-Scale Sparse Inverse Covariance Estimation via Thresholding and Max-Det Matrix Completion reports that approximate minimum degree ordering (AMD) keeps Cholesky storage linear on banded graphs but suffers exploding fill on clustered or hub-heavy ones. That paper motivates the question, and it is the only test in the file of whether the idea travels outside quantum simulation.
Baselines
The naive reference point is dynamic minimum-degree or minimum-fill greedy elimination over the whole line graph. This is roughly what Cotengra's greedy mode and RL-TNCO's prefix do. Every competitor must beat it, and it costs almost nothing.
The strongest method on QAOA is the two-stage linear-ordering plus dynamic-programming builder of Constructing Optimal Contraction Trees. It is the strongest because it already beats general treewidth solvers on this exact benchmark. It reports outperforming FlowCutter on 96.4% of test points and Tamaki-2017 on 90.0%, and beating Cotengra on 95% of points for total operations and 84.1% for edge congestion within a 5-second budget.
The strongest method on Sycamore and the large Max-Cut instance is the cut strategy of Improved Cut Strategy for Tensor Network Contraction Orders. It reports reducing FLOPs by at least a third against prior methods on Sycamore and about 25% on the 5,908-tensor Max-Cut network. We also report Optimizing Tensor Network Contraction Using Reinforcement Learning numbers where the benchmark overlaps, including its reported 3.9x FLOP reduction over greedy on the Max-Cut instance, without retraining its policy. For exact solvers, freetdi and meiji-e run through the ConSequences pipeline of Dumitrescu et al.
Fairness works like this. Each core-first variant is paired with the same downstream optimizer run on the full graph, on identical instances, hardware and wall-clock budget. The budgets are 5 s, 60 s and 10 min, and the downstream hyperparameters are tuned once on held-out instances and then frozen for both arms.
Beating a baseline means one of two things. Either we reach equal log2 peak intermediate tensor size and total FLOPs, within 0.5 bits, in at most one fifth of the time. Or we reach strictly lower cost at equal time on a majority of instances.
The key ablation replaces the core-first split with a random vertex subset of the same size given the same budget. This isolates whether the maximum core, rather than simple graph shrinking, is what matters. A second ablation uses the static degeneracy order itself as the elimination order. We expect it to lose to dynamic greedy, which would confirm the reasoning in the Core Claim.
Why not just…?
Why not just use the degeneracy order as the elimination order, as the bounded out-degree argument suggests? Fill-in invalidates the bound, and dynamic minimum-degree greedy strictly refines the static peeling. This is exactly the ablation above. If the static order ever matches dynamic greedy on circuit networks, that would itself be a surprising and reportable result. We do not build on it.
Why not just run a PACE treewidth solver on the whole graph? Dumitrescu et al. show these solvers beat physics-specific tools, with freetdi up to five orders of magnitude faster than quickbb. However, the linear-ordering dynamic-programming paper beats FlowCutter and Tamaki-2017 on over 90% of QAOA points. The cut-strategy paper also shows that ignoring free indices and forcing balanced trees costs FLOPs. Exact solvers also become impractical above roughly a thousand tensors. Core-first is not a rival to these solvers; it is a way of pointing them at a smaller graph. The fair question is whether exact solvers on the core alone beat both exact solvers and the dynamic-programming method on the full graph, and the time-budget sweep answers it.
Why not just use AMD or reverse Cuthill-McKee from sparse linear algebra? Zhang et al. document AMD's fill explosion on hub-heavy and clustered graphs. The results against Cotengra's local heuristics show large room for improvement on circuits. AMD is essentially our naive greedy baseline, so the proposal must beat it outright. The SuiteSparse transfer study tests the matrix setting directly.
Why not just switch to decision diagrams when the graph is dense? This is a real threat on clique-heavy circuits. FeynmanDD reports 0.05 s and 16 MB on 40-qubit bounded linear rank-width circuits where TensorCircuit took over 312 s and more than 100 GB. We do not expect core-first ordering to close a gap that size. What we can offer is a cheap test, based on core density and the width gap, that tells the user when to switch. The bounded rank-width circuits are included so this prediction can fail visibly.
Proposed Experiments
The benchmarks are the file's standard suites. The first is QAOA on 32-vertex 3-, 4- and 5-regular graphs with $p = 2$ to $5$ and ten circuits per setting, plus 64-, 96- and 128-qubit scaling instances. The others are Sycamore circuits at cycle depths 10, 12, 14 and 20; random 3-regular networks from 25 to 225 tensors; the 1,688-qubit, 5,908-tensor Max-Cut network; and FeynmanDD's 40-qubit CZ-clique circuits. We also add a sweep that interpolates CZ-clique density between a sparse ring and a complete clique. Metrics are log2 largest intermediate tensor, total FLOPs, ordering wall-clock, peak RAM when contraction is actually executed on instances small enough to run, and the ratio of achieved width to $d(L)$.
Three checks decide the proposal. The first asks whether core-first optimization matches the full-graph dynamic-programming and cut baselines within 0.5 bits at one fifth the time on QAOA and Sycamore. If it does not, the core does not contain the difficulty, and the central hypothesis is false. The second asks whether core statistics predict the best solver, including the switch near complexity 18 and the tensor-network versus FeynmanDD crossover, with clearly higher held-out accuracy than size-only features. The third asks whether the lower bound $d(L)$ is tight enough to be useful. If it trails achieved width by many bits on deep circuits, the certificate claim shrinks to a diagnostic. That would still help practitioners, but we would report it as a weaker contribution.
References
- Benchmarking treewidth as a practical component of tensor-network-based quantum simulation
- Breaking the Treewidth Barrier in Quantum Circuit Simulation with Decision Diagrams
- Constructing Optimal Contraction Trees for Tensor Network Quantum Circuit Simulation
- Improved Cut Strategy for Tensor Network Contraction Orders
- Large-Scale Sparse Inverse Covariance Estimation via Thresholding and Max-Det Matrix Completion
- Optimizing Tensor Network Contraction Using Reinforcement Learning