Fast and converged classical simulations of evidence for the utility of quantum computing before fault tolerance

Abstract

A recent quantum simulation of observables of the kicked Ising model on 127 qubits implemented circuits that exceed the capabilities of exact classical simulation. We show that several approximate classical methods, based on sparse Pauli dynamics and tensor network algorithms, can simulate these observables orders of magnitude faster than the quantum experiment, and can also be systematically converged beyond the experimental accuracy. Our most accurate technique combines a mixed Schrödinger and Heisenberg tensor network representation with the Bethe free entropy relation of belief propagation to compute expectation values with an effective wavefunction-operator sandwich bond dimension >16,000,000, achieving an absolute accuracy, without extrapolation, in the observables of <0.01, which is converged for many practical purposes. We thereby identify inaccuracies in the experimental extrapolations and suggest how future experiments can be implemented to increase the classical hardness.

This can be regarded as the full version of the preliminary note in arXiv:2306.16372

References in corpus (16)

• Strong quantum computational advantage using a superconducting quantum processor
• Accurate determination of tensor network state of quantum lattice models in two dimensions
• Algorithms for finite Projected Entangled Pair States
• Hyper-optimized tensor network contraction
• Quantum Graphical Models and Belief Propagation
• Solving the sampling problem of the Sycamore quantum circuits
• Efficient tensor network simulation of IBM's Eagle kicked Ising experiment
• Quantum Belief Propagation
• Fast and converged classical simulations of evidence for the utility of quantum computing before fault tolerance
• Simulation of Qubit Quantum Circuits via Pauli Propagation
• Effective quantum volume, fidelity and computational cost of noisy quantum processing experiments
• Tensor Networks contraction and the Belief Propagation algorithm
• Gauging tensor networks with belief propagation
• Simulating Noisy Variational Quantum Algorithms: A Polynomial Approach
• Fourier expansion in variational quantum algorithms
• Block belief propagation algorithm for two-dimensional tensor networks

Cited by in corpus (55)

• Beyond-classical computation in quantum simulation
• Fast and converged classical simulations of evidence for the utility of quantum computing before fault tolerance
• Does provable absence of barren plateaus imply classical simulability?
• Benchmarking quantum computers
• Efficient tensor network simulation of IBM's largest quantum processors
• Quantum computing for chemistry and physics applications from a Monte Carlo perspective
• Stabilizer Tensor Networks: universal quantum simulator on a basis of stabilizer states
• Tensor networks enable the calculation of turbulence probability distributions
• Towards a Linear-Ramp QAOA protocol: Evidence of a scaling advantage in solving some combinatorial optimization problems
• Simulating unsteady fluid flows on a superconducting quantum processor
• Benchmarking Quantum Computer Simulation Software Packages: State Vector Simulators
• Classically estimating observables of noiseless quantum circuits
• Magic Resources of the Heisenberg Picture
• Real-time operator evolution in two and three dimensions via sparse Pauli dynamics
• Combining Matrix Product States and Noisy Quantum Computers for Quantum Simulation
• Scaling Whole-Chip QAOA for Higher-Order Ising Spin Glass Models on Heavy-Hex Graphs
• Bias-Field Digitized Counterdiabatic Quantum Algorithm for Higher-Order Binary Optimization
• Quantum Computing and Tensor Networks for Laminate Design: A Novel Approach to Stacking Sequence Retrieval
• Noise-induced shallow circuits and absence of barren plateaus
• Bridging Entanglement and Magic Resources within Operator Space
• A nonstabilizerness monotone from stabilizerness asymmetry
• Hubbard physics with Rydberg atoms: using a quantum spin simulator to simulate strong fermionic correlations
• Noise-Robust Detection of Quantum Phase Transitions
• Simulating quantum dynamics in two-dimensional lattices with tensor network influence functional belief propagation
• Dynamics of disordered quantum systems with two- and three-dimensional tensor networks
• Efficient simulation of parametrized quantum circuits under non-unital noise through Pauli backpropagation
• Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits
• Exponential Qubit Reduction in Optimization for Financial Transaction Settlement
• Loop Series Expansions for Tensor Networks
• Problem-tailored Simulation of Energy Transport on Noisy Quantum Computers
• Simulating quantum circuits with arbitrary local noise using Pauli Propagation
• Unveiling clean two-dimensional discrete time crystals on a digital quantum computer
• Efficient quantum-enhanced classical simulation for patches of quantum landscapes
• The Role of Quantum Computing in Advancing Scientific High-Performance Computing: A perspective from the ADAC Institute
• Classical simulability of Clifford+T circuits with Clifford-augmented matrix product states
• Quantum subspace expansion approach for simulating dynamical response functions of Kitaev spin liquids
• State-dependent mobility edge in kinetically constrained models
• Survey on Computational Applications of Tensor Network Simulations
• Automatic Structural Search of Tensor Network States including Entanglement Renormalization
• PAC-learning of free-fermionic states is NP-hard
• Analog simulation of noisy quantum circuits
• Scalable projected entangled-pair state representation of random quantum circuit states
• Simulating dynamics of the two-dimensional transverse-field Ising model: a comparative study of large-scale classical numerics
• Short-time simulation of quantum dynamics by Pauli measurements
• Evaluating the Limits of QAOA Parameter Transfer at High-Rounds on Sparse Ising Models With Geometrically Local Cubic Terms
• Efficient Online Quantum Circuit Learning with No Upfront Training
• Utility-Scale Quantum State Preparation: Classical Training using Pauli Path Simulation
• Symmetry-Accelerated Classical Simulation of Clifford-Dominated Circuits
• Tensor Network Loop Cluster Expansions for Quantum Many-Body Problems
• A quantum eigenvalue solver based on tensor networks
• Variational Tensor Network Simulation of Gaussian Boson Sampling and Beyond
• Emulation of large-scale qubit registers with a phase-space approach
• Majorana string simulation of nonequilibrium dynamics in two-dimensional lattice fermion systems
• Entropy density benchmarking of near-term quantum circuits
• Classical simulation of noisy quantum circuits via locally entanglement-optimal unravelings