PaperlayerView exact revision on arXiv

Source-linked AI summary

Pareto-Efficient Quantum Circuit Simulation Using Tensor Contraction Deferral

Edwin Pednault, John A. Gunnels, Giacomo Nannicini, Lior Horesh, Thomas Magerlein, Edgar Solomonik, Erik W. Draeger, Eric T. Holland, Robert Wisnieff

arXiv:1710.05867v4quant-ph

TL;DR

Computing quantum-state amplitudes becomes exponentially difficult as circuits grow, limiting assessment of algorithms and device fidelity. The paper combines tensor-network generalizations, contraction deferral, slicing, and storage-hierarchy techniques, demonstrating large-circuit simulations with far lower memory requirements than contemporary methods and extending simulation through secondary storage. The approach is evaluated on universal random circuits, including complete-state and sliced-amplitude calculations.

  • Problem

    Quantum-state amplitudes are needed to assess algorithm correctness, performance, scaling, and device fidelity, but their computation generally has exponential resource requirements.

  • Method

    The methodology combines hyperedges, non-adjacent tensor contractions, tensor slicing, circuit partitioning, and secondary storage to calculate quantum states efficiently.

  • Results

    4.5 Terabytes and 3.0 Terabytes of main memory supported depth-27 7 × 7 and depth-23 8 × 7 simulations, compared with 8 Petabytes and 1 Exabyte required by contemporary techniques.

  • Takeaways & Limitations

    Contraction deferral combined with slicing and storage-hierarchy techniques extends classical simulation to circuits that previously exceeded practical resource requirements.

  • Takeaways & Limitations

    The reported optimization baselines consider only non-sliced contraction deferral across qubit lines and exclude communication buffers from memory footprints.

Abstract

from arXiv · show

With the current rate of progress in quantum computing technologies, systems with more than 50 qubits will soon become reality. Computing ideal quantum state amplitudes for circuits of such and larger sizes is a fundamental step to assess both the correctness, performance, and scaling behavior of quantum algorithms and the fidelities of quantum devices. However, resource requirements for such calculations on classical computers grow exponentially. We show that deferring tensor contractions can extend the boundaries of what can be computed on classical systems. To demonstrate this technique, we present results obtained from a calculation of the complete set of output amplitudes of a universal random circuit with depth 27 in a 2D lattice of $7 \times 7$ qubits, and an arbitrarily selected slice of $2^{37}$ amplitudes of a universal random circuit with depth 23 in a 2D lattice of $8 \times 7$ qubits. Combining our methodology with other decomposition approaches found in the literature, we show that we can simulate $7 \times 7$-qubit random circuits to arbitrary depth by leveraging secondary storage. These calculations were thought to be impossible due to resource requirements.

1 Introduction

The paper addresses the exponential cost of computing quantum-state amplitudes by combining tensor representations, slicing, secondary storage, and deferred contractions. It demonstrates this methodology on large universal random circuits, substantially reducing memory requirements relative to prior techniques.

  • Quantum-state amplitude calculations are needed to assess quantum algorithms, devices, and circuit fidelity, but their difficulty generally grows exponentially with circuit size.The paper targets calculating entire quantum states or selected portions of them.
  • Tensor representations combine tensor computations, tensor slicing, and optimized secondary storage to calculate final states in slices rather than materializing entire states in memory.A second simulation stage extends limited-depth calculations to arbitrary depths when sufficient secondary-storage resources are available.
  • Tensor contraction deferral permits non-adjacent contractions and decomposes circuits into independently simulated subcircuits that are later combined.This reduces resource requirements relative to approaches restricted to adjacent contractions.
  • 4.5 Terabytes and 3.0 Terabytes of main memory supported depth-27 7 × 7 and depth-23 8 × 7 simulations, versus 8 Petabytes and 1 Exabyte required by contemporary techniques.The simulations were performed on the Vulcan IBM Blue Gene/Q supercomputer.

2 Methods

