Concentration for random product formulas

Abstract

Quantum simulation has wide applications in quantum chemistry and physics. Recently, scientists have begun exploring the use of randomized methods for accelerating quantum simulation. Among them, a simple and powerful technique, called qDRIFT, is known to generate random product formulas for which the average quantum channel approximates the ideal evolution. qDRIFT achieves a gate count that does not explicitly depend on the number of terms in the Hamiltonian, which contrasts with Suzuki formulas. This work aims to understand the origin of this speed-up by comprehensively analyzing a single realization of the random product formula produced by qDRIFT. The main results prove that a typical realization of the randomized product formula approximates the ideal unitary evolution up to a small diamond-norm error. The gate complexity is already independent of the number of terms in the Hamiltonian, but it depends on the system size and the sum of the interaction strengths in the Hamiltonian. Remarkably, the same random evolution starting from an arbitrary, but fixed, input state yields a much shorter circuit suitable for that input state. In contrast, in deterministic settings, such an improvement usually requires initial state knowledge. The proofs depend on concentration inequalities for vector and matrix martingales, and the framework is applicable to other randomized product formulas. Our bounds are saturated by certain commuting Hamiltonians.

27 pages, 6 figures

References in corpus (29)

• Quantum Simulation
• Comments on the Sachdev-Ye-Kitaev model
• Quantum computational chemistry
• Hamiltonian Simulation by Qubitization
• Optimal Hamiltonian Simulation by Quantum Signal Processing
• User-friendly tail bounds for sums of random matrices
• The Spectrum in the Sachdev-Ye-Kitaev Model
• Recovering low-rank matrices from few coefficients in any basis
• Towards the fast scrambling conjecture
• Hamiltonian simulation with nearly optimal dependence on all parameters
• A Grand Unification of Quantum Algorithms
• A random compiler for fast Hamiltonian simulation
• Even more efficient quantum computations of chemistry through tensor hypercontraction
• Low Depth Quantum Simulation of Electronic Structure
• Quantum algorithms for systems of linear equations inspired by adiabatic quantum computing
• Faster quantum simulation by randomization
• Concentration of the adjacency matrix and of the Laplacian in random graphs with independent edges
• Time-dependent Hamiltonian simulation with $L^1$-norm scaling
• Hamiltonian simulation in the low-energy subspace
• Quantum Simulation of the Sachdev-Ye-Kitaev Model by Asymmetric Qubitization
• Near-term quantum algorithms for linear systems of equations
• Shorter gate sequences for quantum computing by mixing unitaries
• Compilation by stochastic Hamiltonian sparsification
• Operator growth bounds from graph theory
• Optimal Frobenius light cone in spin chains with power-law interactions
• Quantum linear system solver based on time-optimal adiabatic quantum computing and quantum approximate optimization algorithm
• Matrix Concentration for Products
• Concentration of OTOC and Lieb-Robinson velocity in random Hamiltonians
• On Concentration Inequalities for Random Matrix Products

Cited by in corpus (24)

• Generalization in quantum machine learning from few training data
• Learning many-body Hamiltonians with Heisenberg-limited scaling
• 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
• Hamiltonian simulation with random inputs
• Variational Hamiltonian simulation for translational invariant systems via classical pre-processing
• Randomizing multi-product formulas for Hamiltonian simulation
• 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
• On the complexity of implementing Trotter steps
• Low-depth Hamiltonian Simulation by Adaptive Product Formula
• Composite Quantum Simulations
• Importance sampling for stochastic quantum simulations
• Efficient quantum imaginary time evolution by drifting real time evolution: an approach with low gate and measurement complexity
• A stochastic quantum Krylov protocol with double factorized Hamiltonians
• Average-case Speedup for Product Formulas
• Quantum differential equation solvers: limitations and fast-forwarding
• Co-Design quantum simulation of nanoscale NMR
• Doubling the order of approximation via the randomized product formula
• Simple and high-precision Hamiltonian simulation by compensating Trotter error with linear combination of unitary operations
• Parallel Quantum Algorithm for Hamiltonian Simulation
• Digital quantum simulation of non-perturbative dynamics of open systems with orthogonal polynomials