ArcTN: Efficient Tensor-Network Contraction Planning for Quantum Circuit Simulation

AI summary

Overview

Research area: Quantum physics / quantum circuit simulation — specifically tensor-network contraction-order optimization and slicing, a classical simulation tooling problem.

Technical level: Intermediate. The paper assumes some familiarity with tensor networks, contraction paths, and FLOP cost models, but the core ideas (search strategy, planning versus execution time, memory limits) are accessible to anyone with a numerical-computing background.

Scope (one sentence): The paper presents ArcTN, a Rust-based contraction-planning framework with two search presets (Light and Heavy) and two slicing modes (Fixed and Dynamic), evaluated against Cotengra, OMECO, and Google TNCO on the QC32 benchmark and on 672 networks built from 320 MQT Bench circuits.

What This Paper Is About

Simulating a quantum circuit as a tensor network requires choosing an order in which to multiply and sum over tensors, and different orders can differ enormously in arithmetic cost and in the size of the largest intermediate tensor. Finding a good order is a trade-off: more search effort can lower the contraction cost, but the search itself takes time, and memory limits may force the contraction to be split ("sliced") into many smaller tasks. The authors build a planning framework that coordinates candidate generation, selective refinement, and stopping rules, and that couples slicing with re-optimization of the contraction order, then benchmark it against established optimizers.

Key Contributions

1. A coordinated planning framework. ArcTN organizes adaptive candidate generation (random-greedy construction with the cross-entropy method, plus recursive partitioning in Light), selective subtree reconfiguration, parallel tempering, and stage-specific stopping criteria into two presets — Light for low planning overhead and Heavy for lower-cost orders.

2. An executable contraction tool. A Rust implementation with Python interfaces (arctn_path, arctn_schedule, arctn_plan, arctn_contract, ArcTNOptimizer, arctn_tree) that connects order search and slicing to numerical execution, via a native CPU executor using matrixmultiply kernels or an external array backend through opt_einsum. It supports reusable, serializable execution plans and compiled in-process contractions.

3. Two slicing modes coupled to the order search. Fixed selects sliced indices while preserving a given order; Dynamic alternates slice selection with local order refinement and retains the feasible plan with the lowest modeled total cost across all slices, targeting a user-specified bound on intermediate-tensor size.

4. An evaluation of planning and execution benefits. Benchmarks on QC32 (the 32 quantum-computing instances from Einsum Benchmark, comprising 20 scalar-output and 12 tensor-output networks) and on 672 networks built from 320 MQT Bench circuits for amplitude, expectation-value, and state tasks.

Main Findings

• FLOPs and planning-time gains on QC32: On the 30 circuits completed by all eight main configurations, ArcTN Light reduces contraction FLOPs by 61.32% with a 1.62× planning-time speedup over Cotengra Auto/CMA-ES.

• Heavy versus Cotengra AutoHQ/Optuna: ArcTN Heavy reduces FLOPs by 43.83% with a 7.21× planning-time speedup over Cotengra AutoHQ/Optuna.

• Heavy versus OMECO TreeSA-8: Heavy reduces FLOPs by 11.85% with a 1.33× speedup over OMECO TreeSA-8.

• Dynamic slicing meets memory limits: Dynamic slicing satisfies the prescribed intermediate-tensor size limits in all 90 runs on the 18 common scalar-output instances, and reduces total sliced FLOPs by 31.99% relative to Fixed slicing, at the cost of additional planning time.

• Combined planning-plus-execution time: With a common NumPy executor, ArcTN Heavy achieves the lowest combined planning and execution time among five evaluated configurations on their shared successful cases.

• Scaling to larger circuit collections: On 672 additional networks built from 320 MQT Bench circuits, Heavy obtains the lowest geometric-mean FLOPs on the 142 large networks while planning 3.1× and 31× faster than Cotengra AutoHQ and Hyper128, respectively. The paper reports 672 additional networks total across the amplitude, expectation-value, and state tasks.

