A random compiler for fast Hamiltonian simulation

Abstract

The dynamics of a quantum system can be simulated using a quantum computer by breaking down the unitary into a quantum circuit of one and two qubit gates. The most established methods are the Trotter-Suzuki decompositions, for which rigorous bounds on the circuit size depend on the number of terms $L$ in the system Hamiltonian and the size of the largest term in the Hamiltonian $\Lambda$. Consequently, Trotter-Suzuki is only practical for sparse Hamiltonians. Trotter-Suzuki is a deterministic compiler but it was recently shown that randomised compiling offers lower overheads. Here we present and analyse a randomised compiler for Hamiltonian simulation where gate probabilities are proportional to the strength of a corresponding term in the Hamiltonian. This approach requires a circuit size independent of $L$ and $\Lambda$, but instead depending on $\lambda$ the absolute sum of Hamiltonian strengths (the ${\ell }_1$ norm). Therefore, it is especially suited to electronic structure Hamiltonians relevant to quantum chemistry. Considering propane, carbon dioxide and ethane, we observe speed-ups compared to standard Trotter-Suzuki of between $306\times$ and $1591\times$ for physically significant simulation times at precision $10^{-3}$. Performing phase estimation at chemical accuracy, we report that the savings are similar.

Additional analysis of resource costs of using phase estimation to estimate electronic structure energies

References in corpus (12)

• Surface codes: Towards practical large-scale quantum computation
• Simulated Quantum Computation of Molecular Energies
• Simulating Hamiltonian dynamics with a truncated Taylor series
• Entanglement-free Heisenberg-limited phase estimation
• Toward the first quantum simulation with quantum speedup
• Variational Quantum Computation of Excited States
• Encoding Electronic Spectra in Quantum Circuits with Linear T Complexity
• Quantum simulation of time-dependent Hamiltonians and the convenient illusion of Hilbert space
• Chemical Basis of Trotter-Suzuki Errors in Quantum Chemistry Simulation
• Quantum phase estimation of multiple eigenvalues for small-scale (noisy) experiments
• Reducing the quantum computing overhead with complex gate distillation
• Optimal Trotterization in universal quantum simulators under faulty control

Cited by in corpus (220)

