Entanglement accelerates quantum simulation

Abstract

Quantum entanglement is an essential feature of many-body systems that impacts both quantum information processing and fundamental physics. The growth of entanglement is a major challenge for classical simulation methods. In this work, we investigate the relationship between quantum entanglement and quantum simulation, showing that product-formula approximations can perform better for entangled systems. We establish a tighter upper bound for algorithmic error in terms of entanglement entropy and develop an adaptive simulation algorithm incorporating measurement gadgets to estimate the algorithmic error. This shows that entanglement is not only an obstacle to classical simulation, but also a feature that can accelerate quantum algorithms.

31 pages, 6 figures

References in corpus (37)

• Quantum entanglement
• Many body localization and thermalization in quantum statistical mechanics
• Efficient classical simulation of slightly entangled quantum computations
• From Quantum Chaos and Eigenstate Thermalization to Statistical Mechanics and Thermodynamics
• Quantum Coherence as a Resource
• Quantum discord and the power of one qubit
• Predicting Many Properties of a Quantum System from Very Few Measurements
• Equilibration, thermalisation, and the emergence of statistical mechanics in closed quantum systems
• Hamiltonian Simulation by Qubitization
• Matrix Product States and Projected Entangled Pair States: Concepts, Symmetries, and Theorems
• Optimal Hamiltonian Simulation by Quantum Signal Processing
• Simulating Hamiltonian dynamics with a truncated Taylor series
• Determining eigenstates and thermal states on a quantum computer using quantum imaginary time evolution
• Efficient quantum algorithms for simulating sparse Hamiltonians
• Lieb-Robinson bounds and the generation of correlations and topological quantum order
• Time-evolution methods for matrix-product states
• Contextuality supplies the magic for quantum computation
• Tensor networks for complex quantum systems
• Quantum Simulators: Architectures and Opportunities
• Toward the first quantum simulation with quantum speedup
• Quantum Many-Body Scars and Weak Breaking of Ergodicity
• Testing whether all eigenstates obey the Eigenstate Thermalization Hypothesis
• Aspects of generic entanglement
• Multipartite entanglement, quantum-error-correcting codes, and entangling power of quantum evolutions
• Provably efficient machine learning for quantum many-body problems
• Nearly optimal lattice simulation by product formulas
• Hamiltonian simulation in the low-energy subspace
• Time-dependent unbounded Hamiltonian simulation with vector norm scaling
• Nearly tight Trotterization of interacting electrons
• Hamiltonian simulation with random inputs
• First-Order Trotter Error from a Second-Order Perspective
• Destructive Error Interference in Product-Formula Lattice Simulation
• $k$-Uniform states and quantum information masking
• Polynomial-time classical simulation of quantum ferromagnets
• Self-healing of Trotter error in digital adiabatic state preparation
• Performance analysis of multi-shot shadow estimation
• Average-case Speedup for Product Formulas

Cited by in corpus (16)

• Exponentially reduced circuit depths in Lindbladian simulation
• Trotterization is substantially efficient for low-energy states
• On the Trotter Error in Many-body Quantum Dynamics with Coulomb Potentials
• Coherence as a resource for phase estimation
• Faster Algorithmic Quantum and Classical Simulations by Corrected Product Formulas
• Simulating Electron Transfer on Noisy Quantum Computers
• Adaptive random compiler for Hamiltonian simulation
• Detecting high-dimensional entanglement by randomized product projections
• Quantum Routing and Entanglement Dynamics Through Bottlenecks
• Stationary two-qubit entanglement mediated by one-dimensional plasmonic nanoarrays
• Benchmarking Quantum Simulation of Chemical Hamiltonians using the Sorted-List Encoding
• Fluctuation-guided adaptive random compiler for Hamiltonian simulation
• Energy Spectra of Compressed Quantum States
• Quantum states supported by matroids
• Scalable and fault-tolerant preparation of encoded k-uniform states
• Error Interference in Quantum Simulation