The methods represent quantum circuits as tensor networks and extend standard contraction strategies with hyperedges, non-adjacent contraction deferral, tensor slicing, and circuit partitioning. These choices expose memory–computation trade-offs while enabling independent subcircuit simulation and recombination.

  • Simulation setup: The simulation input is a quantum circuit and a specified set of output amplitudes, with the entire state vector as the main target.Exact access to the full state can reveal properties of outcome distributions that limited samples cannot infer.
  • Main building blocks: Contraction deferral partitions a circuit into independently simulated subcircuits whose deferred entanglement indices are contracted later to obtain amplitudes.Tensor slicing fixes selected hyperedge values, producing smaller tensors that can be computed iteratively.
  • Main building blocks: The proposed representation uses hyperedges for diagonal or separable gates, non-adjacent contractions, and tensor slicing to increase flexibility beyond conventional adjacent contractions.Diagonal rank-k tensors require O(2^(k/2)) memory rather than O(2^k), improving correspondence between tensor ranks and actual memory occupancy.
  • Optimization and trade-offs: Partitioning circuits along qubit lines and combining subcircuits exposes a trade-off between memory usage and floating-point computation.For the 49-qubit depth-27 circuit, optimization reduced computation to 2^9,16 FLOPs per amplitude, approximately 2^8,5 times less than the baseline strategy.
  • Optimization and trade-offs: The strategy searches among many circuit partitions, contraction sequences, gate transformations, and slicing choices, with non-sliced contraction deferral serving as a baseline.The resulting resource trade-offs can remain relatively flat as memory decreases until a threshold below which computational costs rise sharply.

3 Results

The experiments evaluate simulation results and circuit-generation changes using sliced amplitudes, storage-aware execution, and Pareto-frontier analysis. The revised generation rules generally increase simulation difficulty, with final Hadamard layers having the largest effect.

  • Simulation results: 2^11 slices of 2^38 amplitudes were computed for the 49-qubit circuit, while one 2^37-amplitude slice was computed for the 56-qubit circuit.The 56-qubit slice was one of 2^19 slices defining the final state.
  • Simulation results: More than 32 TB of memory was required in practice for the experiments, despite a theoretical slice footprint below 5 TB for the 49-qubit circuit.The parallel calculations used 64 TB of aggregate memory across 4,096 nodes.
  • Simulation results: The 49-qubit outcome-probability distributions across slices were virtually identical and closely matched the predicted distributions.Histograms used log-transformed probabilities to compare observed and theoretically expected distributions.
  • Circuit-generation analysis: The 7 × 8 depth-23 circuit becomes computationally expensive at higher memory thresholds than the 8 × 7 circuit as available memory decreases.The analysis uses Pareto-frontier bends to compare simulation difficulty.
  • Circuit-generation analysis: Control ⪅ CZ < SG ⪅ SG & H < H < CZ & SG < CZ & H ⪅ CZ & SG & H summarizes the relative simulation difficulty of the circuit variants.The ordering is based on the bend locations of their computation-versus-memory Pareto frontiers.
  • Circuit-generation analysis: All circuit-generation changes tend to increase simulation difficulty, with final Hadamard layers appearing more impactful than the revised CZ-gate sequence.Combining all changes dramatically increases required computational resources, although the circuits remain within reach of existing supercomputers.

4 Discussion

The discussion presents the methodology as a set of techniques that enabled unusually large universal random-circuit simulations. It emphasizes contraction deferral, tensor slicing, and storage-hierarchy-aware partitioning while identifying further combinations as future work.

  • Discussion: The methodology enabled simulation of universal random circuits that were, for some time, among the largest simulated.The paper describes this as a central outcome of introducing and extending several techniques.
  • Discussion: Contraction deferral is identified as a key contribution, especially when combined with tensor slicing.The discussion links this combination to simulations of circuits deeper than those presented in the paper.
  • Discussion: Extending partitioning and slicing across the memory hierarchy makes secondary storage a viable option for quantum-circuit simulation.The authors state that these techniques can also be leveraged on conventional servers.
  • Discussion: Whether combining sliced and non-sliced contraction deferral along and across qubit lines provides additional benefits remains an open question.The authors leave both the potential benefit and its extent for future exploration.

A Supplementary Information

The supplementary information provides a formal mathematical account of the simulation methodology and uses it to estimate feasibility for deep 49-qubit circuits.

  • Supplementary Information: The appendix formalizes the algorithms and describes a methodology capable of simulating deep 49-qubit circuits to arbitrary depth.It also gives safe estimates of the required wall-clock time for such computations.

