Solving the sampling problem of the Sycamore quantum circuits

Abstract

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{\psi }(\mathbf{s}){|}^2$, where the approximate state $\hat{\psi }$ 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.

17 pages, 13 figures

References in corpus (2)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Strong quantum computational advantage using a superconducting quantum processor

Cited by in corpus (75)

• Computational advantage of quantum random sampling
• TensorCircuit: a Quantum Software Framework for the NISQ Era
• Beyond-classical computation in quantum simulation
• Phase transition in Random Circuit Sampling
• Nishimori's cat: stable long-range entanglement from finite-depth unitaries and weak measurements
• Near-Term Quantum Computing Techniques: Variational Quantum Algorithms, Error Mitigation, Circuit Compilation, Benchmarking and Classical Simulation
• Fast and converged classical simulations of evidence for the utility of quantum computing before fault tolerance
• A polynomial-time classical algorithm for noisy random circuit sampling
• NISQ Computers: A Path to Quantum Supremacy
• A density-matrix renormalization group algorithm for simulating quantum circuits with a finite fidelity
• Variational Benchmarks for Quantum Many-Body Problems
• Is quantum computing green? An estimate for an energy-efficiency quantum advantage
• Resources for bosonic quantum computational advantage
• Dynamical Magic Transitions in Monitored Clifford+T Circuits
• Demonstration of algorithmic quantum speedup
• Probing quantum correlations in many-body systems: a review of scalable methods
• Effective quantum volume, fidelity and computational cost of noisy quantum processing experiments
• Large-scale quantum approximate optimization on non-planar graphs with machine learning noise mitigation
• Absence of barren plateaus in finite local-depth circuits with long-range entanglement
• Gauging tensor networks with belief propagation
• The computational power of random quantum circuits in arbitrary geometries
• Spoofing cross entropy measure in boson sampling
• Benchmarking Quantum Computer Simulation Software Packages: State Vector Simulators
• Tensor networks for interpretable and efficient quantum-inspired machine learning
• Tensor networks for quantum computing
• Opening the Black Box Inside Grover's Algorithm
• Efficient sampling of noisy shallow circuits via monitored unraveling
• Assessing and Advancing the Potential of Quantum Computing: A NASA Case Study
• Quantum algorithms for scientific computing
• Quantum cryptography beyond key distribution: theory and experiment
• Validating quantum-supremacy experiments with exact and fast tensor network contraction
• Simulating quantum circuits using efficient tensor network contraction algorithms with subexponential upper bound
• Protocols for classically training quantum generative models on probability distributions
• Efficient Quantum Circuit Compilation for Near-Term Quantum Advantage
• The Coming Decades of Quantum Simulation
• Distributed quantum machine learning via classical communication
• Noise-Robust Detection of Quantum Phase Transitions
• Simulating the quantum Fourier transform, Grover's algorithm, and the quantum counting algorithm with limited entanglement using tensor-networks
• Entanglement entropy scaling of noisy random quantum circuits in two dimensions
• Exponential Qubit Reduction in Optimization for Financial Transaction Settlement
• Fault-tolerant compiling of classically hard IQP circuits on hypercubes
• Verifiable measurement-based quantum random sampling with trapped ions
• Time-optimal transfer of the quantum state in long qubit arrays
• Loop Series Expansions for Tensor Networks
• Characterizing randomness in parameterized quantum circuits through expressibility and average entanglement
• Correlated states in super-moiré materials with a kernel polynomial quantics tensor cross interpolation algorithm
• Classical simulability of Clifford+T circuits with Clifford-augmented matrix product states
• The Role of Quantum Computing in Advancing Scientific High-Performance Computing: A perspective from the ADAC Institute
• Experimental Quantum Advantage in the Odd-Cycle Game
• Improved real-space parallelizable matrix-product state compression and its application to unitary quantum dynamics simulation
• TensorKrowch: Smooth integration of tensor networks in machine learning
• Efficient and systematic calculation of arbitrary observables for the matrix product state excitation ansatz
• Survey on Computational Applications of Tensor Network Simulations
• Efficient Optimization of Variational Autoregressive Networks with Natural Gradient
• Solving the Gross-Pitaevskii equation on multiple different scales using the quantics tensor train representation
• Simulating quantum circuits using the multi-scale entanglement renormalization ansatz
• Report on reproducibility in condensed matter physics
• Scalable projected entangled-pair state representation of random quantum circuit states
• Revisiting Nishimori multicriticality through the lens of information measures
• Low Depth Virtual Distillation of Quantum Circuits by Deterministic Circuit Decomposition
• Expressibility, entangling power and quantum average causal effect for causally indefinite circuits
• Secret extraction attacks against obfuscated IQP circuits
• Classically Simulating Quantum Supremacy IQP Circuits through a Random Graph Approach
• Quantum max-flow in the bridge graph
• Tight-Binding Energy-Phase Calculation for Topological Josephson Junction Nanowire Architecture
• Optimal sampling of tensor networks targeting wave function's fast decaying tails
• Dynamical cluster-based strategy for improving tensor network algorithms in quantum circuit simulations
• Toward quantum scaling advantage in approximate optimization
• Matrix Product State on a Quantum Computer
• Efficient classical simulation of cluster state quantum circuits with alternative inputs
• Efficient Quantum Circuit Simulation by Tensor Network Methods on Modern GPUs
• Tensorization of neural networks for improved privacy and interpretability
• Recent quantum runtime (dis)advantages
• Provable and Verifiable Quantum Advantage in Sample Complexity
• Integrating Neural Networks and Tensor Networks for Computing Free Energy