Source-linked AI summary
Solving the sampling problem of the Sycamore quantum circuits
Feng Pan, Keyang Chen, Pan Zhang
TL;DR
The paper addresses how to generate many independent samples from Sycamore’s output distribution at a target fidelity, a task used in quantum-supremacy demonstrations. It introduces a sparse-state tensor-network method that computes selected amplitudes in one contraction and reports one million samples for a 53-qubit, 20-cycle circuit with estimated fidelity about 0.0037.
Problem
Generating independent Sycamore samples at target fidelity remains a classical simulation challenge because existing approaches require large storage or repeated contractions.
Method
The method projects onto selected bitstrings and contracts the resulting sparse-state tensor network once, using grouped bitstrings and slicing to control complexity.
Results
Estimated fidelity F_estimate ≈ 0.0037 was achieved for one million samples from the 53-qubit, 20-cycle Sycamore circuit.
Takeaways & Limitations
The sparse-state approach makes the targeted uncorrelated Sycamore sampling task practically executable with classical tensor-network contraction.
Takeaways & Limitations
The sampling construction relies on the final-state distribution following the Porter–Thomas distribution for near-perfect sampling with l = 64.
Abstract
from arXiv · showhide
We study the problem of generating independent samples from the output distribution of Google's Sycamore quantum circuits with a target fidelity, which is believed to be beyond the reach of classical supercomputers and has been used to demonstrate quantum supremacy. We propose a new method to classically solve this problem by contracting the corresponding tensor network just once, and is massively more efficient than existing methods in obtaining a large number of uncorrelated samples with a target fidelity. For the Sycamore quantum supremacy circuit with $53$ qubits and $20$ cycles, we have generated one million uncorrelated bitstrings $\{\mathbf s\}$ which are sampled from a distribution $\hat P(\mathbf s)=|\hat ψ(\mathbf s)|^2$, where the approximate state $\hat ψ$ has fidelity $F\approx 0.0037$. The whole computation has cost about $15$ hours on a computational cluster with $512$ GPUs. The obtained one million samples, the contraction code and contraction order is made public. If our algorithm could be implemented with high efficiency on a modern supercomputer with ExaFLOPS performance, we estimate that ideally, the simulation would cost a few dozens of seconds, which is faster than Google's quantum hardware.
The sparse-state method
The sparse-state method computes amplitudes for selected bitstrings in one tensor-network contraction, avoiding the unnecessary entries required by full, single-amplitude, or repeated batch simulation.
- The sparse-state method: The method chooses L random groups, each containing l bitstrings formed by fixing 47 bits and leaving 6 qubits open, yielding 64 configurations per group.For the illustrated construction, each group contains 2^6 = 64 bitstrings.
- The sparse-state method: Full-amplitude simulation requires 2^n space, single-amplitude simulation repeats contraction per bitstring, and batch simulation still repeats contractions for uncorrelated samples.These strategies trade storage for repeated or expensive contractions.
- The sparse-state method: One contraction computes amplitudes for selected bitstrings by projecting onto their basis vectors, forming a sparse state of the Hilbert space.The sparse-state boundary guides contraction toward requested entries only.
- The sparse-state method: During contraction, only entries corresponding to target-bitstring configurations are retained when merged dimensions are formed.This avoids calculating unrequested bitstrings and reduces contraction complexity, especially memory usage.
Details about the numerical simulations
The numerical objective is to generate 2^20 independent samples with XEB above Google’s 0.002 value using the one-contraction sparse-state scheme.
- Details about the numerical simulations: The simulation targets 2^20 independent samples with XEB greater than 0.002.The section frames this as the practical sampling problem addressed by the sparse-state contraction.
- Details about the numerical simulations: The sparse-state scheme combines multiple uncorrelated bitstring-amplitude calculations into one tensor-network contraction.The section identifies this reduction in contraction complexity as central to the practical simulation.
Bitstrings choice and sampling details
Sampling uses a large set of uniformly selected bitstrings, organized into groups so that one sample can be drawn from each group’s approximate probability distribution.
- Bitstrings choice and sampling details: At least one million bitstring samples are required to pass the XEB test with XEB greater than 0.002.This requirement determines the sampling scale for the simulation.
- Bitstrings choice and sampling details: For importance sampling, L groups of l bitstrings are used to sample L outputs from the approximate distribution.The cited procedure contrasts this grouped approach with requiring all l × L bitstrings to be distinct and uniformly random.
- Bitstrings choice and sampling details: The simulation chooses l = 2^6 and L = 2^20, obtaining 2^26 bitstring amplitudes in one sparse-state contraction.The circuit instance is the 53-qubit, 20-cycle Sycamore circuit with sequence ABCDCDAB.
Slicing and contraction order
The simulation trades fidelity for tractable contraction by slicing the tensor network, summing only a fraction of orthogonal sub-tasks while choosing contraction order and local slices to fit GPU memory.
- Slicing and contraction order: The method deliberately chooses fidelity reduction as the trade-off rather than reducing the number of generated bitstrings.This choice is presented as the strategy used in the simulation.
- Slicing and contraction order: Slicing fixes selected tensor indices, turning the original contraction into sub-task contractions whose results are summed.This reduces space complexity so the contraction can fit computational devices.
- Slicing and contraction order: Because sliced copies are orthogonal for the relevant random circuits, each contributes equally to fidelity and a fraction of sub-tasks can estimate the full result.The cited passage attributes this property to circuits using fSim gates.
- Slicing and contraction order: Summing 1/2^8 of the slicing sub-tasks yields an estimated sample fidelity F_estimate = F_a/2^8 ≈ 0.0037.The approach also removes four two-qubit gates and may apply rank-one approximations to companion edges.
- Slicing and contraction order: The tensor network is divided into head and tail parts, with interface and local slicing edges selected to keep intermediate contractions within GPU memory.For 53-qubit circuits, the interface has at least 53 indices and 24 are sliced for a 32 GB GPU.
Computational cost
The contraction data cover a 53-qubit, 20-cycle Sycamore simulation and account for fidelity-preserving and fidelity-reducing companion-edge choices.
- Table I reports detailed contraction data for Sycamore circuits with n = 53 qubits and m = 20 cycles.
- 21 companion edges determine the calculated fidelity, each contributing a factor (sin^2 θ + 1)/2.The simulation excludes some companion edges when their complexity benefit is small relative to the fidelity loss.
- The simulation includes no companion edges in the head, 5 of 7 in the tail, and all 16 in the interface.
The singular values of the sliced fSim gate
The method exploits exact and approximate low-rank structures arising when input indices of fSim gates are pinned during slicing.
- The sliced fSim tensor is analyzed by pinning each possible input-qubit configuration and reshaping the resulting tensor into matrices for singular-value calculation.
- Dropping the singular vectors associated with cos^2(θ) yields a rank-one approximation and effectively breaks a companion edge.The approximation decreases fidelity by approximately a factor (sin^2(θ) + 1)/2.
- Pinning two input indices produces a rank-one matrix that can be replaced by two (1, 0) vectors without decreasing fidelity.This exact rank-one structure reduces tensor-network computational complexity.
- Pinning one input index produces a rank-2 tensor whose singular values are heavily imbalanced for Sycamore circuits with θ ≈ π/2.The resulting tensor is used for an accurate low-rank approximation.
Validation of our method using smaller Sycamore circuits
The method is validated on smaller Sycamore circuits where exact amplitudes and fidelities are computationally available, using uncorrelated samples to compare fidelity and XEB estimates.
- Exact amplitudes of the original smaller circuits allow direct evaluation of sample XEB and fidelity for the approximate state.
- The validation uses 30-qubit, 14-cycle EFGH circuits with exact final states and approximate states formed by removing K edges and companion edges.
- 220 uncorrelated bitstrings are produced by grouping 2^20 approximate probabilities and sampling one bitstring per group with rejection sampling and Markov chains.
- The validation compares exact fidelity, estimated fidelity, logarithmic XEB, and XEB from 220 samples across edge cuts.Each data point in the reported comparison is averaged over 15 independent sample sets.
Contraction order
The contraction order uses a head-tail split, with a manually designed zig-zag order for the tail, and evaluates sample-based XEB and entropy on smaller circuits.
- Validation diagnostics: The approximate-state entropy is compared with entropy estimated from 220 uncorrelated samples over different numbers of cuts.
- Contraction order: The contraction order includes explicit tensor-pair sequences, with contractions assigned to the head before the tail.
- Validation diagnostics: For 30-qubit, 14-cycle circuits with K = 8 cuts, XEB is evaluated from 220 uncorrelated samples across group sizes.
- Validation diagnostics: The exact fidelity of the K = 8 approximate state is shown as a reference in the comparison.
- Contraction order: The 53-qubit tensor network is split into head and tail parts, with tail contractions using a manually designed zig-zag order.The split and contraction IDs are illustrated in the cited figures.