The algorithmic error of digital quantum simulations is usually explored in terms of the spectral norm distance between the actual and ideal evolution operators. In practice, this worst-case error analysis may be unnecessarily pessimistic. To address this, we develop a theory of average-case performance of Hamiltonian simulation with random initial states. We relate the average-case error to the Frobenius norm of the multiplicative error and give upper bounds for the product formula (PF) and truncated Taylor series methods. As applications, we estimate average-case error for the digital Hamiltonian simulation of general lattice Hamiltonians and k-local Hamiltonians. In particular, for the nearest-neighbor Heisenberg chain with n spins, the error is quadratically reduced from O(n) in the worst case to O(sqrt[n]) on average for both the PF method and the Taylor series method. Numerical evidence suggests that this theory accurately characterizes the average error for concrete models. We also apply our results to error analysis in the simulation of quantum scrambling.
The algorithmic error of digital quantum simulations is usually explored in terms of the spectral norm distance between the actual and ideal evolution operators. In practice, this worst-case error analysis may be unnecessarily pessimistic. To address this, we develop a theory of average-case performance of Hamiltonian simulation with random initial states. We relate the average-case error to the Frobenius norm of the multiplicative error and give upper bounds for the product formula (PF) and truncated Taylor series methods. As applications, we estimate average-case error for the digital Hamiltonian simulation of general lattice Hamiltonians and k-local Hamiltonians. In particular, for the nearest-neighbor Heisenberg chain with n spins, the error is quadratically reduced from O(n) in the worst case to O(sqrt[n]) on average for both the PF method and the Taylor series method. Numerical evidence suggests that this theory accurately characterizes the average error for concrete models. We also apply our results to error analysis in the simulation of quantum scrambling.
Hamiltonian simulation is a central application of quantum computing. Randomized Hamiltonian simulation approximates the target dynamics by sampling quantum circuits and often allows simpler circuit implementations. We develop a framework for randomized Hamiltonian simulation in which Hamiltonian terms are sampled with arbitrary probabilities and the corresponding short-time evolutions are implemented sequentially. The leading channel error relative to ideal time evolution is governed by the variance of the sampled generators. Minimizing the variance-based upper bound on the worst-case error recovers qDRIFT, a leading randomized Hamiltonian simulation algorithm that samples terms in proportion to their operator norms. For typical input states, however, this sampling distribution need not be optimal. Minimizing Haar-averaged error bounds instead yields sampling probabilities proportional to the Hilbert-Schmidt norms of the terms. This choice can provide smaller average-error bounds than conventional qDRIFT. For Hamiltonians expressed as sums of Pauli strings, we combine this framework with commuting Pauli grouping to obtain smaller error bounds than conventional qDRIFT at fixed Rz depth. Numerical benchmarks for the Sachdev-Ye-Kitaev model show error-bound improvement factors consistent with linear scaling in the number of qubits. For the 108-qubit FeMoco Hamiltonian, the error bounds are reduced by a factor of about 5.65. These results establish average-error optimization as a practical design principle for randomized Hamiltonian simulation.
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 speedup 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.
Simulating the Hamiltonian dynamics of quantum systems is one of the most promising applications of digital quantum computers. In this dissertation, we develop an understanding of quantum simulation algorithms concerning their design, analysis, implementation, and application. We implement three leading simulation algorithms, employing diverse techniques to tighten their error analyses and optimize circuit implementations. We produce concrete resource estimates for simulating a Heisenberg spin system, a problem arising in condensed matter physics that is otherwise difficult to solve on a classical computer. The resulting circuits are orders of magnitude smaller than those for the simplest classically-infeasible instances of factoring and quantum chemistry, suggesting the simulation of spin systems as a promising candidate for an early demonstration of practical quantum computation. We design new simulation algorithms by using classical randomness. We show that by simply randomizing how the terms in the Hamiltonian are ordered, one can prove stronger bounds for product formulas and thereby give more efficient quantum simulations. We also develop a classical sampler for time-dependent Hamiltonians, using which we give a simulation algorithm that substantially improves over previous approaches when the Hamiltonian varies significantly with time. We propose a general theory to analyzing product formulas, an approach to quantum simulation widely used in experimental demonstrations but whose error scaling was poorly understood. Our approach directly exploits the commutativity of Hamiltonian, overcoming the limitations of prior error analyses. We prove new speedups of product formulas for simulating many quantum systems, including simulations of nearest-neighbor lattice systems, second-quantized plane-wave electronic structure, k-local Hamiltonians, rapidly decaying power-law interactions, and clustered Hamiltonians, nearly matching or even outperforming the best previous results in quantum simulation. We accompany our analysis with numerical calculation, which suggests that the bounds also have nearly tight constant prefactors. We identify applications of quantum simulation to designing other quantum algorithms and improving quantum Monte Carlo methods. We develop an algorithmic framework ``quantum singular value transformation'' using techniques from quantum simulation and apply it to implement principal component regression. We also apply our new analysis of product formulas and obtain improved quantum Monte Carlo simulations of the transverse field Ising model and quantum ferromagnets.
Trotter product formulas are a leading approach for Hamiltonian simulation on quantum computers, yet their practical performance has remained difficult to assess due to the challenge of accurately estimating the Trotter error. In this work, we develop new theoretical results, algorithms, and software tools that advance the state-of-the-art in Trotter error estimation by orders of magnitude in both scale and accuracy. On the theoretical side, we prove that in the asymptotic limit the error of a product formula depends on the diagonal elements of the Baker-Campbell-Hausdorff (BCH) error operator in the eigenbasis of the Hamiltonian, rather than its full spectral norm -- yielding an improved scaling for Hamiltonian simulation using product formulas. On the algorithmic side, we introduce a compact representation of the BCH expansion that reduces the number of commutators from O(n3) to O(n) for second-order, and from O(n5) to O(n2) for fourth-order formulas on n fragments, complemented by an importance sampling scheme to further reduce the computational cost. We provide implementations of these techniques in software and demonstrate their power on two applications: (i) X-ray absorption spectroscopy of an electronic Hamiltonian (Li4Mn2O) at up to 56 qubits using tensor networks; and (ii) vibronic dynamics of naphthalene at over 100 qubits using ML-MCTDH, where we find that naive analytical bounds overestimate the required number of Trotter steps by nearly five orders of magnitude. Our framework enables, for the first time, the accurate estimation of Trotter error at practically relevant system sizes, providing a foundation for fair algorithmic comparisons and rational design of product formulas.
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. This work provides a comprehensive analysis of 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 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. If the observable is also fixed, the same random evolution provides an even shorter product formula. The proofs depend on concentration inequalities for vector and matrix martingales. Numerical experiments verify the theoretical predictions.
Randomized quantum algorithms have been proposed for quantum linear algebra with the goal of constructing shallower circuits than methods based on block encodings, and have been speculated to offer benefits in the early fault-tolerant era. In this work, we derive explicit, non-asymptotic error bounds on every algorithmic parameter of a randomized quantum linear systems solver that combines sampling from a Fourier series with Hamiltonian simulation, and confirm these bounds numerically. We show that even a 4×4 instance with condition number κ=100 requires on the order of 1015 non-Clifford gates to converge, calling into question the practicality of such randomized schemes. Comparing the two Hamiltonian-simulation kernels, product formulas (PFs) and the random Taylor expansion (RTE), both our analytical bounds and experiments show RTE reaches a given target error with roughly an order of magnitude smaller total gate budget, although neither is practical. Our analysis bridges asymptotic proposals and hardware implementation.