PaperlayerView exact revision on arXiv

Source-linked AI summary

Classical Simulation of Intermediate-Size Quantum Circuits

Jianxin Chen, Fang Zhang, Cupjin Huang, Michael Newman, Yaoyun Shi

arXiv:1805.01450v2quant-ph

TL;DR

Classical simulation is increasingly challenged by larger quantum systems, even as it remains important for testing processors and assessing quantum supremacy. This paper adapts simulation to cluster computing and reports successful simulations of large random circuits, suggesting realistic noisy circuits may be classically simulable.

  • Problem

    As quantum systems grow, classical simulation faces memory demands, while simulation remains useful for testing processors and locating the quantum-supremacy boundary.

    Source: §I · p. 1

  • Method

    The paper adapts variable elimination for cluster computing and divides amplitude evaluation into subtasks by fixing variable values.

    Source: §II · p. 2, §2 · p. 6

  • Results

    The simulator handled circuits up to 12 × 12 × 27, giving evidence that noisy random circuits with realistic physical parameters may be simulated classically.

    Source: §VI · pp. 10–11

  • Takeaways & Limitations

    The authors suggest new approaches or error correction may be necessary to demonstrate quantum supremacy with random circuit sampling.

    Source: §II · p. 3, §VI · p. 11

    The implementation is constrained by numpy's einsum limit of 32 subscripts, set by NPY_MAXDIMS.

    Source: §VI · p. 11

Abstract

from arXiv · show

We introduce a distributed classical simulation algorithm for general quantum circuits, and present numerical results for calculating the output probabilities of universal random circuits. We find that we can simulate more qubits to greater depth than previously reported using the cluster supported by the Data Infrastructure and Search Technology Division of the Alibaba Group. For example, computing a single amplitude of an $8\times 8$ qubit circuit with depth $40$ was previously beyond the reach of supercomputers. Our algorithm can compute this within $2$ minutes using a small portion ($\approx$ 14% of the nodes) of the cluster. Furthermore, by successfully simulating quantum supremacy circuits of size $9\times 9\times 40$, $10\times 10\times 35 $, $11\times 11\times 31$, and $12\times 12\times 27 $, we give evidence that noisy random circuits with realistic physical parameters may be simulated classically. This suggests that either harder circuits or error-correction may be vital for achieving quantum supremacy from random circuit sampling.

I. INTRODUCTION

The introduction frames classical simulation as both a tool for checking quantum processors and a way to locate the quantum-supremacy boundary. It surveys whole-state and single-amplitude approaches alongside prior simulation results.

I. INTRODUCTION

  • Classical simulation can help test quantum processors, characterize noise, develop error correction, verify quantum systems, and probe the boundary of quantum supremacy.The introduction describes quantum supremacy as the point beyond which quantum systems exceed the limits of classical simulation.Source: §I · p. 1
  • Amplitude-wise simulation either stores the full state vector or computes the amplitude for a selected bit string.The introduction notes that full-state storage makes memory a major issue.Source: §I · p. 1
  • By 2017, quantum-supremacy circuits with 45 qubits had been simulated using 0.5 petabytes of memory and 8,192 nodes.Earlier work also simulated 7 × 7 grids at depth 39 on Sunway TaihuLight.Source: §I · pp. 1–2
  • The paper situates its amplitude-focused approach alongside tensor-network contraction and a graphical-model method that uses diagonal gates.Prior work using the graphical model simulated 5 × 9 qubits at depth 40 and 7 × 8 circuits at depth 30 on one workstation.Source: §I · p. 2

II. OUR CONTRIBUTIONS

The paper adapts graphical-model variable elimination for cluster simulation and parallelizes costly parts of the computation. It applies the simulator to random circuits, reporting evidence that realistic noisy circuits may be classically simulated.

II. OUR CONTRIBUTIONS

  • The simulator computes a single amplitude for arbitrary circuits and is tested on circuits from a restricted class, building on graphical-model variable elimination.The paper describes its simulation technique as based on Google's line-graph variable-elimination model.Source: §II · p. 2
  • The cluster-oriented adaptation addresses full-state storage and expensive inter-node communication, while tensor-network complexity grows exponentially with treewidth.Storing the full amplitude of 50 qubits in double precision requires 16 petabytes; the Alibaba cluster has 10,000 computers and costly inter-node communication.Source: §II · p. 2
  • Figure 1 reports 80th-percentile runtime across 1,000 random circuits by depth and grid size; the largest tested depths for 10 × 10 to 12 × 12 grids are not algorithm limits.The runtime axis is logarithmic.Source: Figure 1 · p. 3
  • The algorithm divides the task into subtasks and uses QuickBB treewidth estimates to approximate their running times.QuickBB generates the elimination ordering; the reported 60-second estimation limit may be insufficient for larger-depth circuits.Source: §II · p. 3, Figure 1 · p. 3
  • Parallelizing over values of costly nodes can remove them from the graph and simplify its evaluation across a cluster.The paper says this balances sequential and parallel techniques to optimize circuit evaluation.Source: §II · pp. 2–3
  • The authors give evidence that low-depth random-circuit sampling may not achieve quantum supremacy even at idealized but plausible target gate fidelities.They suggest new approaches or error correction may be necessary.Source: §II · p. 3

