PaperlayerView exact revision on arXiv

Source-linked AI summary

Tensor Network Quantum Simulator With Step-Dependent Parallelization

Danylo Lykov, Roman Schutski, Alexey Galda, Valerii Vinokur, Yuri Alexeev

arXiv:2012.02430v2quant-ph

TL;DR

Classical simulation of large QAOA circuits helps explore the computing limits relevant to demonstrating quantum advantage. The paper combines tensor-network contraction with step-dependent slicing and ordering algorithms, and reports simulations of 210-qubit circuits with 1,785 gates on 1,024 Theta nodes.

  • Problem

    The paper explores the limits of classical computing for simulating large QAOA circuits to help define the quantum-computer size needed to demonstrate an advantage on useful problems.

    Source: §I · p. 1

  • Method

    The authors use tensor-network circuit representations with novel step-dependent slicing and ordering algorithms to reduce memory footprint and find contraction orders.

    Source: §I · p. 1, B. Graph model of tensor expression · p. 3, §IX · p. 9

  • Results

    The simulator ran QAOA circuits up to 210 qubits, 1,785 gates, on 1,024 Theta nodes with 213 TB of memory, which the authors report as the largest QAOA circuit simulations to date.

    Source: §IX · pp. 9–10

  • Takeaways & Limitations

    The contraction order can be reused across QAOA simulations with different circuit parameters, supporting studies of angle transferability, angle optimality, and symmetry.

    Source: §IX · p. 10

Abstract

from arXiv · show

In this work, we present a new large-scale quantum circuit simulator. It is based on the tensor network contraction technique to represent quantum circuits. We propose a novel parallelization algorithm based on \stepslice . In this paper, we push the requirement on the size of a quantum computer that will be needed to demonstrate the advantage of quantum computation with Quantum Approximate Optimization Algorithm (QAOA). We computed 210 qubit QAOA circuits with 1,785 gates on 1,024 nodes of the the Cray XC 40 supercomputer Theta. To the best of our knowledge, this constitutes the largest QAOA quantum circuit simulations reported to this date.

I. INTRODUCTION

The introduction motivates classical circuit simulation as a tool for studying quantum algorithms and presents QTensor and new slicing and ordering algorithms for larger QAOA simulations. The related work situates tensor-network contraction among classical simulation approaches.

I. INTRODUCTION

  • Classical circuit simulators help researchers evaluate quantum-algorithm complexity and develop and validate circuit designs.QAOA is presented as a candidate for demonstrating quantum advantage on useful problems, including hard combinatorial problems such as MaxCut.Source: §I · p. 1

II. RELATED WORK

  • Classical circuit simulators include amplitude-vector evolution –, Feynman paths, linear algebra open-system simulation, decision diagrams, and tensor-network contraction –[10].Prior work describes tensor networks as particularly suitable for short circuits and QAOA [11].Source: §I · p. 1

I. INTRODUCTION

  • QTensor is an Argonne-developed tensor-network simulator for generic quantum circuits, including QAOA, with automatic differentiation with respect to gate parameters.The text notes its usefulness for quantum machine learning and QAOA parameter optimization.Source: §I · p. 1
  • The slicing and ordering algorithms increase simulated circuit size from 120 to 210 qubits on a distributed system while maintaining the same time-to-solution.The paper frames this work as exploring the classical-computing limits relevant to demonstrating QAOA’s potential quantum advantage.Source: §I · p. 1

II. RELATED WORK

  • Line-graph tensor-network methods connect circuit simulation to probabilistic graphical models and treewidth, while supporting straightforward parallelization [17], [19].Their limited usability for simulating amplitude subtensors was addressed in later work.Source: §II · p. 2

III. METHODOLOGY

The methodology introduces QAOA’s objective and layered ansatz, then explains why targeted amplitude sampling matters for simulation. It distinguishes ansatz-state simulation from expectation-value calculations that can use lightcone optimization.