A.1 Preliminaries

The preliminaries define the hypergraph-based tensor-network representation and extend contraction to non-adjacent vertices. They establish the formal basis for the paper’s simulation methodology.

  • Network representation: A tensor network is represented by vertices, a hyperedge multiset, and a labeling function assigning index labels to hyperedges.The formal components are a vertex set V, hyperedge multiset E, and labeling function λ.
  • Network representation: Hyperedges are ordered subsets of vertices, with the first and last nodes designated as tail and head.These definitions support the directed indexing conventions used in the formalism.
  • Scope: The formal treatment addresses concepts that the authors state were not previously formalized and systematically used for quantum-circuit simulation.The claim is framed as a statement about the authors’ knowledge of the literature.
  • Contraction: The paper defines contraction between any two vertices, including non-adjacent vertices, by replacing them with a new vertex and updating incident hyperedges.This generalizes conventional tensor-network contractions beyond adjacent nodes.
  • Contraction: Traditional contractions occur when vertices share connecting edges, while contractions without such edges form outer products.If both tensors are diagonal, the resulting tensor is diagonal.
  • Contraction: Pairwise contractions over a fixed set of nodes produce the same outcome regardless of order, although computational cost may depend on the order.This motivates generalizing contraction from pairs to vertex subsets.

A.2 Simulation of quantum circuits

Quantum circuits are represented as directed tensor networks whose nodes and hyperedges encode states, gates, and open output wires. Simulation contracts all tensor nodes while balancing fast primary storage against larger secondary storage.

  • Circuit representation: The initial state uses q rank-1 |0⟩ tensors, while q output hyperedges terminate at ⟨0|, ⟨1|, or open-wire node O.The node O represents output wires and cannot be contracted.
  • Circuit representation: A quantum circuit on q qubits and depth D forms a layered tensor network with D + 2 layers and at most q input and output hyperedges per layer.Non-boundary gates are assumed to be rank-2 or rank-4 tensors, although the analysis extends to gates involving more qubits.
  • Simulation model: A simulation strategy is a sequence of contractions that removes every tensor node except the special output node O.The output node is excluded because it does not represent a tensor.
  • Resource model: Contractions are evaluated using both primary storage, such as RAM, and larger but slower secondary storage, such as disk.The framework explicitly treats memory occupation and operation count as computational requirements.
  • Resource model: A rank-n contraction requires O(2^n) space, but its result can be written to disk when the contraction is the computation’s final goal.This permits unavoidable large intermediate results to reside outside RAM.

A.3 Asymptotic performance of quantum circuit simulation strategies

Standard quantum-circuit simulation strategies trade time against memory, while later methods improve asymptotic bounds through tensor-network structure and recursive circuit decomposition.

  • Standard strategies: The Schrödinger approach contracts the circuit layer by layer, creating an O(2^q)-size state tensor and requiring exponential memory in the qubit count.It follows the circuit’s topological ordering and contracts each layer sequentially.
  • Standard strategies: The Feynman approach computes output amplitudes one at a time by summing over paths, with cost O(2^(n+qD)) and memory O(nD).Here n is the number of open output wires and the circuit has O(qD) hyperedges.
  • Improved bounds: Tensor-network treewidth methods achieve runtime exponential in the network treewidth when computing a single final-state amplitude.Their stated setting assumes a complete set of q output states ⟨0| or ⟨1|.
  • Improved bounds: Recursive layer splitting gives a general-circuit algorithm with time O(q(2D)^(q+1)) and memory O(q log D).The circuit is recursively divided into halves by depth.
  • Improved bounds: For two-dimensional grid connectivity, combining grid partitioning with recursive layer splitting reduces runtime while increasing space to O(Dq log q).Grid partitions create subcircuits connected by small cut sets.

A.4 Slicing