III. THE ALGORITHM

The simulator uses an undirected graphical model as a tensor-network contraction variant that exploits diagonal gates. The section identifies treewidth reduction as central to controlling time and space complexity.

III. THE ALGORITHM

  • The simulator uses the complex undirected graphical model from [8], a variant of Markov and Shi tensor-network contraction that also exploits diagonal gates.Its parallelization scheme is designed to reduce treewidth, the dominant factor in time and space complexity.Source: §III · p. 4

A. Undirected Graphical Model

The circuit amplitude is expressed as a sum over intermediate bit-string indices, which can be represented as an undirected graph. Diagonal gates simplify that graph by imposing equalities between indices.

A. Undirected Graphical Model

  • The amplitude of a chosen output bit string is expanded across the circuit's clock-cycle matrices and summed over intermediate indices.The example circuit has four qubits and depth 8.Source: A. Undirected Graphical Model · p. 4
  • Each intermediate bit-string index becomes a graph vertex, with an edge between two vertices when an operator acts on both.A labeling of the vertices by 0 or 1 corresponds to a term in the Feynman path integral.Source: A. Undirected Graphical Model · p. 5
  • Diagonal gates merge graph nodes when their terms require equal labels, reducing the number of terms in the amplitude sum.The example uses diagonal T and CZ gates to impose index equalities.Source: A. Undirected Graphical Model · pp. 4–5
  • Figure 3 pairs single- and two-qubit diagonal and non-diagonal gates with their graphical gadgets.The graphical model uses these gadgets to represent circuit operations.Source: Figure 3 · p. 5, A. Undirected Graphical Model · p. 5

1. Variable elimination

The base algorithm evaluates the amplitude by eliminating graph variables one at a time. Each elimination contracts the tensors involving that variable and updates the graph.

1. Variable elimination

  • Eliminating a variable combines its tensors, sums over that variable, and replaces the removed tensors with the resulting tensor.The graph is updated by connecting the eliminated vertex's neighbors and removing the vertex.Source: §1 · p. 6
  • After all variables are eliminated, the remaining rank-0 tensor is the circuit amplitude.The procedure repeats the elimination steps until no variables remain.Source: §1 · pp. 5–6
  • The tensor multiplication and summation steps form most of the computation and can be executed using numpy.einsum.The implementation combines small input tensors before evaluating large tensors.Source: §1 · p. 6
  • The estimated cost of an elimination ordering is the sum of the sizes of its resulting tensors, with each step's tensor size estimated as 2^deg(v).High-rank tensors usually dominate the time cost of a step.Source: §1 · p. 6

2. Parallelization by fixing the values of variables

The algorithm parallelizes amplitude evaluation by fixing selected variable values, dividing the graph evaluation into independent subtasks. It uses a greedy cost-based strategy to choose variables because fixing alone causes exponential growth in evaluations.

2. Parallelization by fixing the values of variables

  • Using only variable fixing is inefficient because each removed vertex doubles the number of recursive evaluations.The evaluation count grows exponentially with the number of removed vertices.Source: §2 · p. 6
  • Fixing t selected variables splits the evaluation into 2^t subtasks, which are evaluated with the base algorithm.Fixing a variable removes its vertex and edges without introducing a new tensor.Source: §2 · pp. 6–7
  • A greedy strategy selects vertices according to the estimated time cost of evaluating the graph after their removal.Different vertices can have widely different effects, including low-degree vertices that hold large graph regions together.Source: §2 · p. 7
  • For single-amplitude evaluation, fixing all final qubit values to the output string removes their corresponding vertices for free.For the circuits considered, this optimization considerably simplifies the initial graph.Source: §2 · p. 7

3. The variable elimination ordering

Variable-elimination ordering affects both the base algorithm's time complexity and the choice of vertices to remove. The algorithm uses QuickBB before and after vertex removal despite its runtime cost.