A. QAOA introduction

  • QAOA seeks an N-bit string z maximizing a classical objective C(z), with the goal of achieving a desired approximation ratio.For MaxCut, the objective is reformulated using quantum spins to form the problem Hamiltonian HC.Source: A. QAOA introduction · p. 2
  • The QAOA ansatz evolves an initialized state using problem and mixing Hamiltonians for p layers, producing a variational wavefunction parameterized by β and γ.The parameters comprise 2p variational values.Source: A. QAOA introduction · p. 2
  • Sampling the QAOA state’s 2^N measurement outcomes is expensive, so the paper focuses on computing targeted amplitudes rather than all amplitudes.The text identifies effective sampling of selected amplitudes as an advantage for a simulator such as QTensor.Source: A. QAOA introduction · p. 2
  • Lightcone optimization makes expectation-value complexity depend on iteration count p rather than graph size, but does not apply to the ansatz-state simulations studied here.The text relates QAOA directly to adiabatic quantum computing, describing QAOA as a Trotterized adiabatic algorithm and the approaches as the same for large p.Source: A. QAOA introduction · p. 2

B. Description of quantum circuits

The section frames QAOA simulation as a tensor-network contraction problem, representing circuits through tensors and graph indices. It explains how elimination order controls contraction cost and how graph structure informs that cost.

B. Description of quantum circuits

  • A single-depth QAOA circuit is converted into a tensor network, and one amplitude of the ansatz state is simulated as a benchmark used to compute the energy function.The full energy computation corresponds to a single amplitude of a duplicated tensor expression with additional cost-operator gates.Source: B. Description of quantum circuits · p. 3

IV. OVERVIEW OF SIMULATION ALGORITHM

  • The overview introduces tensor-network contraction as the simulation algorithm and points to prior descriptions of the method.The cited treatments include Boixo et al. [17], Detcher et al. [23], and Marsland et al..Source: §IV · p. 3

A. Quantum circuit as tensor expression

B. Graph model of tensor expression

  • In the line-graph representation, vertices denote unique tensor indices and cliques denote tensors, with smaller cliques representing tensors diagonal along some axes.Fig. 3 labels output-statevector indices 0–3 and input-statevector indices 32–25; self-loop edges are omitted, including for diagonal Z2γ.Source: B. Graph model of tensor expression · p. 3, Figure 3 · p. 3
  • Sequentially eliminating an index removes its vertex and adds a clique among its neighbors; the resulting tensor’s memory and time cost grows exponentially with the neighbor count.The cost is governed by the maximum neighbor count during elimination, called the contraction width; Fig. 4 shows per-vertex contraction cost and neighbor counts.Source: B. Graph model of tensor expression · p. 4, Figure 4 · p. 4
  • Minimizing the maximum neighbor count is connected to tree decomposition, and finding a tree decomposition is NP-hard for general graphs.The expression graph’s treewidth equals the contraction width minus one.Source: B. Graph model of tensor expression · p. 4

V. SIMULATION OF A SINGLE AMPLITUDE

The section presents single-amplitude simulation as a simple benchmark for circuit complexity and simulator performance. It starts from the N-qubit zero state and evaluates the probability of measuring that same state.

V. SIMULATION OF A SINGLE AMPLITUDE

  • Single-amplitude simulation is used as a simple benchmark for evaluating quantum-circuit complexity and simulation performance.The calculation starts with the N-qubit zero state and evaluates the probability of measuring that state again.Source: §V · p. 4
  • The benchmark begins with the N-qubit zero state and calculates the probability of measuring the same state.Source: §V · p. 4
  • The section uses one amplitude as a simple measure for comparing circuit complexity and simulator performance.Source: §V · p. 4

A. Ordering algorithm

Efficient tensor-network contraction depends on finding a good ordering, balancing width improvement against the ordering algorithm’s runtime. The section compares greedy, randomized, and heuristic approaches, then describes how slicing is parallelized across nodes and threads.

A. Ordering algorithm

  • Linear improvement in contraction width yields exponential speedup, making ordering a dominant part of efficient tensor-network contraction.The greedy algorithm contracts the lowest-degree vertex and serves as a baseline because it gives reasonable results within a short runtime budget.Source: A. Ordering algorithm · p. 4, 1) Greedy algorithm · p. 4

