Source-linked AI summary
Classical Simulation of Quantum Supremacy Circuits
Cupjin Huang, Fang Zhang, Michael Newman, Junjie Cai, Xun Gao, Zhengxiong Tian, Junyin Wu, Haihong Xu, Huanjun Yu, Bo Yuan, Mario Szegedy, Yaoyun Shi, Jianxin Chen
TL;DR
Random quantum-circuit sampling is expected to be classically hard, but prior supremacy claims relied on classical runtime estimates that may improve. This work introduces stem-optimized tensor-network simulation, reducing estimated runtimes from thousands of years to days or minutes and narrowing the case for an unequivocal quantum-supremacy demonstration.
Problem
Random quantum-circuit sampling is expected to require exponentially growing classical simulation time, while quantum-supremacy claims depend on classical runtime estimates that may underestimate improved simulators.
Method
The authors develop a tensor-network simulator that identifies and optimizes a dominant contraction path, called the stem, in regular random-circuit tensor networks.
Results
The simulator reduces one-million-sample estimates for 20-cycle circuits from 10,000 years to under 20 days and three-million-sample estimates for 14-cycle circuits from 1.1 years to 264 seconds.
Takeaways & Limitations
These orders-of-magnitude reductions suggest that quantum-supremacy claims may require continued quantum-hardware development before an unequivocal first demonstration.
Takeaways & Limitations
The simulator currently has low FLOPS efficiency, and the authors identify further algorithmic and engineering improvements that could change its performance estimates.
Abstract
from arXiv · showhide
It is believed that random quantum circuits are difficult to simulate classically. These have been used to demonstrate quantum supremacy: the execution of a computational task on a quantum computer that is infeasible for any classical computer. The task underlying the assertion of quantum supremacy by Arute et al. (Nature, 574, 505--510 (2019)) was initially estimated to require Summit, the world's most powerful supercomputer today, approximately 10,000 years. The same task was performed on the Sycamore quantum processor in only 200 seconds. In this work, we present a tensor network-based classical simulation algorithm. Using a Summit-comparable cluster, we estimate that our simulator can perform this task in less than 20 days. On moderately-sized instances, we reduce the runtime from years to minutes, running several times faster than Sycamore itself. These estimates are based on explicit simulations of parallel subtasks, and leave no room for hidden costs. The simulator's key ingredient is identifying and optimizing the "stem" of the computation: a sequence of pairwise tensor contractions that dominates the computational cost. This orders-of-magnitude reduction in classical simulation time, together with proposals for further significant improvements, indicates that achieving quantum supremacy may require a period of continuing quantum hardware developments without an unequivocal first demonstration.
1 Introduction
Random-circuit sampling is used to probe quantum supremacy because classical simulation is expected to scale exponentially, but prior runtime estimates could underestimate classical progress. This work introduces a tensor-network simulator that substantially reduces those estimates through stem optimization and parallel subtasks.
- 1 Introduction: Random-circuit sampling is attractive for supremacy tests because quantum execution is straightforward while classical simulation is expected to grow exponentially with circuit size.
- 1 Introduction: The claimed supremacy of Sycamore depends partly on classical runtime estimates that may fall as simulators improve.
- 1.1 Results: Less than 20 days replaces the 10,000-year estimate for collecting one million 20-cycle samples at 0.2% fidelity, using Summit-comparable nodes.The subtasks were explicitly benchmarked in parallel, avoiding hidden full-scale simulation costs.
- 1.1 Results: 264 seconds replaces 1.1 years for collecting three million 14-cycle samples at 1% fidelity, twice as fast as Sycamore’s total execution time.
2 Sycamore Random Quantum Circuits
The simulated Sycamore circuits use repeated layers of random single-qubit and patterned two-qubit gates across increasing cycle depths. XEB measures how closely noisy-device outputs match the ideal Porter–Thomas distribution.
- 2 Sycamore Random Quantum Circuits: Each circuit has m cycles of single-qubit and two-qubit gate layers, followed by an extra single-qubit layer before computational-basis measurement.
- 2 Sycamore Random Quantum Circuits: Two-qubit pairings follow four patterns repeated as A, B, C, D, C, D, A, B across cycles.
- 2 Sycamore Random Quantum Circuits: The linear cross-entropy benchmarking fidelity is 2^n⟨p_I(x)⟩−1, with 0 for a uniform output distribution and 1 for the ideal distribution.
- 2 Sycamore Random Quantum Circuits: At 20 cycles, simplified Sycamore circuits achieved approximately 0.2% XEB, which numerical evidence suggested also characterized the target random circuits.
3 Classical Simulation with Tensor Networks
The paper represents quantum circuits as tensor networks and compares contraction strategies with different space–time tradeoffs. Its hybrid approach slices indices into parallel subtasks, while contraction-tree structure motivates efficient optimization.
- 3 Classical Simulation with Tensor Networks: A tensor network represents tensors as vertices linked by shared-index hyperedges, with network entries obtained by summing products over compatible paths.
- 3 Classical Simulation with Tensor Networks: Contraction trees typically contain a short path of expensive nodes called the stem, while inexpensive clusters form branches around it.
- 3 Classical Simulation with Tensor Networks: The Feynman method uses polynomial space but exponentially many steps in the number of hyperedges, making it infeasible for networks with 50–100 hyperedges.
- 3 Classical Simulation with Tensor Networks: The Schrödinger method sequentially contracts tensor pairs, but its space complexity grows exponentially with contraction width and can exceed one device’s memory.
- 3 Classical Simulation with Tensor Networks: The hybrid method fixes a subset of indices, producing independently parallelizable tensor-network contractions with lower space complexity per subtask.Choosing the indices and contraction sequence determines the resulting space–time tradeoff.
- 3 Classical Simulation with Tensor Networks: Finding an optimal contraction scheme is computationally hard, so the simulator combines prior and new algorithmic ideas to find an acceptable scheme efficiently.
4 Stem Optimization
The method targets the computationally intensive stem in contraction trees, combining hypergraph partitioning, local optimization, and dynamic slicing to obtain efficient contraction schemes.
- Stem structure: A typical contraction tree has a short, expensive stem where most computation occurs, plus inexpensive branches attached to it.The stem is a path of costly nodes in which a large tensor sequentially absorbs branch results.
- Hypergraph partitioning: The algorithm first uses recursive hypergraph partitioning to construct and optimize candidate contraction trees around the stem.Top-level multi-partitioning identifies major stem components, followed by recursive bipartitioning and parameter optimization.
- Local optimization: Local optimization rearranges selected connected subgraphs, especially stem subpaths, to reduce contraction cost without altering the rest of the tree.Brute-force optimization is feasible on small connected subgraphs and focuses on the computation-dominating stem.
- Dynamic slicing: Dynamic slicing selects hyperedges whose subtrees intersect the stem and enumerates them until each subtask fits available memory.Slicing is interleaved with local optimization and produces smaller subtasks that retain a usable contraction structure.
- Algorithm framework: The framework repeats partitioning, local optimization, and dynamic slicing to obtain a good contraction scheme.Figure 3 organizes these operations into an unsliced-order phase followed by space-reducing optimization and slicing.
5 Complexity of Random Quantum Circuit Sampling
The simulator is benchmarked on Sycamore random-circuit files across multiple cycle counts, using repeated contraction-order generation and comparisons with leading simulators.
- Benchmark setup: The benchmark uses publicly available Sycamore circuit files containing 12-, 14-, 16-, 18-, and 20-cycle instances.The files come from the data supplement to and were obtained from a public Dryad repository.
- Benchmark setup: Each circuit is run five times after contraction-order preprocessing, and the best generated order is selected.Preprocessing uses 50 CMA-ES iterations and 20, 20, and 50 local-optimization iterations before, between, and after slicing.
- Benchmark results: AC-QDP achieves more than five orders of magnitude speedup over the best classical algorithms in [7] and more than two orders over other state-of-the-art simulators.Its contraction cost is up to 10^6 times lower than qFlex and up to 10^3 times lower than Cotengra, despite lower FLOPS efficiency.
- Benchmark comparison: Figure 4 compares contraction cost, FLOPS efficiency, extrapolated runtime, and leading simulators using different amplitude-contraction modes.AC-QDP and qFlex compute batches of 64 amplitudes with open contraction, whereas Cotengra computes single amplitudes with closed contraction.
6 Discussion
The discussion argues that AC-QDP substantially lowers classical simulation costs while retaining room for major algorithmic and engineering improvements.
- Future improvements: Further refinements could reduce simulation costs by several orders of magnitude through better contraction orders, truncated gates, and improved hardware utilization.The current FLOPS efficiency is approximately 15%, and Tensor Cores were not used.
- Comparison caveat: Cotengra’s comparison may change because private communication indicated it also implements open tensor network contraction with potentially similar batch and single-amplitude costs.This caveat qualifies the comparison between contraction modes used in the benchmark.
- Simulation costs: Figure 4 and Table 1 present classical simulation costs for m-cycle random circuits with low XEB fidelities on a Summit-comparable cluster.Table 1 reports extrapolated AC-QDP benchmarks, with explicit single-sample runs for m = 12 and m = 14 on one V100.
- Implications: The discussion positions the simulator as a potential tool for advancing quantum information technologies and defining the quantum supremacy frontier.This conclusion follows the reported efficiency of the simulator and its role in estimating classical simulation costs.
A.1 Tensor network contraction
The section introduces notation for positive-integer index sets used in tensor-network descriptions.
- Notation: For d ∈ N+, [d] denotes the set {1, . . . , d}.
A.1.1 Tensors and tensor networks
Tensor networks represent computations as attributed multi-hypergraphs whose vertices carry tensors and whose hyperedges carry shared indices. Contracting the network sums products over index assignments, with qubit circuits modeled using bond dimension 2.
- Tensor networks: A tensor network is an attributed multi-hypergraph with open hyperedges, bond dimensions, ordered incident edges, and an associated tensor at each vertex.Each vertex tensor has one dimension for every incident hyperedge, determined by that hyperedge’s bond dimension.
- Tensor networks: An assignment to all hyperedges fixes tensor indices and produces a Feynman-path value by multiplying the corresponding tensor entries.The network value sums these path products subject to any fixed open-edge assignment.
- Tensor networks: Contraction computes the tensor-network value, producing an output tensor whose entries sum path values consistent with the open-edge assignment.The computational task is to solve for the value of T_H given H.
- Tensor networks: For qubit-circuit simulation, all bond dimensions can be taken as 2, and the example network contains 4 tensors and 5 hyperedges.Figure 5 illustrates this small tensor-network structure.
A.1.2 Contraction trees and tensor network slicing
Contraction trees evaluate tensor networks through sequential pairwise contractions, whose ordering determines time and space complexity. Slicing creates parallel subtasks and reduces memory requirements while preserving a common subnetwork structure.
- Contraction trees: A contraction tree replaces chosen pairs of vertices with single vertices until one tensor remains, while preserving outgoing connections.The final tensor is independent of contraction order, but the computational cost depends on that order.
- Contraction trees: A pairwise contraction step has time complexity 2^|E_AB| and space complexity 2^|E*_AB|, based on enumerating paths over the involved hyperedges.Repeating these steps yields a rooted binary contraction tree.
- Contraction trees: 16 + 16 + 8 = 40 total time complexity and 8 total space complexity in the illustrated contraction tree.Time sums stepwise costs, whereas space takes the maximum stepwise space cost; hyperedge counts encode these quantities.
- Slicing: Slicing selected hyperedges enumerates assignments to generate subtasks with identical subhypergraph structure, enabling parallelism and reducing space complexity.The full value is recovered by summing the values of all resulting subtensor networks.
- Slicing: A slicing-incorporated scheme pairs sliced edges with a contraction tree on the remaining hypergraph, while its contraction width equals the tree’s width.For an Nvidia V100 with 16 GiB, width at most 29 is usually sufficient under single precision.
A.2 Optimization methods
The optimization approach targets a dominant stem in typical contraction trees. Identifying and optimizing this costly contraction path is presented as the basis for reducing simulation cost.
- Optimization methods: Typical contraction trees contain a stem of overwhelming cost with short branches attached, motivating heuristics that optimize the stem.The stem is a path of contractions that dominates the overall computation.
A.2.1 Stems and branches
The simulator identifies a high-cost stem in contraction trees and optimizes it separately from lower-cost branches. Hypergraph decompositions, local restructuring, slicing, and GPU-aware execution reduce contraction costs while trading space, time, and runtime overhead.
- Stems and branches: The stem is a high-weight path containing most contraction cost, while smaller branch clusters attach to it.Stem nodes have similar weights, whereas branch nodes typically have substantially smaller weights.
- Stem construction: Hypergraph multipartite decomposition locates major stem components, then recursive bipartite decomposition peels away branches until the stem ends.The implementation fixes the stopping threshold N to 25 and optimizes decomposition parameters with CMA-ES.
- Local optimization: Local optimization replaces small connected stem subgraphs with brute-force-optimal internal connections, repeating until improvements cease or an iteration limit is reached.The method focuses optimization where most computation occurs while requiring sufficiently small subgraphs for feasibility.
- Slicing: Greedy hyperedge slicing reduces memory demand, while intervening local optimization limits increases in total time complexity.Slicing is applied when the contraction tree does not fit in memory.
- GPU execution: GPU-specific pre-computation and branch merging reduce transfer or matrix-multiplication overhead despite potentially increasing FLOPs.Branches can be computed on CPUs and shared across subtasks, while merging branches absorbs larger tensors at once.
- Experimental evaluation: Explicit cluster experiments find scheduling and communication costs negligible, with 200,000 amplitudes producing a Porter–Thomas-like distribution.The reported calculation corresponds to approximately 1.89 days under the stated FLOP and sampling assumptions.