Hyper-optimized tensor network contraction

Johnnie Gray; Stefanos Kourtis

Source-linked AI summary

Hyper-optimized tensor network contraction

Johnnie Gray, Stefanos Kourtis

arXiv:2002.01935v4Feb 5, 2020quant-phcond-mat.dis-nnphysics.comp-ph

TL;DR

Arbitrary tensor-network contraction is difficult, and the chosen contraction path exponentially affects computation time and memory. The paper combines randomized contraction-tree construction with hyper-optimization, finding near-optimal paths and estimating a speed-up of over 10,000× for Sycamore ‘supremacy’ circuits.

Problem
Arbitrary tensor-network contraction remains difficult, while contraction-path quality has major implications for computation time and memory, especially in quantum-circuit simulation.
Method
The paper constructs contraction trees for arbitrary networks and hyper-optimizes both the applied algorithms and their parameters over the full tree and total contraction cost.
Results
The methods produce near-optimal contraction paths and outperform established approaches across benchmarks, with an estimated speed-up of over 10,000× for Sycamore ‘supremacy’ circuits.
Takeaways & Limitations
The resulting contraction schemes improve practical performance for tensor-network applications, including classical simulation of amplitudes on Google quantum chips.
Takeaways & Limitations
For planar graphs and grids, the advantage over less sophisticated methods can be modest because good contraction paths are easy to find.

Abstract

from arXiv · show