2) Randomized greedy algorithm:

  • rgreedy assigns vertex-selection probabilities using a Boltzmann distribution, repeats contraction q times, and keeps the best ordering.Its randomized approach follows the observation that small changes in contraction order can strongly affect width.Source: 2) Randomized greedy algorithm · pp. 4–5

3) Heuristic solvers:

  • Ordering heuristics use global information, while the choice among ordering algorithms balances width improvement against runtime.The section identifies branch-and-bound and dynamic-programming heuristics as alternatives to greedy approaches.Source: A. Ordering algorithm · p. 4, 3) Heuristic solvers · p. 5
  • QuickBB provides no significant contraction-width improvement over greedy algorithms while running much more slowly.Tamaki’s heuristic solver [35] provides good results, with noticeable improvements when run for tens of seconds to minutes; it can return a solution whenever stopped.Source: 3) Heuristic solvers · p. 5

VI. PARALLELIZATION ALGORITHM

  • MPI distributes slices of a partially contracted expression across nodes, while threads parallelize tensor operations within a node using a shared result tensor.The two approaches slice tensor indices; splitting result indices avoids per-worker result copies but is less flexible for complex expressions.Source: §VI · p. 5

A. Description of hardware and software

The benchmarks use Intel Xeon Phi systems, including Theta, while the single-node method addresses memory and thread-scaling constraints by sharing result tensors and adapting thread count to task size.

A. Description of hardware and software

  • Theta is a 12-petaflop Cray XC40 with 4,392 Intel Xeon Phi 7230 processors; each processor has 64 cores.The processors run at 1.3 GHz and have 16 GB MCDRAM plus 192 GB DDR4 memory.Source: A. Description of hardware and software · p. 5

B. Single-node parallelization

  • Quantum-circuit simulation is memory-bound because storing intermediate results is its main bottleneck, and MPI-only replication increases memory use with rank count.The largest data object is a contraction-result tensor, whose storage requirement grows exponentially with its size.Source: B. Single-node parallelization · p. 6
  • The single-node method shares the resulting tensor among threads and adapts thread count to task size to limit inefficiency on small tensors.It slices input and output tensors over selected indices, with thread IDs in binary selecting slice values.Source: B. Single-node parallelization · p. 6
  • For contraction, the method slices the first t shared indices so threads receive consistent result-tensor blocks, reducing memory-access time.The thread count is selected from experiments estimating overhead; the resulting tensor’s rank is the stated variable in the empirical formula.Source: B. Single-node parallelization · p. 6

C. Multinode parallelization

Multinode parallelization slices a partially contracted expression across nodes, selecting a contraction step and vertices intended to reduce contraction width. The authors report substantial speedups from slicing and describe the approach as previously undescribed in the field.

C. Multinode parallelization

  • Each node evaluates a version of the expression at selected index values, and slicing can split an expression into 2^n parts with lower graph connectivity.The authors report that this late-parallelization approach had not previously been described in the field.Source: C. Multinode parallelization · pp. 6–7
  • Using only two computational nodes can yield speedups of an order of 25, depending on the expression.Source: C. Multinode parallelization · p. 6
  • The method searches steps before the peak neighbor count, removes high-neighbor vertices, and chooses the step with the smallest resulting contraction width.The selected step is used to slice the partially contracted expression; the authors state that the new width can be lower than the original by more than the number of removed vertices.Source: C. Multinode parallelization · p. 7
  • After serially contracting the first s buckets, the algorithm slices n high-neighbor vertices, reorders the sliced expression, and contracts the resulting buckets in parallel.MPI rank bits determine slice values, and node results are summed at the end.Source: C. Multinode parallelization · p. 7

D. Step-dependent slicing

Step-dependent slicing chooses a point in contraction at which slicing yields the best contraction width, exploiting the fact that partially contracted networks can also be sliced. The reported width reduction translates into an eightfold simulation speedup.

