Sample-based Hamiltonian and Lindbladian simulation: Non-asymptotic analysis of sample complexity

• URL: http://arxiv.org/abs/2412.02134v3
• Date: Mon, 29 Sep 2025 06:55:22 GMT
• Title: Sample-based Hamiltonian and Lindbladian simulation: Non-asymptotic analysis of sample complexity
• Abstract summary: We present detailed sample complexity analyses for Density matrix exponentiation (DME) and Wave matrix Lindbladization (WML)<n>Both algorithms are prototypical sample-based quantum algorithms.<n>We prove that WML is optimal for sample-based Lindbladian simulation whenever the Lindblad operator acts nontrivially.
• Score: 11.214304423266304
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Density matrix exponentiation (DME) is a quantum algorithm that processes multiple copies of a program state $\sigma$ to realize the Hamiltonian evolution $e^{-i \sigma t}$. Wave matrix Lindbladization (WML) similarly processes multiple copies of a program state $\psi_L$ in order to realize a Lindbladian evolution. Both algorithms are prototypical sample-based quantum algorithms and can be used for various quantum information processing tasks, including quantum principal component analysis, Hamiltonian simulation, and Lindbladian simulation. In this work, we present detailed sample complexity analyses for DME and sample-based Hamiltonian simulation, as well as for WML and sample-based Lindbladian simulation. In particular, we prove that the sample complexity of DME is no larger than $4t^2/\varepsilon$ for evolution time $t$ and imprecision level $\varepsilon$ quantified by the normalized diamond distance. We also establish a fundamental lower bound on the sample complexity of sample-based Hamiltonian simulation, which matches our DME sample complexity bound up to a constant multiplicative factor. Additionally, we prove that the sample complexity of WML is no larger than $3t^2d^2/\varepsilon$, where $d$ is the dimension of the space on which the Lindblad operator acts nontrivially, and we prove a lower bound of $10^{-4} t^2/\varepsilon$ on the sample complexity of sample-based Lindbladian simulation. These results prove that WML is optimal for sample-based Lindbladian simulation whenever the Lindblad operator acts nontrivially on a constant-sized system. Finally, we point out that the DME sample complexity analysis in [Kimmel et al., npj Quantum Information 3, 13 (2017)] and the WML sample complexity analysis in [Patel and Wilde, Open Systems \& Information Dynamics 30, 2350010 (2023)] appear to be incomplete, highlighting the need for the results presented here.

Related papers

• Improved sample complexity bound for sample-based Lindbladian simulation [10.583368233681378]
  We establish improved sample-complexity bounds for sample-based Lindbladian simulation based on the Wave Matrix Lindbladization (WML) algorithm.<n>For a jump operator $L$ with dimension $d$, we derive an explicit non-asymptotic sample complexity bound $n_d*(t,varepsilon) le left( frac2d+38 right) |L|_infty2 left( fract2varepsilon right)
  arXiv  Detail & Related papers  (2026-05-28T17:46:25Z)
• Quantum algorithms based on quantum trajectories [0.4870012761464388]
  We show that the additive complexity of $O(T + log(1/epsilon))$ is reachable for the simulation of a large class of Lindbladian.<n>In this work we show that the additive complexity of $O(T + log(1/epsilon))$ is reachable for the simulation of a large class of Lindbladian by constructing a novel quantum algorithm based on quantum trajectories.
  arXiv  Detail & Related papers  (2025-09-12T17:27:25Z)
• Reducing Circuit Depth in Lindblad Simulation via Step-Size Extrapolation [2.847280100380157]
  We study algorithmic error mitigation via Richardson-style extrapolation for quantum simulations of open quantum systems modelled by the Lindblad equation.<n>We show that an extrapolator reduces the maximum circuit depth needed for accuracy $varepsilon$ from $mathcalO ((lT)2/varepsilon)$ to polylogarithmic $mathcalO ((lT)2/varepsilon)$ scaling.
  arXiv  Detail & Related papers  (2025-07-30T02:56:07Z)
