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

1 Introduction

• Contraction orders vary substantially in arithmetic cost and intermediate tensor size, while greater search effort and slicing can change planning or total computation costs.Modeled operation counts also do not guarantee faster execution on a particular backend.Source: §1 · p. 2
• Light and Heavy combine cross-entropy-adapted random-greedy generation, multiple starting orders, subtree reconfiguration, parallel tempering, and stage-specific stopping rules.Light prioritizes low planning overhead; Heavy spends more effort seeking lower-cost orders.Source: §1 · p. 2
• Fixed slicing selects indices while preserving the chosen order, whereas Dynamic slicing alternates slice selection with local order refinement to retain a feasible plan with the lowest modeled total cost.Both modes target a user-specified bound on contraction-result size within each slice.Source: §1 · pp. 2–3
• ArcTN provides Rust implementation and Python interfaces for order search, optional slicing, numerical execution, and reusable plans that avoid repeating order search with new tensor values.Source: §1 · p. 3
• On QC32, Light reduces FLOPs by 61.32% and plans 1.62× faster than Cotengra Auto/CMA-ES, while Heavy reduces FLOPs by 43.83% and plans 7.21× faster than Cotengra AutoHQ/Optuna.Heavy also achieves the lowest combined planning–execution time among five configurations using a common NumPy executor.Source: §1 · p. 3
• On large MQT Bench networks, Heavy obtains the lowest geometric-mean FLOPs while planning 3.1× and 31× faster than Cotengra AutoHQ and Hyper128.Source: §1 · p. 3

2.1 Tensor Networks and Contraction

• A contraction problem specifies input tensors, ordered index labels, label dimensions, and ordered output labels; in circuits, the requested quantity determines which indices remain.Circuit gates and initial states are represented as tensors, with connected indices expressing operation composition.Source: §2.1 · pp. 3–4

2.2 Contraction Orders and Their Costs

• The same contraction expression can have substantially different modeled costs and intermediate sizes under different binary orders.A binary order contracts pairs of current tensors while retaining labels needed by other tensors or the requested output.Source: §2.2 · pp. 4–5
• 4× as many modeled operations and a fourfold larger maximum result tensor are required by the B–C-first order, although both orders produce the same output.The comparison illustrates how contraction order changes cost and intermediate size without changing the expression’s output.Source: Table 1 · p. 5, §2.2 · p. 5
• FLOPs counts modeled scalar multiplications from network structure, while the largest-result-size metric counts elements in the biggest contraction result, not total process memory.Total process memory also depends on input storage, simultaneously live results, element type, execution order, and backend workspace.Source: §2.2 · p. 6

2.3 Planning Objectives and Practical Tradeoffs

• More search may improve an order but must be weighed against planning time and expected execution savings; modeled operation count alone does not determine execution time.Search overhead may dominate for small contractions, while reuse across contractions can make more extensive search worthwhile.Source: §2.3 · p. 6

2.4 Slicing under Tensor-Size Constraints

• Slicing fixes selected indices to split oversized contractions, but plans must minimize total work across slices subject to a per-slice result-size bound.The stated cost excludes final accumulation and output assembly.Source: §2.4 · pp. 6–7

3 ArcTN: Architecture and Capabilities

• ArcTN takes an upstream network description through planning, optional slicing, and numerical execution, separating structural planning from execution on tensor values.This separation also supports external execution and reuse with new tensor values.Source: §3 · p. 7, Figure 3 · p. 8

3.1 Planning Interfaces and Controls

• Light emphasizes low planning overhead, while Heavy spends more effort on candidate refinement; users can also set a seed and search-time or rate-based limits.Interfaces range from returning paths and schedules to executable plans and direct contraction.Source: §3.1 · p. 8

3.2 Numerical Execution and Plan Reuse

• ArcTN supports native CPU execution and external array backends, plus saved plans and compiled in-process reuse for repeated computations.Saved plans can be loaded and executed without repeating the search; compiled reuse currently supports unsliced contractions.Source: §3.2 · pp. 8–9

3.3 Availability

• The public repository provides documentation, benchmark scripts, input manifests, and recorded results for independent inspection of paths and costs.Source: §3.3 · p. 9

4 Contraction Planning in ArcTN

• ArcTN builds multiple candidate orders, refines selected ones, and returns the lowest-cost order found.Multiple starting points let refinement explore orders whose initial costs may not predict their eventual quality.Source: §4 · p. 9

4.1 Candidate Generation

• Both presets use random-greedy construction and cross-entropy sampling; Light also uses recursive partitioning, while candidates from original and simplified networks are compared on the original network.Heavy also retains simplified-network orders as starting points for additional search.Source: §4.1 · p. 9

4.2 Selective Refinement

• Subtree reconfiguration replaces a local tree only when it lowers modeled cost, and parallel tempering explores beyond local improvements with staged continuation when initial progress suffices.Heavy refines more candidates than Light and adds simplified-network search followed by optional fixed-leaf-order dynamic programming.Source: §4.2 · p. 10

4.3 Search Control

• Each stage stops when progress is insufficient, while a user-set time limit and optional rate rule bound overall search effort.The rate rule estimates execution time as the best order's modeled cost divided by an assumed operations-per-second rate.Source: §4.3 · p. 12

4.4 Fixed and Dynamic Slicing

• Fixed slicing selects labels for an existing order to meet the result-size limit; Dynamic alternates slice selection with order refinement and retains the feasible plan with lowest total sliced cost.Dynamic accepts a revised order when its cost for the current slice does not increase, then compares feasible plans by total cost.Source: §4.4 · pp. 12–13

5 Implementation Design