D. Step-dependent slicing

  • For QAOA, most contraction steps are cheap and graph connectivity is low, motivating the step-dependent slicing strategy.The algorithm’s blue-box operations are evaluated for each graph node and are the main time contributions.Source: D. Step-dependent slicing · p. 7, Figure 8 · p. 9
  • Partially contracted tensor networks remain sliceable, so the algorithm can choose both a slicing index and its contraction step.The authors present step-dependent slicing as a previously undescribed approach in the field.Source: D. Step-dependent slicing · pp. 7, 9
  • The algorithm evaluates slicing before the peak-width step, removes high-degree vertices, and selects the step producing the best contraction width.It finds an ordering for the full graph, then reruns the ordering after removing r vertices at each candidate step.Source: D. Step-dependent slicing · p. 7
  • A contraction-width reduction of 3 yields an 8x simulation speedup with n = 1 sliced index.Source: D. Step-dependent slicing · p. 9

VII. SIMULATION OF SEVERAL AMPLITUDES

The paper extends tensor-network simulation to batches of amplitudes by leaving selected indices uncontracted. This can provide multiple amplitudes at the cost of a single amplitude when the added clique does not increase contraction width.

VII. SIMULATION OF SEVERAL AMPLITUDES

  • This batch approach addresses frugal rejection sampling, which requires calculating several amplitudes to obtain samples.Source: §VII · p. 9
  • Leaving out selected tensor-network indices produces a tensor indexed by those indices, rather than a scalar amplitude.Source: §VII · p. 9
  • When the added clique has size a below contraction width c, the method can simulate 2^a amplitudes for the cost of one.Source: §VII · p. 9
  • Figure 9 presents contraction width for simulating batches of amplitudes across different values of a, ordering algorithms, and graph sizes.Source: §VII · p. 9

VIII. RESULTS

For the 210-qubit test circuit, step-dependent slicing substantially reduces memory use relative to serial simulation. The results also show that contraction width varies by slicing step and that using more nodes can further reduce simulation time.

VIII. RESULTS

  • Theta has 4,392 nodes, each with 64 Intel Xeon Phi cores and 208 GB RAM; aggregate memory is approximately 900,000 GB.Source: §VIII · p. 9
  • More than 35x less memory than serial simulation was used: 60% of 13 TB across 64 nodes for the 210-qubit circuit.Slicing removed six vertices and reduced contraction width from 44 to 32; the initial width-44 contraction was estimated to require at least 281 TB.Source: §VIII · p. 9
  • Up to 9 contraction-width units of variation across slicing steps correspond to a 512x cost difference; increasing n by one reduces the minimum width by one.Source: §VIII · p. 9
  • 4096x speedup was reported for 64 nodes; using 512 nodes reduced contraction width to 29 and simulation time 3x versus 64 nodes.Source: §VIII · p. 9
  • Simulation time for 64–1,024 nodes includes a 40-second serial phase, which accounts for 25–50% of total time depending on node count.Source: §VIII · p. 9

IX. CONCLUSIONS

The authors present step-dependent slicing and ordering methods for tensor-network circuit simulation, demonstrating them on QAOA circuits. On Theta, the approach reaches 210 qubits and 1,785 gates, which the authors describe as the largest QAOA simulations reported to date, to their knowledge.

IX. CONCLUSIONS

  • The approach simulated QAOA circuits up to 210 qubits and 1,785 gates on 1,024 Theta nodes with 213 TB of memory.Source: §IX · p. 9
  • Step-dependent slicing contracts part of the expression in advance to reduce memory use and the cost of finding an elimination order; ordering choices yielded speedups up to 512x.The demonstration used p = 1 QAOA ansatz circuits, though the authors state the algorithm also works for higher p.Source: §IX · p. 9
  • Prior tensor-network contraction simulated 120–140 qubits, rising to 175 with randomized greedy ordering; the paper reports 210 using step-dependent slicing.The largest density-matrix simulators known to the authors reached 100 [39] and 120 qubits.Source: §IX · pp. 9–10
  • The contraction order need only be generated once and can be reused for QAOA simulations with different circuit parameters.The authors connect this reuse to studies of angle transferability [41], angle optimality, and QAOA under symmetry [42].Source: §IX · p. 10
  • The authors report these as the largest QAOA circuit simulations to date, to their knowledge.Source: §IX · p. 10
Loading 2012.02430v2…