Randomizing multi-product formulas for Hamiltonian simulation

Abstract

Quantum simulation, the simulation of quantum processes on quantum computers, suggests a path forward for the efficient simulation of problems in condensed-matter physics, quantum chemistry, and materials science. While the majority of quantum simulation algorithms are deterministic, a recent surge of ideas has shown that randomization can greatly benefit algorithmic performance. In this work, we introduce a scheme for quantum simulation that unites the advantages of randomized compiling on the one hand and higher-order multi-product formulas, as they are used for example in linear-combination-of-unitaries (LCU) algorithms or quantum error mitigation, on the other hand. In doing so, we propose a framework of randomized sampling that is expected to be useful for programmable quantum simulators and present two new multi-product formula algorithms tailored to it. Our framework reduces the circuit depth by circumventing the need for oblivious amplitude amplification required by the implementation of multi-product formulas using standard LCU methods, rendering it especially useful for early quantum computers used to estimate the dynamics of quantum systems instead of performing full-fledged quantum phase estimation. Our algorithms achieve a simulation error that shrinks exponentially with the circuit depth. To corroborate their functioning, we prove rigorous performance bounds as well as the concentration of the randomized sampling procedure. We demonstrate the functioning of the approach for several physically meaningful examples of Hamiltonians, including fermionic systems and the Sachdev-Ye-Kitaev model, for which the method provides a favorable scaling in the effort.

arXiv comment24 pages, 6 figures

References in corpus (27)

• Quantum Computing in the NISQ era and beyond
• Predicting Many Properties of a Quantum System from Very Few Measurements
• Probing the relaxation towards equilibrium in an isolated strongly correlated 1D Bose gas
• Hamiltonian Simulation by Qubitization
• Simulating Hamiltonian dynamics with a truncated Taylor series
• Efficient quantum algorithms for simulating sparse Hamiltonians
• The European Quantum Technologies Roadmap
• Toward the first quantum simulation with quantum speedup
• Hybrid quantum-classical algorithms and quantum error mitigation
• A Theory of Trotter Error
• Hamiltonian simulation with nearly optimal dependence on all parameters
• A random compiler for fast Hamiltonian simulation
• Quantum simulation of time-dependent Hamiltonians and the convenient illusion of Hilbert space
• Exponential improvement in precision for simulating sparse Hamiltonians
• Nearly optimal lattice simulation by product formulas
• Faster quantum simulation by randomization
• Higher Order Decompositions of Ordered Operator Exponentials
• A dissipative quantum Church-Turing theorem
• Digital-Analog Quantum Computation
• Simulating Quantum Dynamics On A Quantum Computer
• Quantum Simulation of the Sachdev-Ye-Kitaev Model by Asymmetric Qubitization
• Concentration for random product formulas
• Shorter gate sequences for quantum computing by mixing unitaries
• Digital quantum simulation of many-body non-Markovian dynamics
• Compilation by stochastic Hamiltonian sparsification
• Hamiltonian operator approximation for energy measurement and ground state preparation
• Adiabatic Quantum State Generation and Statistical Zero Knowledge

Cited by in corpus (31)

• Variational Hamiltonian simulation for translational invariant systems via classical pre-processing
• Implementing any Linear Combination of Unitaries on Intermediate-term Quantum Computers
• Well-conditioned multi-product formulas for hardware-friendly Hamiltonian simulation
• qSWIFT: High-order randomized compiler for Hamiltonian simulation
• Hybrid Oscillator-Qubit Quantum Processors: Instruction Set Architectures, Abstract Machine Models, and Applications
• Error-resilient Monte Carlo quantum simulation of imaginary time
• Composite Quantum Simulations
• Qubit-Efficient Randomized Quantum Algorithms for Linear Algebra
• Importance sampling for stochastic quantum simulations
• Continuous Hamiltonian dynamics on digital quantum computers without discretization error
• Quantum error mitigation for Fourier moment computation
• Hardware-Tailored Diagonalization Circuits
• Simple and high-precision Hamiltonian simulation by compensating Trotter error with linear combination of unitary operations
• Measurement-efficient quantum Krylov subspace diagonalisation
• Algorithm-Oriented Qubit Mapping for Variational Quantum Algorithms
• Calculating the many-body density of states on a digital quantum computer
• Early Fault-Tolerant Quantum Algorithms in Practice: Application to Ground-State Energy Estimation
• Parallel Quantum Algorithm for Hamiltonian Simulation
• Improving the Performance of Digitized Counterdiabatic Quantum Optimization via Algorithm-Oriented Qubit Mapping
• Block encoding bosons by signal processing
• In the shadow of the Hadamard test: Using the garbage state for good and further modifications
• Quantum techniques for eigenvalue problems
• Power of quantum measurement in simulating unphysical operations
• Quantum many-body simulation of finite-temperature systems with sampling a series expansion of a quantum imaginary-time evolution
• On the commutator scaling in Hamiltonian simulation with multi-product formulas
• Short-time simulation of quantum dynamics by Pauli measurements
• Co-Designing Spectral Transformation Oracles with Hybrid Oscillator-Qubit Quantum Processors: From Algorithms to Compilation
• Tight bound for the total time in digital-analog quantum computation
• Data-Efficient Quantum Noise Modeling via Machine Learning
• Quantum Simulation via Stochastic Combination of Unitaries
• Unitary-transformed projective squeezing: applications for circuit-knitting and state-preparation of non-Gaussian states