• For dimension-two quantum-circuit networks, ArcTN represents costs as exact 128-bit integers, making subtree-reconfiguration DP about 7% faster and fixed-leaf-order DP 13–19% faster without changing results.A conservative bound guards against overflow; other dimensions or bounds that do not fit trigger logarithmic arithmetic.Source: §5 · p. 13

6.1 Experimental Setup

• QC32 comprises 32 dimension-two networks—20 scalar-output and 12 tensor-output—and the planning comparison evaluates eight configurations with five runs per instance.Source: §6.1 · pp. 13–14

6.2 Planning Efficiency and Contraction Quality

• Light reduces FLOPs by 61.32% and plans 1.62× faster than Cotengra Auto, while Heavy reduces FLOPs by 43.83% and plans 7.21× faster than AutoHQ.Heavy also outperforms OMECO on both planning time and FLOPs and has the lowest geometric mean for all four reported cost and storage measures.Source: §6.2 · p. 15, Table 5 · p. 16, Figure 4 · p. 16

6.3 Numerical Execution Benefits

• Heavy achieves the lowest geometric mean for contraction and total time, reducing total time by 13.99% versus Light, 21.97% versus OMECO, and 53.67% versus AutoHQ.The totals include planning, execution, and associated overhead.Source: Table 6 · p. 17, §6.3 · p. 17

6.4 Planning under Tensor-Size Constraints

• All retained plans meet their size limits; Dynamic reduces total FLOPs versus Fixed by 31.99% for scalar outputs and 27.04% for tensor outputs, with additional planning time.Source: Table 8 · p. 18, §6.4 · p. 18

6.5 Deployment and Evaluation on the Hygon Cluster

• On the six circuits completed by all three configurations, Light and Heavy reduce planning and contraction time versus Cotengra; their total-time speedups are 5.91× and 6.53×.Heavy achieves the lowest contraction and total times on those six circuits.Source: Table 9 · p. 19, §6.5 · p. 19

6.6 Evaluation on Additional Realistic Quantum Circuits

• The reported results show that, on the 530 small networks, Heavy, AutoHQ, Hyper128, and OMECO with 200 iterations are within 4% of each other in geometric-mean FLOPs.Source: §6.6 · p. 20
• On 142 large MQT Bench networks, Heavy has the lowest geometric-mean FLOPs; AutoHQ and Hyper128 require 1.34× and 1.23× its FLOPs, with 3.1× and 31× its planning time.Light requires 1.29× Heavy’s FLOPs in about half its planning time.Source: Table 11 · p. 21, §6.6 · p. 21

• Cotengra combines greedy or partition-based construction, parameter tuning, local tree changes, simulated annealing, and slicing.Source: §7 · p. 21
• OMECO provides TreeSA for annealing-based tree improvement and TreeSASlicer for selecting slices; TNCO also searches contraction trees through simulated annealing, [12],,.Source: §7 · p. 21
• quimb constructs tensor networks, opt_einsum prepares reusable contraction expressions, cuTensorNet combines planning with GPU computation, and TNC distributes contractions using MPI.ArcTN exposes orders as paths or trees and provides executable plans for its own executor or external numerical libraries.Source: §7 · p. 22

8 Conclusion

• ArcTN integrates contraction-order search, slicing, and reusable execution plans through Python interfaces to a Rust implementation.Source: §8 · p. 22
• With a common NumPy executor, Heavy has the lowest geometric-mean contraction time and total planning–execution time among five tested configurations.Source: §8 · p. 22
• On networks built from MQT Bench circuits, Heavy obtains the lowest geometric-mean FLOPs on the large networks and requires much less planning time than Cotengra AutoHQ and Hyper128.Source: §8 · p. 22

A QC32 Circuit Set

• Of 32 archived QC32 instances, two are omitted from the common comparison; the 30-instance comparison has 28 distinct structures and equal instance weighting.Source: A QC32 Circuit Set · p. 24
• Grid-instance tensor outputs have more open indices than qubits and should not be interpreted as full state vectors.Source: A QC32 Circuit Set · p. 24

• Appendix B gives the details of the evaluation in Section 6.6.Source: B MQT Bench Benchmark Details · p. 24

B.1 Circuit selection

• The selection uses all circuits from 14 problem-specific families and circuits at 10, 20, through 130 qubits from 14 families available at every qubit count.Source: §B.1 · p. 24
• Table 12 lists QC32 circuit types, sources, and output shapes.Source: Table 12 · p. 25
• Rank is the number of open output indices; with dimension-2 indices, the output contains 2^r elements.Source: §B.1 · p. 25
• Depth counts gate layers when each gate is placed directly after the last gate on any of its qubits; gate counts exclude measurements and barriers.Source: §B.1 · p. 26

B.2 Network construction

• Networks are built and simplified with quimb, including exact gate decompositions where needed, and small-network contractions are checked against dense-state-vector results.Source: §B.2 · p. 26

B.3 Run protocol

• Planning time runs from planner-API entry until return, and a common evaluator recomputes metrics from each returned order on the simplified network.Source: §B.3 · p. 26

B.4 Complete results

• Tables 14 and 15 report four cost measures and planning time across network-size classes and task categories.Table 14 groups networks by size; Table 15 groups them by task.Source: §B.4 · p. 26, Table 14 · p. 28, Table 15 · p. 29
• Table 13 describes MQT Bench circuit families and the numbers of planned networks for each task.Each circuit yields one amplitude network, two expectation networks, and one state network; task entries count planned networks.Source: Table 13 · p. 27
• Table 14 reports geometric means relative to Heavy, with values above one favoring Heavy.The measures are Writes, Largest, Peak, and planning Time; size classes include network and tensor counts.Source: Table 14 · p. 28
• Table 15 groups results by task, with Expectation combining the two listed expectation-value tasks.Its columns use the same measures as Table 14.Source: Table 15 · p. 29