Tensor networks represent the state-of-the-art in computational methods across many disciplines, including the classical simulation of quantum many-body systems and quantum circuits. Several applications of current interest give rise to tensor networks with irregular geometries. Finding the best possible contraction path for such networks is a central problem, with an exponential effect on computation time and memory footprint. In this work, we implement new randomized protocols that find very high quality contraction paths for arbitrary and large tensor networks. We test our methods on a variety of benchmarks, including the random quantum circuit instances recently implemented on Google quantum chips. We find that the paths obtained can be very close to optimal, and often many orders or magnitude better than the most established approaches. As different underlying geometries suit different methods, we also introduce a hyper-optimization approach, where both the method applied and its algorithmic parameters are tuned during the path finding. The increase in quality of contraction schemes found has significant practical implications for the simulation of quantum many-body systems and particularly for the benchmarking of new quantum chips. Concretely, we estimate a speed-up of over 10,000$\times$ compared to the original expectation for the classical simulation of the Sycamore `supremacy' circuits.

1 Introduction

Tensor networks support many scientific applications, but arbitrary network contraction remains computationally difficult and strongly affects simulation cost. The paper introduces randomized, hyper-optimized contraction-path methods and reports substantial benchmark gains, including over 10,000× for Sycamore circuits.

Tensor networks are used across quantum many-body physics, statistical mechanics, information science, engineering, quantum computation, and machine learning.
Arbitrary-structure tensor-network contraction remains at least #P-hard, including for networks modeling random quantum circuits.
The paper introduces a framework that explicitly constructs contraction trees using agglomerative, divisive, and multiscale drivers.
Hyper-optimization tunes both the contraction method and its parameters against the entire tree and total contraction cost, rather than only leading scaling.
The methods achieve exponential speedups over established approaches across varied problems and often produce near-optimal, automatically customized contraction algorithms.
Over 10,000× speed-up is estimated for classical simulation of Google Sycamore ‘supremacy’ circuits, with broader gains across benchmark tasks.

2 Problem statement

The paper formalizes tensor networks, pairwise contractions, binary contraction trees, and the space and time costs induced by their edge and vertex congestions. It distinguishes contraction width from total contraction cost, which need not yield the same optimal tree.

An edge-weighted graph assigns positive weights to edges, while each vertex has an incidence set containing its incident edges.
A tensor network augments the graph with edge variables, domains, ordered vertex-edge tuples, and tensor functions over those domains.
Contraction removes common edges between tensor pairs and performs inner or outer products, with the paper focusing on contracting all vertices into one.
A rooted binary tree represents the contraction sequence, and its recursively defined incidence sets form the contraction tree embedding.
For qubits, space scales as 2^W, where contraction width is determined by maximum edge congestion and corresponds to maximum minor degree along the path.
Time is governed by total contraction cost, with each qubit contraction proportional to 2^|sl(v)∪sr(v)| operations.
Btime(G) and Bspace(G) can differ, so optimizing one objective does not guarantee finding or approximating the other.

3 Tensor network contraction path optimization

The paper develops contraction-path heuristics spanning exhaustive search, community detection, greedy agglomeration, and divisive partitioning. Hyper-optimization varies algorithmic parameters and targets contraction cost or width through proxies for graph congestion.

Overview: Contraction-path optimization corresponds to minimizing vertex or edge congestion over possible tree embeddings, motivating proxy-based heuristics.The heuristics use established graph algorithms such as balanced bipartitioning and community detection.
3.1 Exhaustive search: Optimal uses dynamic programming over connected subgraphs to find contraction trees minimizing target width W or cost C.The method avoids exhaustive consideration of outer products, which are rarely beneficial.
3.3 Community detection via edge betweenness - Hyper-GN: Community detection contracts intra-community edges first, producing community vertices with lower maximum degree and approximating a space-optimal contraction tree.The method relies on communities being internally dense and sparsely connected to the rest of the network.
3.3 Community detection via edge betweenness - Hyper-GN: Hyper-GN reverses a Girvan–Newman edge-removal list into a contraction path and repeatedly samples weighted variants.Randomization strength τ can be used when incorporating edge weights and bond dimensions.
3.4 Agglomerative contraction trees - Hyper-Greedy: Hyper-Greedy repeatedly samples bottom-up contraction trees using a tunable cost function and Boltzmann weighting, potentially tuning α and τ.It is described as generally outperforming other greedy approaches while remaining quick to run.
3.5 Divisive contraction trees - Hyper-Par: Hyper-Par builds contraction trees top-down by recursively bipartitioning graph substructures and tuning KaHyPar parameters k, ϵ, and a partitioning cutoff.Partition costs depend on outer and crossing indices, so minimizing cut indices minimizes the corresponding contraction cost; hyperedges can be replaced by COPY-tensor subgraphs.

4 Results

The benchmarks cover six tensor-network classes with complex geometries and evaluate optimizers under fixed search limits against contraction width or cost. The study also relates these metrics to practical memory and computational-performance scales.

Benchmark design: Six benchmark classes include random regular graphs, random planar graphs, square lattices, weighted model counting, QAOA energy computation, and random quantum circuits.Each optimizer receives a time limit or maximum number of shots and targets contraction width W or cost C.
Evaluation metrics: W is essentially the space requirement of a contraction, defined as log2 of the largest intermediate tensor size.The benchmarks target either W or contraction cost C.
Practical scale: A complex single-precision tensor of size 2^27 requires 1 GB of memory, while a consumer GPU can typically deliver a few teraFLOPs.The passage associates this performance with approximately C ∼ 10^15 over an hour.
Practical scale: Summit’s memory corresponds roughly to W ∼ 47, while its sustained performance could correspond to C ∼ 10^20 over an hour.The passage cautions that distributed contraction introduces inter-node communication and may reduce achievable performance.

4.1 Random Regular Graphs

On random regular graphs, optimizer differences are small at low sizes but separate as the number of vertices grows. Across degree and target combinations, Hyper-Par ranks best, while Hyper-Greedy’s advantage depends on whether width or cost is optimized.

Setup: Random regular graphs assign each vertex k random connections and represent each edge as a size-2 tensor index.The benchmark studies graph-defined tensor networks with varying vertex counts and regular degree.
Results: For small networks, all optimizers perform similarly and close to Optimal, but a consistent ranking emerges as |V| increases.From worst to best, the ranking is QuickBB, Hyper-Greedy, FlowCutter, Hyper-GN, then Hyper-Par.
Results: Figure 4 plots mean contraction width and cost against vertex count for degree k = 3, 4, and 5 under five-minute optimization budgets.Shaded regions show standard deviations over 100 random graph instances.
Results: Guided stochastic sampling is attributed to Hyper-GN’s improvement over previous studies.The stated optimizer ranking holds across combinations of graph degree and target metric W or C.
Width versus cost: Hyper-Greedy beats QuickBB for contraction width across the board, whereas their contraction-cost results are much closer.Hyper-Par’s advantage over Hyper-GN and FlowCutter is more pronounced for cost than width.

4.2 Random Planar Graphs

Random planar graphs exhibit sub-exponential scaling for all tested optimizers and a different performance ranking from random regular graphs. Hyper-Greedy performs best, but optimizer differences remain relatively small across the studied sizes.

Setup: The planar-graph benchmark generates random instances with |V| from 20 to 200 and assigns size-2 bond dimensions to tensor-network edges.Each optimizer receives five minutes per instance to explore contraction paths.
Scaling: Planar tensor networks have sub-exponential contraction scaling as a consequence of the planar separator theorem.The passage also states that width-optimal paths can be found in polynomial time for planar graphs.
Results: Hyper-Greedy performs best on random planar graphs, unlike the ranking observed for random regular graphs.The performance difference between methods remains relatively small throughout the studied size range.
Results: Figure 5 reports mean contraction width W and cost C versus graph size for optimizers given five-minute search limits.The 35,162 instances are approximately uniformly distributed across the shown |V| bins, with shaded standard deviations.

4.3 Regular Square Lattice

The hyper-optimized methods are evaluated on square-lattice tensor networks against exact TEBD-style and optimal contraction paths. They substantially improve contraction width and cost, closely tracking optimal performance at accessible sizes.

Setup: The comparison evaluates TEBD-Exact, the best Hyper-Greedy or Hyper-Par path, and Optimal paths on square-lattice networks with bond dimension 2.Both open and periodic boundaries, and vertex- versus hyper-edge geometries, are included.
Open boundary conditions: For open boundaries, Hyper-Greedy or Hyper-Par significantly reduces contraction width and cost relative to TEBD-Exact.The TEBD-Exact width scales as 2L in the reported comparison.
Periodic boundary conditions: For periodic boundaries, TEBD-Exact has optimal contraction width but significantly worse contraction cost than the optimized paths.The optimized methods improve cost even when the TEBD-Exact width is already optimal.
Hyper-edge geometry: Hyper-edge representations provide an advantage in both contraction width and cost for open and periodic boundary conditions.Hyper-edges can be converted to COPY tensors to obtain standard tensor-network geometry, but this makes contraction harder.
Overall comparison: At accessible sizes, Hyper-Greedy or Hyper-Par closely tracks the Optimal contraction width and cost in every tested case.This agreement holds across the boundary conditions and representations shown in Figure 6.

4.4 Exact Weighted Model Counting

The paper applies direct hypergraph contraction to exact weighted model counting, avoiding conversion to ordinary tensor-network form. Simplification and hyper-optimization solve 99 of 100 competition instances, outperforming the competition’s best score.

Task: Weighted model counting is an important #P-complete task with applications in graphical-model inference, statistical-physics partition functions, and network reliability.The task is formulated as a sum over all binary-variable assignments.
Representation and method: The weighted-counting expression forms a hyper tensor network whose tensors are variable weights and clause tensors, with variables represented by hyper-edges.The method directly constructs contraction trees for the hypergraph instead of mapping it to a normal tensor network.
Simplification: Simplification reduces 63 of 100 private competition instances all the way to a single scalar.The procedure actively renormalizes tensors because some instance values exceed 10^200.
Results: 99 of 100 instances are solved with contraction paths having W < 20 and C < 10^8 for all but one exceptionally difficult instance.The hyper-optimizer uses 64 repeats with greedy and KaHyPar drivers.
Results: The 99 solved instances compare favorably with the competition’s best score of 69.Results for the 69 competition instances were confirmed against the ADDMC solver.

4.5 QAOA Energy Evaluation

The paper evaluates contraction optimization for QAOA energy calculations on random 3-regular MAX-CUT graphs. Simulations remain workstation-scale through p=4, while p=5 becomes substantially more difficult.

Problem setup: The QAOA experiment computes energies of p-layer ansatz circuits for MAX-CUT on random 3-regular graphs, after cancellations outside each term’s reverse lightcone.The resulting tensor-network geometries differ substantially from those of the earlier random-circuit benchmark.
Evaluation: Figure 8 reports maximum contraction width Wmax and total contraction cost Ctotal across terms, averaged over 10 random-graph instances.The results are shown as functions of graph size N and circuit depth p, with standard-deviation shading.
Results: For p=4 or less, Wmax remains below approximately 28 and Ctotal below approximately 10^10 across the tested N range.These bounds place the simulations within the range of single workstations.
Results: For N=54 and p=4, all contractions take on the order of seconds on a four-core CPU.Increasing to p=5 significantly raises difficulty, especially for N between 40 and 120.

4.6 Random Quantum Circuits

The section benchmarks contraction-path optimizers on random circuits across three chip geometries, showing that performance depends strongly on circuit structure and simplification choices. Hyper-Par performs best overall, while Sycamore circuits expose distinct cost and fidelity trade-offs.

Circuit-specific optimization: The qFlex/PEPs optimizer flattens circuit tensor networks into planar networks before optimizing contraction width or cost.It spatially decomposes entangling gates and contracts tensors within spatial slices.
Results: Hyper-Par performs best across the benchmark suite, with little variance between random circuit instances.The remaining optimizers are harder to rank consistently, and stochasticity contributes to instance-to-instance variation.
Results: For Rectangular-7x7 and Bristlecone-70, diagonal tensor reductions substantially simplify networks, benefiting methods that exploit them.Hyper-Par also achieves lower contraction width, while Hyper-GN and qFlex/PEPs show similar performance without diagonal simplification.
Results: For Sycamore-53, Hyper-Par reaches similar widths to FlowCutter and Hyper-GN but a much lower contraction cost, likely through imbalanced partition trees.The exact Sycamore-53 results avoid approximate gate decompositions so all methods are compared at perfect fidelity.
Fidelity trade-offs: Applying the swapped χ=2 decomposition to all Sycamore layers can reduce fidelity substantially, with an estimated ∼50% total drop at m=20.Using it only in the first and last layers reduced W by ∼4 and C by ∼24 with an estimated ∼5% fidelity drop.

4.7 Practical Performance

Slicing converts a contraction into independent lower-memory contractions, trading reduced width for increased total cost. The authors tune slicing and paths jointly, obtaining practical GPU performance and an estimated over-10,000× speed-up for Sycamore sampling.

Slicing: Slicing reduces each contraction's width and enables embarrassingly parallel evaluation, but generally increases total cost through repeated contractions.Choosing sliced indices balances memory reduction against the resulting sliced cost.
Slicing optimization: The authors greedily sample sliced-index sets and incorporate sliced-cost estimates into Bayesian optimization to target paths that slice well.Optimization continues until a target width is reached, selecting among randomized candidates by sliced cost.
Sycamore slicing: For the m=20 Sycamore-53 circuit, swapped decomposition becomes beneficial at heavy slicing levels, whereas it provides no benefit across a lower-slicing range.Figure 10 compares exact and approximate χ=2 decompositions while optimizing paths for target sliced widths.
GPU evaluation: A sliced width of Ws = 27 fits the target 5GB memory on the NVIDIA Quadro P2000 used for benchmark timing.The reported contraction times use single-precision arithmetic and include slicing overhead.
GPU evaluation: For Rectangular-7x7 and Bristlecone-70, slicing causes little inefficiency, while Sycamore-53 reaches near-theoretical GPU FLOP rates but incurs substantial slicing overhead.Sycamore-53 has no hyper-edges, whereas the other geometries produce pairwise contractions that limit JAX matrix-matrix dispatch.
Sycamore sampling: Over 10,000× speed-up is estimated for classical sampling of the Sycamore supremacy circuits, with a 241-day runtime under 55% GPU FLOP efficiency.The authors suggest distributed contraction or improved slicing could further reduce the overhead.

5 Summary and conclusion

The paper’s heuristic contractors construct contraction trees and use stochastic hyper-optimization to find near-optimal paths, often delivering exponential speedups across benchmarks. Hypergraph partitioning performs especially well, including an estimated over-10,000× speed-up for simulating Sycamore supremacy circuits, while benefits are more modest for graph families where good paths are already easy to find.

Stochastic hyper-optimization tunes contraction algorithms and their parameters against the total contraction cost, producing near-optimal paths and exponential speedups over established methods.The approach explicitly targets the cost of all contraction operations rather than only leading scaling.
Hypergraph partitioning often outperforms the other contraction methods.
Over 10,000× speed-up is estimated for classical simulation of the Sycamore ‘supremacy’ circuits compared to the original expectation.
The methods’ advantage is sometimes modest for planar graphs and grids because good contraction paths are easy to find by inspection or naive greedy search.
The algorithms can support calibration of larger quantum chips, quantum-error-correction decoders, and artificial-intelligence tasks such as inference and model counting.
Approximate contractions and improved slicing strategies remain promising directions for extending the methodology to harder or previously inaccessible tensor-network computations.The paper notes that truncation can improve performance at the expense of accuracy and may enable computations on disordered or irregular systems.