Slicing fixes selected boundary indices and computes the resulting tensors separately, reducing primary-memory demand while preserving essentially the original total contraction work.

  • Slicing mechanism: A contraction with n boundary hyperedges and m interior hyperedges costs O(2^(n+m)) time and memory before slicing.The unsliced result is a rank-n tensor that can then be contracted with another tensor set.
  • Slicing mechanism: Slicing s hyperedges creates 2^s tensors, each requiring O(2^(n−s+m)) computation and O(2^(n−s+m)) primary storage.The selected hyperedges are fixed to every possible binary assignment.
  • Benefits: Slicing preserves essentially the original total contraction cost but enables parallel execution and can keep only a few slices in primary storage.Reordering computation is the key to avoiding simultaneous storage of all sliced tensors.

A.5 Our simulation strategy

The proposed strategy partitions a circuit into manageable subcircuits, contracts them in an ordered schedule, defers selected inter-subcircuit contractions, and uses secondary storage when needed.

  • A.5 Our simulation strategy: The method partitions the tensor network into subcircuits with manageable ranks and few interconnecting hyperedges, then contracts each subcircuit in layers.For full-state simulation, all output wires are assumed open; narrower output structures may reduce memory bounds.
  • Computation order: Subcircuits are assigned ordered computation steps, with precedence relations allowing completed subcircuits to initialize immediately subsequent ones.The computation order must remain nondecreasing along each hyperedge.
  • Deferred contractions: Tensor contraction deferral slices hyperedges linking subcircuits across computation steps when they violate the precedence relation.All such deferred hyperedges belong to Δ and are fixed during the algorithm’s loop over sliced assignments.
  • Algorithm: At each sliced assignment, the algorithm contracts a subcircuit using the Schrödinger method, then stores tensors from the current computation step to secondary storage.Intermediate disk operations may be skipped when the tensors fit in primary storage.
  • Resource analysis: Step 4 requires O(ℓ_i2^(m_i)) time and O(2^(m_i)) primary storage for subcircuit V_i.The bound follows from the number of layers within V_i and the maximum boundary rank m_i.
  • Resource analysis: Deferred-contraction indices correspond to Γ_i, and the experiments did not slice these indices further.The text identifies sliced contraction deferral as a possible extension rather than an experimental component.

A.6 An example of possible computation schemes

The example partitions a small circuit into subcircuits and uses sliced indices to avoid materializing the full state vector. The same partitioning ideas extend to the larger circuits studied in the paper.

  • Example circuit: The 4 × 1, depth-15 circuit is partitioned into three subcircuits with a specified computation order and precedence relations.The subcircuits are labeled |φ⟩, |ξ⟩, and |ψ⟩.
  • Deferred contractions: Deferred entanglement indices must remain available until the relevant subcircuits are combined.The j1 index cannot be contracted away before the top and bottom subcircuits are combined.
  • Memory use: 21-dimensional slices can be computed without allocating the full 24-dimensional state vector.Individual slices may remain in primary storage when they fit, avoiding secondary-storage input/output.
  • Scaling the scheme: The partitioning scheme used for the 7 × 7 depth-27 and 8 × 7 depth-23 circuits follows the same general construction.The larger circuits use analogous partitioning, with some details omitted because of their size.

A.7 Determining a computation scheme via integer programming

The paper formulates circuit partitioning as an integer program that assigns tensors and sliced edges to subcircuits while modeling computation order and tensor ranks. Its objective minimizes the largest subcircuit rank, and reported solutions are nearly optimal for the simulation settings.

  • Model formulation: Circuit partitioning is posed as a discrete optimization problem over subcircuits, computation steps, sliced hyperedges, and tensor ranks.The circuit is represented by a hypergraph, and the computation-step sequence is treated as given.
  • Decision variables: Each tensor is assigned to exactly one subcircuit, while binary variables identify sliced edges and inter-subcircuit rank contributions.Additional integer variables represent subcircuit ranks and computation-step complexity.
  • Constraints: The constraints enforce nondecreasing computation steps along hyperedges and define when edges are sliced or contribute to subcircuit rank.Sliced edges connecting separated computation steps contribute to the rank of the subcircuit containing their tail tensor.
  • Objective: The primary objective minimizes the rank of the largest subcircuit, with secondary terms controlling rank variables and the number of subcircuits.This avoids explicitly modeling exponential total memory in the objective.
  • Optimization results: After 5 hours, the integer-programming results show that the simulation partitionings are nearly optimal, especially with four subcircuits.The reported comparison uses best solutions and lower bounds for the maximum subcircuit rank.