• Exact integer cost arithmetic: Because all evaluated quantum-circuit networks have index dimension two, ArcTN represents DP costs as exact 128-bit unsigned integers (a tensor with k indices has 2^k elements, computed by bit shift) instead of base-2 logarithms. In the authors' tests this made subtree-reconfiguration DP about 7% faster and fixed-leaf-order DP 13–19% faster without changing results, and it compares tied orders exactly rather than up to rounding.

• Overflow safety: Integer costs are used only when a conservative bound of (n−1)·2^M fits in 128 bits (n = number of input tensors, M = the larger of the number of distinct indices and the largest number of axes of any input tensor). Otherwise, or if any index has a dimension other than two, the DP falls back to logarithmic arithmetic.

• Cost-model sensitivity: A worked example (contracting A ∈ ℂ^{2×8}, B ∈ ℂ^{8×2}, C ∈ ℂ^{2×8}) shows the order (AB)C costs 64 modeled FLOPs with a 16-element largest result, while A(BC) costs 256 FLOPs with a 64-element largest result — a fourfold difference in both metrics from the same expression.

• Slicing is not free: In the same example, slicing index b yields eight tasks meeting a 16-element limit, but the modeled total cost is 8(16+16) = 256 versus 64 for the unsliced order (AB)C, which already meets the limit — the motivation for Dynamic mode re-optimizing the order alongside the slice set.

• Not reported in the provided content: The paper's Section 6 is truncated mid-sentence in the supplied text, so the numerical execution-time speedups on accelerator hardware, the detailed per-instance tables, and the full comparison of all eight configurations are not available in this excerpt.

Methodology in Plain English

The authors treat contraction planning as a search problem with a budget. First, they generate many starting orders cheaply: a "random-greedy" procedure builds an order one pairwise contraction at a time, scoring candidate pairs by a local heuristic that favors a small result relative to its inputs, and then sampling among at most eight candidate pairs with a temperature-controlled probability so that repeated attempts differ. The cross-entropy method adjusts the sampling parameters based on the costs of previously generated orders, so later attempts concentrate on better-behaved settings. Light additionally uses recursive partitioning; both presets search the user's network and a preprocessed ("simplified") version, converting simplified-network orders back into complete orders on the original tensors so all candidates can be compared under one cost function.

Second, they refine only the most promising candidates. Subtree reconfiguration holds part of the contraction tree fixed and uses dynamic programming to find a cheaper way to combine those inputs, accepting the change only if the modeled FLOP count drops. Light refines up to 2 candidates, Heavy up to 8. Then parallel tempering — several search chains at different temperatures that can exchange states — explores beyond local improvements, with a check on whether the initial tempering run reduced the best cost enough to justify continuing. Heavy adds a tempering pass on the simplified network plus optional fixed-leaf-order dynamic programming (applied when the simplified network has at most 5000 tensors), followed by a final subtree reconfiguration.

Third, search effort is bounded at two levels: each stage stops when it stops making sufficient progress, and the overall run is capped by a user-specified time limit plus a "rate rule" that estimates execution time as F(P_best)/r and halts search once elapsed time exceeds that estimate, so finding a cheaper order can itself shorten the remaining search.

Fourth, for memory constraints they add slicing. Fixed mode takes the chosen order and progressively selects labels from results that exceed the size limit. Dynamic mode applies that procedure, then collapses the sliced indices to dimension one, applies subtree reconfiguration to that single slice representation, accepts the revised order if it does not increase per-slice cost, and re-selects slices from scratch — comparing resulting feasible plans by total sliced cost and keeping the cheapest.

Finally, they benchmark against six baseline configurations from Cotengra (Auto/CMA-ES, AutoHQ/Optuna, Hyper128/Optuna), OMECO TreeSA-8, and Google TNCO (with and without fusion), running each five times per instance on Intel Xeon Platinum 8253 processors at 2.20 GHz with approximately 2.95 TiB of memory, eight physical cores per run, and a 3600-s external limit. All returned plans are re-evaluated on the original networks under the same cost model.

Why This Matters

Impact on research. Classical simulation underpins algorithm development, device validation, and the study of quantum dynamics. Since many tasks need only an amplitude, an expectation value, or a reduced density matrix rather than the full state vector, tensor-network contraction is a practical route — but only if the contraction order is good and findable within a reasonable budget. ArcTN's contribution is not a new search primitive but the coordination of existing ones, with explicit accounting for planning time and tensor-size limits. The release of benchmark scripts, input manifests, and recorded results supports independent inspection of returned paths and reported costs.

