Faster quantum simulation by randomization

Abstract

Product formulas can be used to simulate Hamiltonian dynamics on a quantum computer by approximating the exponential of a sum of operators by a product of exponentials of the individual summands. This approach is both straightforward and surprisingly efficient. We show that by simply randomizing how the summands are ordered, one can prove stronger bounds on the quality of approximation for product formulas of any given order, and thereby give more efficient simulations. Indeed, we show that these bounds can be asymptotically better than previous bounds that exploit commutation between the summands, despite using much less information about the structure of the Hamiltonian. Numerical evidence suggests that the randomized approach has better empirical performance as well.

arXiv comment20 pages, 2 figures

References in corpus (24)

• Quantum algorithm for solving linear systems of equations
• Hamiltonian Simulation by Qubitization
• Exponential algorithmic speedup by quantum walk
• Optimal Hamiltonian Simulation by Quantum Signal Processing
• Simulating Hamiltonian dynamics with a truncated Taylor series
• Elucidating Reaction Mechanisms on Quantum Computers
• Efficient quantum algorithms for simulating sparse Hamiltonians
• Universal digital quantum simulation with trapped ions
• Toward the first quantum simulation with quantum speedup
• Quantum Algorithms for Quantum Field Theories
• Hamiltonian simulation with nearly optimal dependence on all parameters
• A random compiler for fast Hamiltonian simulation
• Digital quantum simulation of fermionic models with a superconducting circuit
• Gate count estimates for performing quantum chemistry on small quantum computers
• Quantum simulation of time-dependent Hamiltonians and the convenient illusion of Hilbert space
• Exponential improvement in precision for simulating sparse Hamiltonians
• Chemical Basis of Trotter-Suzuki Errors in Quantum Chemistry Simulation
• Quantum algorithm for linear differential equations with exponentially improved dependence on precision
• Nearly optimal lattice simulation by product formulas
• Time-dependent Hamiltonian simulation with $L^1$-norm scaling
• Limitations of Quantum Simulation Examined by Simulating a Pairing Hamiltonian using Nuclear Magnetic Resonance
• Quantum-circuit design for efficient simulations of many-body quantum dynamics
• Shorter gate sequences for quantum computing by mixing unitaries
• Black-box Hamiltonian simulation and unitary implementation

Cited by in corpus (109)