• The Generative Leap: Sharp Sample Complexity for Efficiently Learning Gaussian Multi-Index Models [71.5283441529015]
  In this work we consider generic Gaussian Multi-index models, in which the labels only depend on the (Gaussian) $d$-dimensional inputs through their projection onto a low-dimensional $r = O_d(1)$ subspace.<n>We introduce the generative leap exponent $kstar$, a natural extension of the generative exponent from [Damian et al.'24] to the multi-index setting.
  arXiv  Detail & Related papers  (2025-06-05T18:34:56Z)
• Phase estimation with partially randomized time evolution [36.989845156791525]
  Quantum phase estimation combined with Hamiltonian simulation is the most promising algorithmic framework to computing ground state energies on quantum computers. In this paper we use randomization to speed up product formulas, one of the standard approaches to Hamiltonian simulation. We perform a detailed resource estimate for single-ancilla phase estimation using partially randomized product formulas for benchmark systems in quantum chemistry.
  arXiv  Detail & Related papers  (2025-03-07T18:09:32Z)
• Parallel simulation for sampling under isoperimetry and score-based diffusion models [56.39904484784127]
  As data size grows, reducing the iteration cost becomes an important goal. Inspired by the success of the parallel simulation of the initial value problem in scientific computation, we propose parallel Picard methods for sampling tasks. Our work highlights the potential advantages of simulation methods in scientific computation for dynamics-based sampling and diffusion models.
  arXiv  Detail & Related papers  (2024-12-10T11:50:46Z)
• A Randomized Method for Simulating Lindblad Equations and Thermal State Preparation [22.537918155387388]
  We study a qDRIFT-type randomized method to simulate Lindblad dynamics by decomposing its generator into an ensemble of Lindbladians.<n>We derive a new quantum Gibbs sampler algorithm that utilizes jump operators sampled from a Clifford-random circuit.
  arXiv  Detail & Related papers  (2024-07-09T06:55:19Z)
• Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
  We consider the problem of learning an $varepsilon$-optimal policy in a general class of continuous-space Markov decision processes (MDPs) having smooth Bellman operators. Key to our solution is a novel projection technique based on ideas from harmonic analysis. Our result bridges the gap between two popular but conflicting perspectives on continuous-space MDPs.
  arXiv  Detail & Related papers  (2024-05-10T09:58:47Z)
• Computational-Statistical Gaps in Gaussian Single-Index Models [77.1473134227844]
  Single-Index Models are high-dimensional regression problems with planted structure. We show that computationally efficient algorithms, both within the Statistical Query (SQ) and the Low-Degree Polynomial (LDP) framework, necessarily require $Omega(dkstar/2)$ samples.
  arXiv  Detail & Related papers  (2024-03-08T18:50:19Z)
• Efficient Quantum Lattice Gas Automata [0.0]
  The algorithm is composed of three main steps: collision, mapping, and propagation. Despite the impact of noise, our findings indicate that accurate simulations could be achieved already on current noisy devices.
  arXiv  Detail & Related papers  (2024-02-26T11:12:35Z)
• A Multi-Grained Symmetric Differential Equation Model for Learning Protein-Ligand Binding Dynamics [73.35846234413611]
  In drug discovery, molecular dynamics (MD) simulation provides a powerful tool for predicting binding affinities, estimating transport properties, and exploring pocket sites. We propose NeuralMD, the first machine learning (ML) surrogate that can facilitate numerical MD and provide accurate simulations in protein-ligand binding dynamics. We demonstrate the efficiency and effectiveness of NeuralMD, achieving over 1K$times$ speedup compared to standard numerical MD simulations.
  arXiv  Detail & Related papers  (2024-01-26T09:35:17Z)
• Quantum Simulation of Lindbladian Dynamics via Repeated Interactions [0.5097809301149342]
  We make use of an approximate correspondence between Lindbladian dynamics and evolution based on Repeated Interaction (RI) CPTP maps.<n>We show that the number of interactions needed to simulate the Liouvillian $etmathcalL$ within error $epsilon$ scales in a weak coupling limit.
  arXiv  Detail & Related papers  (2023-12-08T21:17:16Z)
• Wave Matrix Lindbladization I: Quantum Programs for Simulating Markovian Dynamics [6.345523830122166]
  Density Matrix Exponentiation is a technique for simulating Hamiltonian dynamics when the Hamiltonian to be simulated is available as a quantum state. We present a natural analogue to this technique, for simulating Markovian dynamics governed by the well known Lindblad master equation. We propose a quantum algorithm for this task, called Wave Matrix Lindbladization, and we also investigate its sample complexity.
  arXiv  Detail & Related papers  (2023-07-27T15:22:04Z)
• Importance sampling for stochastic quantum simulations [68.8204255655161]
  We introduce the qDrift protocol, which builds random product formulas by sampling from the Hamiltonian according to the coefficients. We show that the simulation cost can be reduced while achieving the same accuracy, by considering the individual simulation cost during the sampling stage. Results are confirmed by numerical simulations performed on a lattice nuclear effective field theory.
  arXiv  Detail & Related papers  (2022-12-12T15:06:32Z)
• Robustly learning the Hamiltonian dynamics of a superconducting quantum processor [0.5564835829075486]
  We robustly estimate the free Hamiltonian parameters of bosonic excitations in a superconducting-qubit analog quantum simulator. Our results constitute an accurate implementation of a dynamical quantum simulation.
  arXiv  Detail & Related papers  (2021-08-18T18:01:01Z)
• Parallel Quantum Algorithm for Hamiltonian Simulation [9.680246554758343]
  A parallel quantum algorithm is proposed for simulating the dynamics of a large class of Hamiltonians. The running time of our parallel quantum simulation algorithm measured by the quantum circuit depth has a doubly (poly-)logarithmic dependence. We show that the total gate depth of our algorithm has a $operatornamepolyloglog (1/epsilon)$ dependence in the parallel setting.
  arXiv  Detail & Related papers  (2021-05-25T12:46:33Z)
• Fixed Depth Hamiltonian Simulation via Cartan Decomposition [59.20417091220753]
  We present a constructive algorithm for generating quantum circuits with time-independent depth. We highlight our algorithm for special classes of models, including Anderson localization in one dimensional transverse field XY model. In addition to providing exact circuits for a broad set of spin and fermionic models, our algorithm provides broad analytic and numerical insight into optimal Hamiltonian simulations.
  arXiv  Detail & Related papers  (2021-04-01T19:06:00Z)
• Spectral Analysis of Product Formulas for Quantum Simulation [0.0]
  We show that the Trotter step size needed to estimate an energy eigenvalue within precision can be improved in scaling from $epsilon$ to $epsilon1/2$ for a large class of systems. Results partially generalize to diabatic processes, which remain in a narrow energy band separated from the rest of the spectrum by a gap.
  arXiv  Detail & Related papers  (2021-02-25T03:17:25Z)
• Revisiting the Sample Complexity of Sparse Spectrum Approximation of Gaussian Processes [60.479499225746295]
  We introduce a new scalable approximation for Gaussian processes with provable guarantees which hold simultaneously over its entire parameter space. Our approximation is obtained from an improved sample complexity analysis for sparse spectrum Gaussian processes (SSGPs)
  arXiv  Detail & Related papers  (2020-11-17T05:41:50Z)
• Model-Independent Simulation Complexity of Complex Quantum Dynamics [0.13999481573773068]
  We present a model-independent measure of dynamical complexity based on simulating complex quantum dynamics using stroboscopic Markovian dynamics. Tools from classical signal processing enable us to infer the Hilbert space dimension of a complex quantum system evolving under a time-independent Hamiltonian.
  arXiv  Detail & Related papers  (2020-09-01T14:52:35Z)
• State preparation and measurement in a quantum simulation of the O(3) sigma model [65.01359242860215]
  We show that fixed points of the non-linear O(3) sigma model can be reproduced near a quantum phase transition of a spin model with just two qubits per lattice site. We apply Trotter methods to obtain results for the complexity of adiabatic ground state preparation in both the weak-coupling and quantum-critical regimes. We present and analyze a quantum algorithm based on non-unitary randomized simulation methods.
  arXiv  Detail & Related papers  (2020-06-28T23:44:12Z)
• Quantum Algorithms for Simulating the Lattice Schwinger Model [63.18141027763459]
  We give scalable, explicit digital quantum algorithms to simulate the lattice Schwinger model in both NISQ and fault-tolerant settings. In lattice units, we find a Schwinger model on $N/2$ physical sites with coupling constant $x-1/2$ and electric field cutoff $x-1/2Lambda$. We estimate observables which we cost in both the NISQ and fault-tolerant settings by assuming a simple target observable---the mean pair density.
  arXiv  Detail & Related papers  (2020-02-25T19:18:36Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.