• Quantum computational chemistry
• Quantum algorithms for quantum chemistry and quantum materials science
• Quantum Error Mitigation
• A Theory of Trotter Error
• Quantum Simulation for High Energy Physics
• Even more efficient quantum computations of chemistry through tensor hypercontraction
• Quantum Computer Systems for Scientific Discovery
• Variational Fast Forwarding for Quantum Simulation Beyond the Coherence Time
• Virtual Distillation for Quantum Error Mitigation
• Qubitization of Arbitrary Basis Quantum Chemistry Leveraging Sparsity and Low Rank Factorization
• Stochastic gradient descent for hybrid quantum-classical optimization
• Quantum Computing for High-Energy Physics: State of the Art and Challenges. Summary of the QC4HEP Working Group
• Heisenberg-limited ground state energy estimation for early fault-tolerant quantum computers
• Nearly optimal lattice simulation by product formulas
• Emerging quantum computing algorithms for quantum chemistry
• Standard Model Physics and the Digital Quantum Revolution: Thoughts about the Interface
• Faster quantum simulation by randomization
• Increasing the representation accuracy of quantum simulations of chemistry without extra quantum resources
• 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
• Quantum Algorithms for Simulating the Lattice Schwinger Model
• Quantum error mitigation as a universal error-minimization technique: applications from NISQ to FTQC eras
• Lower bounds on the non-Clifford resources for quantum computations
• Low-depth gradient measurements can improve convergence in variational hybrid quantum-classical algorithms
• Quantifying quantum speedups: improved classical simulation from tighter magic monotones
• Fault-Tolerant Quantum Simulations of Chemistry in First Quantization
• Time-dependent Hamiltonian simulation with $L^1$-norm scaling
• Calculating energy derivatives for quantum chemistry on a quantum computer
• Early Fault-Tolerant Quantum Computing
• Quantum Computing for Neutrino-nucleus Scattering
• Rodeo Algorithm for Quantum Computing
• A randomized quantum algorithm for statistical phase estimation
• Hamiltonian simulation in the low-energy subspace
• Faster Digital Quantum Simulation by Symmetry Protection
• Early fault-tolerant simulations of the Hubbard model
• Quantum computing of the ${}^6$Li nucleus via ordered unitary coupled clusters
• Learning many-body Hamiltonians with Heisenberg-limited scaling
• 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
• Quantum algorithm for ground state energy estimation using circuit depth with exponentially improved dependence on precision
• Nearly tight Trotterization of interacting electrons
• Quantum Hamiltonian-Based Models and the Variational Quantum Thermalizer Algorithm
• Primitive Quantum Gates for an SU(2) Discrete Subgroup: BT
• Subspace Variational Quantum Simulator
• Robust quantum compilation and circuit optimisation via energy minimisation
• Compilation by stochastic Hamiltonian sparsification
• Primitive Quantum Gates for Dihedral Gauge Theories
• Improved Hamiltonians for Quantum Simulations
• Hybridized Methods for Quantum Simulation in the Interaction Picture
• Toward Quantum Simulations of ${\mathbb{Z}}_2$ Gauge Theory Without State Preparation
• Reducing molecular electronic Hamiltonian simulation cost for Linear Combination of Unitaries approaches
• Fast-forwarding quantum evolution
• Hunting for quantum-classical crossover in condensed matter problems
• Variational Hamiltonian simulation for translational invariant systems via classical pre-processing
• QuESTlink -- Mathematica embiggened by a hardware-optimised quantum emulator
• Randomizing multi-product formulas for Hamiltonian simulation
• First-Order Trotter Error from a Second-Order Perspective
• Realization of quantum signal processing on a noisy quantum computer
• Lattice Renormalization of Quantum Simulations
• Time-dependent Hamiltonian Simulation of Highly Oscillatory Dynamics and Superconvergence for Schrödinger Equation
• Constant-Depth Circuits for Dynamic Simulations of Materials on Quantum Computers
• Orbital transformations to reduce the 1-norm of the electronic structure Hamiltonian for quantum computing applications
• One bound to rule them all: from Adiabatic to Zeno
• Randomized compiling for scalable quantum computing on a noisy superconducting quantum processor
• Quantum Computation for Periodic Solids in Second Quantization
• Implementing any Linear Combination of Unitaries on Intermediate-term Quantum Computers
• Accelerated quantum Monte Carlo with mitigated error on noisy quantum computer
• Well-conditioned multi-product formulas for hardware-friendly Hamiltonian simulation
• On the complexity of implementing Trotter steps
• Local variational quantum compilation of a large-scale Hamiltonian dynamics
• Operator Sampling for Shot-frugal Optimization in Variational Algorithms
• 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 simulation of real-space dynamics
• Hardware-efficient quantum algorithm for the simulation of open-system dynamics and thermalisation
• Hybrid Oscillator-Qubit Quantum Processors: Instruction Set Architectures, Abstract Machine Models, and Applications
• 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
• Resource estimate for quantum many-body ground-state preparation on a quantum computer
• Selected topics of quantum computing for nuclear physics
• A quantum hamiltonian simulation benchmark
• Reducing the runtime of fault-tolerant quantum simulations in chemistry through symmetry-compressed double factorization
• Fragmented imaginary-time evolution for early-stage quantum signal processors
• Continuous-variable assisted thermal quantum simulation
• Gauge Theory Couplings on Anisotropic Lattices
• Quantum computing of reacting flows via Hamiltonian simulation
• Qubit-Efficient Randomized Quantum Algorithms for Linear Algebra
• Second-quantized fermionic operators with polylogarithmic qubit and gate complexity
• Composite Quantum Simulations
• Low-depth Hamiltonian Simulation by Adaptive Product Formula
• Efficient Hamiltonian Simulation for Solving Option Price Dynamics
• Q# and NWChem: Tools for Scalable Quantum Chemistry on Quantum Computers
• Mana and thermalization: probing the feasibility of near-Clifford Hamiltonian simulation
• Tailoring Term Truncations for Electronic Structure Calculations Using a Linear Combination of Unitaries
• Importance sampling for stochastic quantum simulations
• Synthesizing efficient circuits for Hamiltonian simulation
• Efficient quantum imaginary time evolution by drifting real time evolution: an approach with low gate and measurement complexity
• Probabilistic Interpolation of Quantum Rotation Angles
• 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
• Quantum computation of molecular structure using data from challenging-to-classically-simulate nuclear magnetic resonance experiments
• Scalable Quantum Simulations of Scattering in Scalar Field Theory on 120 Qubits
• 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
• Sachdev-Ye-Kitaev circuits for braiding and charging Majorana zero modes
• Continuous Hamiltonian dynamics on digital quantum computers without discretization error
• Average-case Speedup for Product Formulas
• Optimal Hamiltonian simulation for time-periodic systems
• 2QAN: A quantum compiler for 2-local qubit Hamiltonian simulation algorithms
• Encoding trade-offs and design toolkits in quantum algorithms for discrete optimization: coloring, routing, scheduling, and other problems
• Optimizing Stabilizer Parities for Improved Logical Qubit Memories
• Success of digital adiabatic simulation with large Trotter step
• Contextual Subspace Variational Quantum Eigensolver Calculation of the Dissociation Curve of Molecular Nitrogen on a Superconducting Quantum Computer
• Co-Design quantum simulation of nanoscale NMR
• Wave Matrix Lindbladization II: General Lindbladians, Linear Combinations, and Polynomials
• Quantum error mitigation for Fourier moment computation
• Quantum-selected configuration interaction with time-evolved state
• Algorithmic Shadow Spectroscopy
• Doubling the order of approximation via the randomized product formula
• Well-conditioned multiproduct Hamiltonian simulation
• Quantum computing Floquet energy spectra
• Simple and high-precision Hamiltonian simulation by compensating Trotter error with linear combination of unitary operations
• Hamiltonian simulation for low-energy states with optimal time dependence
• Sample-efficient verification of continuously-parameterized quantum gates for small quantum processors
• Quantum Computing Simulation of a Mixed Spin-Boson Hamiltonian and Its Performance for a Cavity Quantum Electrodynamics Problem
• Measurement-efficient quantum Krylov subspace diagonalisation
• Can shallow quantum circuits scramble local noise into global white noise?
• Early Fault-Tolerant Quantum Algorithms in Practice: Application to Ground-State Energy Estimation
• Parallel Quantum Algorithm for Hamiltonian Simulation
• Simulation of open quantum systems via low-depth convex unitary evolutions
• Quantum algorithm for linear non-unitary dynamics with near-optimal dependence on all parameters
• Calculating the many-body density of states on a digital quantum computer
• Selection and improvement of product formulae for best performance of quantum simulation
• Higher-order quantum transformations of Hamiltonian dynamics
• Analysis of Superfast Encoding Performance for Electronic Structure Simulations
• Simulating time evolution on distributed quantum computers
• On Quantum Simulation Of Cosmic Inflation
• Approximate Quantum Compiling for Quantum Simulation: A Tensor Network based approach
• TFermion: A non-Clifford gate cost assessment library of quantum phase estimation algorithms for quantum chemistry
• Novel Trotter formulas for digital quantum simulation
• Fast quantum simulation of electronic structure by spectrum amplification
• Graph Optimization Perspective for Low-Depth Trotter-Suzuki Decomposition
• A Quantum Simulation Approach to Implementing Nuclear Density Functional Theory via Imaginary Time Evolution
• Sparse random Hamiltonians are quantumly easy
• Complexity of Digital Quantum Simulation in the Low-Energy Subspace: Applications and a Lower Bound
• Practicality of quantum adiabatic algorithm for chemistry applications
• Halving the Cost of Quantum Algorithms with Randomization
• Measuring Trotter error and its application to precision-guaranteed Hamiltonian simulations
• Exploiting anticommutation in Hamiltonian simulation
• Lower bound for simulation cost of open quantum systems: Lipschitz continuity approach
• Flexibility of the factorized form of the unitary coupled cluster ansatz
• TE-PAI: Exact Time Evolution by Sampling Random Circuits
• Ab initio extended Hubbard model of short polyenes for efficient quantum computing
• Trotterization is substantially efficient for low-energy states
• Solving lattice gauge theories using the quantum Krylov algorithm and qubitization
• Matrix product state ansatz for the variational quantum solution of the Heisenberg model on Kagome geometries
• Randomized semi-quantum matrix processing
• Ansatz-free Hamiltonian learning with Heisenberg-limited scaling
• Quantum simulation of time-dependent Hamiltonians via commutator-free quasi-Magnus operators
• Quantum techniques for eigenvalue problems
• Statistics of topological defects across a phase transition in a digital superconducting quantum processor
• A Partially Random Trotter Algorithm for Quantum Hamiltonian Simulations
• Solvent distribution effects on quantum chemical calculations with quantum computers
• Inverse iteration quantum eigensolvers assisted with a continuous variable
• Numerical analysis for inchworm Monte Carlo method: Sign problem and error growth
• Lindblad engineering for quantum Gibbs state preparation under the eigenstate thermalization hypothesis
• Learning interacting fermionic Hamiltonians at the Heisenberg limit
• Cost of Emulating a Small Quantum Annealing Problem in the Circuit-Model
• Power of quantum measurement in simulating unphysical operations
• Systematic many-fermion Hamiltonian input scheme and spectral calculations on quantum computers
• 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
• Hardware-efficient quantum phase estimation via local control
• Quantum eigenvalue processing
• Simulating quantum collision models with Hamiltonian simulations using early fault-tolerant quantum computers
• Space-time tradeoff in networked virtual distillation
• High-precision and low-depth quantum algorithm design for eigenstate problems
• Full-counting statistics of particle distribution on a digital quantum computer
• Chemically Motivated Simulation Problems are Efficiently Solvable by a Quantum Computer
• Exponential distillation of dominant eigenproperties
• Faster Algorithmic Quantum and Classical Simulations by Corrected Product Formulas
• Digital Simulation of Single Qubit Markovian Open Quantum Systems: A Tutorial
• Phase estimation with partially randomized time evolution
• Quantum Computing Beyond Ground State Electronic Structure: A Review of Progress Toward Quantum Chemistry Out of the Ground State
• Multi-set variational quantum dynamics algorithm for simulating nonadiabatic dynamics on quantum computers
• Theory of quantum error mitigation for non-Clifford gates
• Comprehensive Library of Variational LSE Solvers
• Resource-Dependent Complexity of Quantum Channels
• Short-time simulation of quantum dynamics by Pauli measurements
• Stochastic search for approximate compilation of unitaries
• Learning the structure of any Hamiltonian from minimal assumptions
• Blockwise Optimization for Projective Variational Quantum Dynamics (BLOP-VQD): Algorithm and Implementation for Lattice Systems
• Robustly decorrelating errors with mixed quantum gates
• Adaptive random compiler for Hamiltonian simulation
• Generative flow-based warm start of the variational quantum eigensolver
• Simulating sparse SYK model with a randomized algorithm on a trapped-ion quantum computer
• Quantum algorithms based on quantum trajectories
• Quantum approximated cloning-assisted density matrix exponentiation
• Halving the cost of quantum multiplexed rotations
• Recurrence in discrete-time quantum stochastic walks
• Quantum Chaos and Universal Trotterisation Behaviours in Digital Quantum Simulations
• Transversal architecture for megaquop-scale quantum simulation with neutral atoms
• Fluctuation-guided adaptive random compiler for Hamiltonian simulation
• Quantum Simulation via Stochastic Combination of Unitaries
• Benchmarking Quantum Simulation of Chemical Hamiltonians using the Sorted-List Encoding
• Majorana string simulation of nonequilibrium dynamics in two-dimensional lattice fermion systems
• Double-bracket quantum algorithms for high-fidelity ground state preparation
• Resource-efficient Quantum Algorithms for Selected Hamiltonian Subspace Diagonalization
• Gate Efficient Composition of Hamiltonian Simulation and Block-Encoding with its Application on HUBO, Chemistry and Finite Difference Method
• Anomalous transport in U(1)-symmetric quantum circuits
• Fast-forwardability of Qubit-mapped Fermion models based on Cartan decomposition
• Towards Compact Wavefunctions from Quantum-Selected Configuration Interaction
• Toward Density Functional Theory on Quantum Computers?
• A Randomized Method for Simulating Lindblad Equations and Thermal State Preparation