What limits the simulation of quantum computers?

Abstract

It is imperative that useful quantum computers be very difficult to simulate classically; otherwise classical computers could be used for the applications envisioned for the quantum ones. Perfect quantum computers are unarguably exponentially difficult to simulate: the classical resources required grow exponentially with the number of qubits $N$ or the depth $D$ of the circuit. Real quantum computing devices, however, are characterized by an exponentially decaying fidelity $\mathcal{F}\sim (1-\epsilon {)}^{ND}$ with an error rate $\epsilon$ per operation as small as $\approx 1\%$ for current devices. In this work, we demonstrate that real quantum computers can be simulated at a tiny fraction of the cost that would be needed for a perfect quantum computer. Our algorithms compress the representations of quantum wavefunctions using matrix product states (MPS), which capture states with low to moderate entanglement very accurately. This compression introduces a finite error rate $\epsilon$ so that the algorithms closely mimic the behavior of real quantum computing devices. The computing time of our algorithm increases only linearly with $N$ and $D$. We illustrate our algorithms with simulations of random circuits for qubits connected in both one and two dimensional lattices. We find that $\epsilon$ can be decreased at a polynomial cost in computing power down to a minimum error ${\epsilon }_{\infty }$. Getting below ${\epsilon }_{\infty }$ requires computing resources that increase exponentially with ${\epsilon }_{\infty }/\epsilon$. For a two dimensional array of $N=54$ qubits and a circuit with Control-Z gates, error rates better than state-of-the-art devices can be obtained on a laptop in a few hours. For more complex gates such as a swap gate followed by a controlled rotation, the error rate increases by a factor three for similar computing time.

arXiv commentNew data added, 14 figures

References in corpus (18)

• Quantum Computing in the NISQ era and beyond
• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• The density-matrix renormalization group in the age of matrix product states
• Random-Matrix Theory of Quantum Transport
• Efficient classical simulation of slightly entangled quantum computations
• Matrix Product States, Projected Entangled Pair States, and variational renormalization group methods for quantum spin systems
• Improved Simulation of Stabilizer Circuits
• Characterizing Quantum Supremacy in Near-Term Devices
• Entanglement renormalization
• Time-evolution methods for matrix-product states
• Simulating quantum computation by contracting tensor networks
• Coherent control of single electrons: a review of current progress
• Isometric Tensor Network States in Two Dimensions
• Perfect Sampling with Unitary Tensor Networks
• General-purpose quantum circuit simulator with Projected Entangled-Pair States and the quantum supremacy frontier
• Contracting Arbitrary Tensor Networks: General Approximate Algorithm and Applications in Graphical Models and Quantum Circuit Simulations
• What determines the ultimate precision of a quantum computer?
• A multiprecision C++ library for matrix-product-state simulation of quantum computing: Evaluation of numerical errors

Cited by in corpus (111)