3. The variable elimination ordering

  • The elimination ordering can change the base algorithm's time complexity and the choice of vertices removed before it runs.The removal choice depends on estimated graph-evaluation cost.Source: §3 · p. 7
  • QuickBB usually improves both maximum tensor rank and estimated time cost compared with vertical ordering.An initial QuickBB ordering also makes greedy vertex removal more efficient at reducing estimated cost.Source: §3 · p. 7
  • Because QuickBB is too slow to run for every cost estimate, it is run once before vertex removal and again afterward.The first ordering guides vertex removal; the second provides an ordering for evaluating the reduced graph.Source: §3 · p. 7

IV. NUMERICAL RESULTS

The numerical tests use supremacy circuits built from alternating CZ layouts and run them on the Alibaba cluster. Across 10 × 10 circuits at depths 34 and 35, dividing work into more subtasks improves success probability until processor capacity is reached, after which improvement requires longer runtimes.

IV. NUMERICAL RESULTS

  • The tests use supremacy circuits formed by alternating CZ configurations and randomly placing Y and T gates under specified placement restrictions.The tests use the circuit family proposed in.Source: §IV · pp. 7–8
  • In the Alibaba test, researchers requested 131,072 Docker-container nodes with 8 GB each; for undirected graphs with treewidth below 28, each node had enough memory for its subtask.For larger circuits, subtasks exceeding 8 GB were further divided until each fit within a node’s memory.Source: §IV · p. 8
  • The simulator is tested on 1,000 random circuits per size and depth, with the 80th-percentile runtime reported when at least 80% succeed.Each circuit is tested on the 131,072-node cluster.Source: §IV · p. 8
  • More subtasks improve success probability for 10 × 10 circuits at depths 34 and 35 until processor capacity is reached; further gains require longer runtimes.Figure 8 plots runtime against success probability for different subtask counts.Source: Figure 8 · p. 9

V. APPLICATION TO RANDOM CIRCUIT SAMPLING

The paper estimates circuit fidelity under a digital error model and compares simulator runtimes with the gate fidelities needed for a 5% circuit fidelity. Under its assumptions, the simulator’s bounds lie above the random-circuit supremacy threshold for 99.5% two-qubit gate fidelity, though the reported runtimes are for single amplitudes.

V. APPLICATION TO RANDOM CIRCUIT SAMPLING

  • Circuit fidelity is coarsely estimated as α ≈ exp(−ϵ1 × g1 − ϵ2 × g2 − ϵinit × N − ϵmes × N), assuming ϵ2 = ϵinit = ϵmes = ϵ and ϵ1 = ϵ/10.The error rates represent single- and two-qubit gates, initialization, and measurement; g1 and g2 count single- and two-qubit gates, and N is the qubit count.Source: §V · p. 9
  • At 99.5% two-qubit gate fidelity, simulator bounds below two hours lie above the supremacy threshold for a 5% circuit fidelity.Figure 9 plots runtime against circuit size and depth over contours of required two-qubit gate fidelity; each black circle represents the 80th-percentile runtime over 1,000 samples.Source: §V · p. 10, Figure 9 · p. 10
  • The reported runtimes cover single-amplitude simulation, while generating a full distribution may require significant additional overhead for many amplitudes and sufficient trials.The authors identify generating a large slice of amplitudes as a future direction that could improve robustness.Source: §V · p. 10

VI. DISCUSSION

The discussion reports simulations spanning several circuit width–depth combinations and argues that realistic noisy random circuits may be classically simulable. It also identifies implementation constraints and notes that circuit fidelity may not capture every form of quantum power.

VI. DISCUSSION

  • On an Alibaba Group cluster, the study simulated quantum-supremacy circuits spanning sizes 6 × 6 × 68 to 12 × 12 × 27, using 131072 processors and 1 petabyte of memory.Source: §VI · pp. 10–11
  • The authors argue that realistic-parameter noisy random circuits may be classically simulated, suggesting harder circuits or error correction may be needed for quantum supremacy.They also note alternative proposals for demonstrating quantum supremacy [22].Source: §VI · p. 11
  • If the task is split into more subtasks than available processes, sequential execution on each processor reduces parallelization gains..Source: §VI · p. 11
  • QuickBB is very slow for larger circuits; rerunning it between vertex removals can simulate 7 × 7 × 60 circuits, but takes appreciably longer.The authors identify faster elimination-ordering algorithms as a possible way to simplify subtasks at low cost.Source: §VI · p. 11
  • Circuit fidelity may not capture all device quality: some circuits with poor fidelity could still display quantum power under another metric.The discussion frames this as a caveat to using circuit fidelity as the quality measure.Source: §VI · p. 11
Loading 1805.01450v2…