• Quantum computational chemistry
• Quantum algorithms for quantum chemistry and quantum materials science
• Quantum Error Mitigation
• Hybrid quantum-classical algorithms and quantum error mitigation
• A Theory of Trotter Error
• The Future of Quantum Computing with Superconducting Qubits
• Variational quantum simulation of general processes
• Virtual Distillation for Quantum Error Mitigation
• Quantum Computing for High-Energy Physics: State of the Art and Challenges. Summary of the QC4HEP Working Group
• Emerging quantum computing algorithms for quantum chemistry
• Standard Model Physics and the Digital Quantum Revolution: Thoughts about the Interface
• Improved Fault-Tolerant Quantum Simulation of Condensed-Phase Correlated Electrons via Trotterization
• Resource-efficient digital quantum simulation of $d$-level systems for photonic, vibrational, and spin-$s$ Hamiltonians
• Time-dependent Hamiltonian simulation with $L^1$-norm scaling
• Rodeo Algorithm for Quantum Computing
• Simulating Quantum Materials with Digital Quantum Computers
• Faster Digital Quantum Simulation by Symmetry Protection
• Toward scalable simulations of Lattice Gauge Theories on quantum computers
• Concentration for random product formulas
• Time-dependent unbounded Hamiltonian simulation with vector norm scaling
• Time-marching based quantum solvers for time-dependent linear differential equations
• Nearly tight Trotterization of interacting electrons
• Robust quantum compilation and circuit optimisation via energy minimisation
• Simulating quantum chemistry in the seniority-zero space on qubit-based quantum computers
• Compilation by stochastic Hamiltonian sparsification
• Optimised Trotter Decompositions for Classical and Quantum Computing
• Hunting for quantum-classical crossover in condensed matter problems
• Variational Hamiltonian simulation for translational invariant systems via classical pre-processing
• Randomizing multi-product formulas for Hamiltonian simulation
• First-Order Trotter Error from a Second-Order Perspective
• QuESTlink -- Mathematica embiggened by a hardware-optimised quantum emulator
• Realization of quantum signal processing on a noisy quantum computer
• Time-dependent Hamiltonian Simulation of Highly Oscillatory Dynamics and Superconvergence for Schrödinger Equation
• Trapped-Ion Quantum Simulation of Collective Neutrino Oscillations
• One bound to rule them all: from Adiabatic to Zeno
• Local variational quantum compilation of a large-scale Hamiltonian dynamics
• Quantum imaginary time evolution steered by reinforcement learning
• Measuring the Loschmidt amplitude for finite-energy properties of the Fermi-Hubbard model on an ion-trap quantum computer
• Quantum Computer-Aided design of Quantum Optics Hardware
• qSWIFT: High-order randomized compiler for Hamiltonian simulation
• State preparation and measurement in a quantum simulation of the O(3) sigma model
• Error-resilient Monte Carlo quantum simulation of imaginary time
• A quantum hamiltonian simulation benchmark
• Fragmented imaginary-time evolution for early-stage quantum signal processors
• Composite Quantum Simulations
• Low-depth Hamiltonian Simulation by Adaptive Product Formula
• Qubit-Efficient Randomized Quantum Algorithms for Linear Algebra
• Importance sampling for stochastic quantum simulations
• HamLib: A library of Hamiltonians for benchmarking quantum algorithms and hardware
• Efficient quantum imaginary time evolution by drifting real time evolution: an approach with low gate and measurement complexity
• Mana and thermalization: probing the feasibility of near-Clifford Hamiltonian simulation
• Tailoring Term Truncations for Electronic Structure Calculations Using a Linear Combination of Unitaries
• Post-Hartree-Fock method in Quantum Chemistry for Quantum Computer
• Fault-tolerant quantum algorithms for quantum molecular systems: A survey
• Quantum computer-aided design: digital quantum simulation of quantum processors
• State-dependent error bound for digital quantum simulation of driven systems
• A stochastic quantum Krylov protocol with double factorized Hamiltonians
• Low-depth simulations of fermionic systems on square-grid quantum hardware
• Quantum differential equation solvers: limitations and fast-forwarding
• Encoding trade-offs and design toolkits in quantum algorithms for discrete optimization: coloring, routing, scheduling, and other problems
• Continuous Hamiltonian dynamics on digital quantum computers without discretization error
• Measurement-Based Time Evolution for Quantum Simulation of Fermionic Systems
• Co-Design quantum simulation of nanoscale NMR
• Doubling the order of approximation via the randomized product formula
• Quantum computing Floquet energy spectra
• Quantum error mitigation for Fourier moment computation
• Simple and high-precision Hamiltonian simulation by compensating Trotter error with linear combination of unitary operations
• Algorithm-Oriented Qubit Mapping for Variational Quantum Algorithms
• Sample-efficient verification of continuously-parameterized quantum gates for small quantum processors
• Quantum algorithm for linear non-unitary dynamics with near-optimal dependence on all parameters
• Early Fault-Tolerant Quantum Algorithms in Practice: Application to Ground-State Energy Estimation
• Parallel Quantum Algorithm for Hamiltonian Simulation
• Simulating time evolution on distributed quantum computers
• TFermion: A non-Clifford gate cost assessment library of quantum phase estimation algorithms for quantum chemistry
• Suppression of inter-band heating for random driving
• Selection and improvement of product formulae for best performance of quantum simulation
• Novel Trotter formulas for digital quantum simulation
• Halving the Cost of Quantum Algorithms with Randomization
• Practicality of quantum adiabatic algorithm for chemistry applications
• Improving the Performance of Digitized Counterdiabatic Quantum Optimization via Algorithm-Oriented Qubit Mapping
• Exploiting anticommutation in Hamiltonian simulation
• Lower bound for simulation cost of open quantum systems: Lipschitz continuity approach
• Quantum techniques for eigenvalue problems
• Tensor Network enhanced Dynamic Multiproduct Formulas
• Quantum simulation by qubitization without Toffoli gates
• Random Splitting of Fluid Models: Ergodicity and Convergence
• Optimize quantum simulation using a force-gradient integrator
• Transforming Collections of Pauli Operators into Equivalent Collections of Pauli Operators over Minimal Registers
• Some Error Analysis for the Quantum Phase Estimation Algorithms
• Digital simulation of convex mixtures of Markovian and non-Markovian single qubit Pauli channels on NISQ devices
• Unifying framework for quantum simulation algorithms for time-dependent Hamiltonian dynamics
• Quantum eigenvalue processing
• Parallelization techniques for quantum simulation of fermionic systems
• High-precision and low-depth quantum algorithm design for eigenstate problems
• Quantum Computing Beyond Ground State Electronic Structure: A Review of Progress Toward Quantum Chemistry Out of the Ground State
• Resource-Dependent Complexity of Quantum Channels
• Statistical prethermalization in randomly kicked many-body classical rotor system
• Expanding Hardware-Efficiently Manipulable Hilbert Space via Hamiltonian Embedding
• Faster Algorithmic Quantum and Classical Simulations by Corrected Product Formulas
• Digital Quantum Simulations of the Non-Resonant Open Tavis-Cummings Model
• Trotter error time scaling separation via commutant decomposition
• Short-time simulation of quantum dynamics by Pauli measurements
• Simulating sparse SYK model with a randomized algorithm on a trapped-ion quantum computer
• Quantum algorithms based on quantum trajectories
• Optimising Trotter-Suzuki Simulations of Markovian Open Quantum Systems via Classical Search
• A Randomized Method for Simulating Lindblad Equations and Thermal State Preparation
• Scalable Simulation of Fermionic Encoding Performance on Noisy Quantum Computers
• Quantum Chaos and Universal Trotterisation Behaviours in Digital Quantum Simulations
• Data-Efficient Quantum Noise Modeling via Machine Learning