• Phase-Programmable Gaussian Boson Sampling Using Stimulated Squeezed Light
• Quantum technologies need a Quantum Energy Initiative
• Computational advantage of quantum random sampling
• Solving the sampling problem of the Sycamore quantum circuits
• Efficient tensor network simulation of IBM's Eagle kicked Ising experiment
• TensorCircuit: a Quantum Software Framework for the NISQ Era
• Stark many-body localization on a superconducting quantum processor
• Efficient classical simulation of noisy random quantum circuits in one dimension
• Developments in the Tensor Network -- from Statistical Mechanics to Quantum Entanglement
• Evaluating the noise resilience of variational quantum algorithms
• Classical variational simulation of the Quantum Approximate Optimization Algorithm
• Solvable model of deep thermalization with distinct design times
• A density-matrix renormalization group algorithm for simulating quantum circuits with a finite fidelity
• Is quantum computing green? An estimate for an energy-efficiency quantum advantage
• Quantum error mitigation via matrix product operators
• Optimizing resource efficiencies for scalable full-stack quantum computers
• Adiabatic Spectroscopy and a Variational Quantum Adiabatic Algorithm
• Boundaries of quantum supremacy via random circuit sampling
• Classical simulation of lossy boson sampling using matrix product operators
• Simulating Noisy Quantum Circuits with Matrix Product Density Operators
• Limitations of Linear Cross-Entropy as a Measure for Quantum Advantage
• Noise and the frontier of quantum supremacy
• An entanglement perspective on the quantum approximate optimization algorithm
• Hydrodynamics of quantum entropies in Ising chains with linear dissipation
• Efficient Simulation of Dynamics in Two-Dimensional Quantum Spin Systems with Isometric Tensor Networks
• Gauging tensor networks with belief propagation
• The computational power of random quantum circuits in arbitrary geometries
• Quantum Magic and Multi-Partite Entanglement in the Structure of Nuclei
• Simulating (2+1)D SU(2) Yang-Mills Lattice Gauge Theory at finite density with tensor networks
• Many-Body Open Quantum Systems
• Simulating Noisy Variational Quantum Algorithms: A Polynomial Approach
• Fourier expansion in variational quantum algorithms
• Efficient variational synthesis of quantum circuits with coherent multi-start optimization
• Evolution of many-body systems under ancilla quantum measurements
• Simulating quantum circuits using tree tensor networks
• Variational quantum algorithm for unconstrained black box binary optimization: Application to feature selection
• Entanglement Dynamics of Noisy Random Circuits
• Explaining Quantum Circuits with Shapley Values: Towards Explainable Quantum Machine Learning
• Variational quantum dynamics of two-dimensional rotor models
• Opening the Black Box Inside Grover's Algorithm
• Efficient sampling of noisy shallow circuits via monitored unraveling
• Combining Matrix Product States and Noisy Quantum Computers for Quantum Simulation
• Quantum algorithms for scientific computing
• Mitigating crosstalk errors by randomized compiling: Simulation of the BCS model on a superconducting quantum computer
• Using analog computers in today's largest computational challenges
• Calibrating the Classical Hardness of the Quantum Approximate Optimization Algorithm
• Impact of decoherence on the fidelity of quantum gates leaving the computational subspace
• A Framework for Curriculum Transformation in Quantum Information Science and Technology Education
• Stable bipolarons in open quantum systems
• Quantum-inspired event reconstruction with Tensor Networks: Matrix Product States
• Benchmarking a novel efficient numerical method for localized 1D Fermi-Hubbard systems on a quantum simulator
• Defining Quantum Games
• Fast Time-Evolution of Matrix-Product States using the QR decomposition
• Quantum Computing for Atomic and Molecular Resonances
• Continuous-time dynamics and error scaling of noisy highly-entangling quantum circuits
• Certificates of quantum many-body properties assisted by machine learning
• The History of Quantum Games
• Robust sparse IQP sampling in constant depth
• Emulating Quantum Interference with Generalized Ising Machines
• Simulating the quantum Fourier transform, Grover's algorithm, and the quantum counting algorithm with limited entanglement using tensor-networks
• Quantum computing topological invariants of two-dimensional quantum matter
• Quantum-Computer-Based Verification of Quantum Thermodynamic Uncertainty Relation
• Entanglement entropy scaling of noisy random quantum circuits in two dimensions
• Dynamics of disordered quantum systems with two- and three-dimensional tensor networks
• Bosonic entanglement renormalization circuits from wavelet theory
• Noisy induced entanglement transition in one-dimensional random quantum circuits
• Quantum circuit compilation with quantum computers
• Loop Series Expansions for Tensor Networks
• Feynman-path type simulation using stabilizer projector decomposition of unitaries
• Differentiable matrix product states for simulating variational quantum computational chemistry
• Correlated states in super-moiré materials with a kernel polynomial quantics tensor cross interpolation algorithm
• Semiconductor-based electron flying qubits: Review on recent progress accelerated by numerical modelling
• Critical Limitations in Quantum-Selected Configuration Interaction Methods
• Long-time equilibration can determine transient thermality
• Optimizing Radiotherapy Plans for Cancer Treatment with Tensor Networks
• Classical simulability of Clifford+T circuits with Clifford-augmented matrix product states
• Improved real-space parallelizable matrix-product state compression and its application to unitary quantum dynamics simulation
• Optimal compression of constrained quantum time evolution
• Solving the Gross-Pitaevskii equation on multiple different scales using the quantics tensor train representation
• Efficient and systematic calculation of arbitrary observables for the matrix product state excitation ansatz
• Automatic Structural Search of Tensor Network States including Entanglement Renormalization
• Finite temperature tensor network algorithm for frustrated two-dimensional quantum materials
• Simulating quantum circuits using the multi-scale entanglement renormalization ansatz
• Efficient Mean-Field Simulation of Quantum Circuits Inspired by Density Functional Theory
• BGLS: A Python Package for the Gate-by-Gate Sampling Algorithm to Simulate Quantum Circuits
• Macroproperties vs. Microstates in the Classical Simulation of Critical Phenomena in Quench Dynamics of 1D Ising Models
• Approximate Contraction of Arbitrary Tensor Networks with a Flexible and Efficient Density Matrix Algorithm
• Prospects for NMR Spectral Prediction on Fault-Tolerant Quantum Computers
• Analog simulation of noisy quantum circuits
• Ab-Initio Approach to Many-Body Quantum Spin Dynamics
• Self-consistent tensor network method for correlated super-moiré matter beyond one billion sites
• Scalable projected entangled-pair state representation of random quantum circuit states
• Tomography-assisted noisy quantum circuit simulator using matrix product density operators
• Boson sampling with ultracold atoms in a programmable optical lattice
• Simulating dynamics of the two-dimensional transverse-field Ising model: a comparative study of large-scale classical numerics
• Simulating Quantum Circuits with Tree Tensor Networks using Density-Matrix Renormalization Group Algorithm
• Approximate Quadratization of High-Order Hamiltonians for Combinatorial Quantum Optimization
• Quantum max-flow in the bridge graph
• Active Learning for Quantum Mechanical Measurements
• Feasibility of performing quantum chemistry calculations on quantum computers
• Tensor network method for real-space topology in quasicrystal Chern mosaics
• Accelerating Quantum Eigensolver Algorithms With Machine Learning
• Pilot-Wave Simulator: Exact Classical Sampling from Ideal and Noisy Quantum Circuits up to Hundreds of Qubits
• Schmidt quantum compressor
• Dynamical cluster-based strategy for improving tensor network algorithms in quantum circuit simulations
• Variational matrix product states for combinatorial optimization
• A Heuristic for Matrix Product State Simulation of Out-of-Equilibrium Dynamics of Two-Dimensional Quantum Spin Systems
• Who can compete with quantum computers? Lecture notes on quantum inspired tensor networks computational techniques
• Classical simulation of noisy quantum circuits via locally entanglement-optimal unravelings
• Toward quantum scaling advantage in approximate optimization
• Locally Purified Maximally Mixed States At Scale: Entanglement Pruning and Symmetries