A.8 Computation of single amplitudes

Single amplitudes are computed by partitioning a circuit in both depth and spatial directions, constructing four tensors, and choosing an efficient contraction order. The method targets circuits whose full state vectors cannot fit in primary memory, including a 7 × 7 depth-46 circuit.

  • Single-amplitude method: The method extends the partitioning framework from full-state simulation to single-amplitude calculations.It combines recursive-partitioning ideas with tensors constructed using the paper’s computation scheme.
  • Depth partitioning: A circuit is split into early and late layers, simulated in input-to-output and output-to-input order, then combined to obtain ⟨x|RL|y⟩.The two halves correspond to L|y⟩ and R†|x⟩.
  • Row-wise partitioning: Each depth half is further split row-wise so the four resulting subcircuits can be constructed without storing the full state vectors.Bridging gates are assigned to partitions, with entanglement indices introduced as needed.
  • Contraction order: The more efficient contraction order combines top tensors and bottom tensors horizontally before the final contraction.This order creates smaller intermediate tensors and requires fewer floating-point operations.
  • Resource requirements: 140 TB of storage is required for the four tensors in the 7 × 7 depth-46 example, while the two intermediate tensors require 0.5 TB each.The four tensor requirements are 4 TB, 64 TB, 8 TB, and 64 TB.
  • Runtime estimates: Expected runtimes are 17.93 hours on Vulcan and 4.76 hours on Sequoia, although the simulations themselves were not carried out.The estimates are safe upper bounds based on benchmarked computational loads and estimated communication times.

A.9 Leveraging secondary storage

The paper combines circuit partitioning, tensor slicing, and secondary storage to extend simulation beyond main-memory limits, including deeper 7 × 7 circuits. Its estimates indicate that secondary storage can support arbitrary-depth simulation when storage-transfer costs remain non-dominant.

  • A.9 Leveraging secondary storage: Secondary storage is combined with the paper’s methods to simulate deeper circuits than previously thought possible.The scheme supplements main memory when quantum states are too large to fit there.
  • A.9 Leveraging secondary storage: Circuit partitioning and tensor slicing organize independent subcircuits and stored tensor slices across computational phases.The implementation processes slices sequentially and transfers updated slices to secondary storage.
  • A.9 Leveraging secondary storage: Boundary-qubit slicing exploits periods of limited interaction in 7 × 7 random circuits to apply over 30 gate layers without additional entanglement indices.The strategy slices a boundary row or column and simulates the remaining circuit with a memory-sized tensor.
  • A.9 Leveraging secondary storage: Estimated total runtimes combine computation, communication, and secondary-storage access for depth-55 and depth-83 7 × 7 circuits.The estimates use computation and communication results alongside secondary-storage capacity and transfer assumptions.
  • A.9 Leveraging secondary storage: Secondary-storage transfer times do not dominate the overall estimates, supporting secondary storage as a viable basis for arbitrary-depth simulation.The conclusion applies when quantum states are too large to fit in main memory alone.
  • A.9 Leveraging secondary storage: If partitioning selects too many global qubits, slices may become too small for efficient secondary-storage transfer.A proposed remedy is to impose a threshold on global qubits, or equivalently a minimum number of local qubits.

A.10 On the graph representation of two-qubit gates

The paper uses a hypergraph tensor-network representation in which shared index labels define hyperedges, changing the resulting line graph relative to a wire-segment representation. This representation can yield more efficient circuit graph decompositions, particularly for diagonal gates.

  • A.10 On the graph representation of two-qubit gates: The paper’s hypergraph representation uses one hyperedge per distinct index label, whereas the traditional representation uses one per wire segment.For the example circuit, this produces four hyperedges instead of eight.
  • A.10 On the graph representation of two-qubit gates: The different hyperedge structure changes the line graph and avoids the 4-clique produced by the traditional tensor-network representation.The line graph connects vertices whose corresponding hyperedges intersect.
  • A.10 On the graph representation of two-qubit gates: The representation difference arises for two-qubit diagonal gates and motivates transforming CX gates into CZ gates and Hadamards when advantageous.Diagonal CZ gates receive more efficient treatment in the paper’s representation.
Loading 1710.05867v4…