Real-world applications:

• Verifying and benchmarking quantum hardware by classically simulating circuits and comparing amplitudes or expectation values.
• Compiling and validating quantum algorithms at scales beyond brute-force state-vector simulation.
• Studying quantum dynamics in condensed-matter and chemistry-inspired models where only selected observables are needed.
• Providing reusable execution plans for workloads where the same network structure is contracted repeatedly with new tensor values.

Industry relevance. The planning-versus-execution trade-off is directly relevant to anyone running simulations at scale, where a cheaper path that takes hours to find may be worthless for a one-off contraction but valuable for a reused plan. The Rust implementation with Python interfaces and compatibility with Cotengra contraction trees, opt_einsum expression building, and backends such as NumPy, CuPy, PyTorch, and JAX lowers the cost of adoption in existing workflows. The explicit tensor-size bound addresses a practical constraint: an order with low FLOPs is useless if its intermediate tensor does not fit in memory.

Future Directions

1. Accelerator execution results. The evaluation setup promises to test "whether these results carry over to accelerator hardware," and the tool supports CuPy, PyTorch, and JAX backends, but the supplied content truncates before reporting those results — leaving open how modeled FLOP reductions translate into GPU wall-clock time, where memory traffic and layout dominate.

2. Bridging the modeling gap. The paper acknowledges that execution time depends on data layout, memory traffic, and the shapes of individual operations, not just the FLOP count. Whether slicing and order choices can be tuned directly against measured backend performance rather than a static cost model is an open question.

3. Broadening the arithmetic fast path. Exact 128-bit integer costs apply only when all indices have dimension two and the overflow bound fits; extensions to mixed or larger bond dimensions, or to wider integer types, would widen the benefit beyond qubit circuits.

4. Slicing for repeated and batched workloads. The total sliced cost model assumes slices run independently and excludes final accumulation and output assembly. Accounting for accumulation cost and for parallelism across slices could change which plan is optimal, particularly when many slices can be run concurrently.

Target Audience

Researchers and engineers working on classical simulation of quantum circuits, tensor-network methods, and numerical contraction libraries. It is most useful to practitioners who already use Cotengra, OMECO, or opt_einsum and need to reason about planning overhead, intermediate-tensor memory limits, and plan reuse. Quantum-computing teams that classically verify circuits or compute amplitudes and expectation values at scale will also benefit, as will developers of numerical array frameworks looking for a concrete example of coupling a combinatorial search with an execution backend.

Authors’ abstract

Tensor-network simulation of quantum circuits depends on contraction orders with low computational cost and small intermediate tensors, found without excessive planning time. We present ArcTN, a contraction-order optimization framework with two search presets. Light keeps planning overhead low, and Heavy spends more effort on refinement. Both combine randomized-greedy construction, subtree reconfiguration, and parallel tempering with stage-specific stopping rules. ArcTN also provides Fixed and Dynamic slicing to meet tensor-size limits and executes the returned orders. On the 30 QC32 quantum-circuit networks completed by all eight compared configurations, Light reduces FLOPs by 61.32% and plans 1.62$\times$ faster than Cotengra Auto/CMA-ES, and Heavy reduces FLOPs by 43.83% and plans 7.21$\times$ faster than Cotengra AutoHQ/Optuna. Heavy also needs 11.85% fewer FLOPs than OMECO TreeSA-8 and plans 1.33$\times$ faster. Dynamic slicing meets the size limits in all 90 runs on 18 scalar-output networks and reduces total sliced FLOPs by 31.99% relative to Fixed slicing, at the cost of longer planning. With a common NumPy executor, Heavy has the lowest combined planning and execution time among five configurations on the runs that all of them completed. On 672 networks built from 320 MQT Bench circuits, Heavy obtains the lowest geometric-mean FLOPs on the 142 large networks while planning 3.1$\times$ and 31$\times$ faster than Cotengra AutoHQ and Hyper128.