Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2409.04161

Classical Algorithms for Hamiltonian Dynamics Mean Value and Guided Local Hamiltonian Problem

Yusen Wu, Yukun Zhang, Wang, Chuan, Xiao Yuan

Published Sep 6, 2024• 8 citations
arXivHTMLPDF

Abstract

The efficient simulation of quantum dynamics and ground states is a central challenge in physics and a key frontier for quantum advantage. While short-time evolution in one-dimensional systems can often be simulated classically, extending this to higher dimensions remains difficult. Here, we introduce an efficient classical algorithm for simulating the short-time dynamics of arbitrary local quantum systems. For any local Hamiltonian $H$ and constant evolution time $t$, our method estimates expectation values of the form $\langleψ|e^{iHt}Oe^{-iHt}|ψ\rangle$ for global Pauli observables $O$ and stabilizer states $|ψ\rangle$, with high precision and exponentially small failure probability. Furthermore, we present a classical dequantization of a tailored quantum algorithm that efficiently solves the guided local Hamiltonian (GLH) problem to constant additive error - previously considered classically hard and hence a promising candidate for quantum computational advantage. These results reveal unexpected classical tractability in constant-time quantum dynamics and fundamental connections between Hamiltonian dynamics mean value and the GLH problem. Our work refines the boundary between classical and quantum computational power, identifying sharper criteria for regimes where quantum advantage may genuinely emerge.

DOI
10.48550/arxiv.2409.04161

Related papers

Classical Algorithms for Constant Approximation of the Ground State Energy of Local Hamiltonians

François Le Gall

We construct classical algorithms computing an approximation of the ground state energy of an arbitrary $k$-local Hamiltonian acting on $n$ qubits. We first consider the setting where a good ``guiding state'' is available, which is the main setting where quantum algorithms are expected to achieve an exponential speedup over classical methods. We show that a constant approximation (i.e., an approximation with constant relative accuracy) of the ground state energy can be computed classically in $\mathrm{poly}\left(1/χ,n\right)$ time and $\mathrm{poly}(n)$ space, where $χ$ denotes the overlap between the guiding state and the ground state (as in prior works in dequantization, we assume sample-and-query access to the guiding state). This gives a significant improvement over the recent classical algorithm by Gharibian and Le Gall (SICOMP 2023), and matches (up a to polynomial overhead) both the time and space complexities of quantum algorithms for constant approximation of the ground state energy. We also obtain classical algorithms for higher-precision approximation. For the setting where no guided state is given (i.e., the standard version of the local Hamiltonian problem), we obtain a classical algorithm computing a constant approximation of the ground state energy in $2^{O(n)}$ time and $\mathrm{poly}(n)$ space. To our knowledge, before this work it was unknown how to classically achieve these bounds simultaneously, even for constant approximation. We also discuss complexity-theoretic aspects of our results.

arXiv:2410.21833•Leibniz international proceedings in informatics•Oct 29, 2024•7 citations

Classical Algorithm for the Mean Value problem over Short-Time Hamiltonian Evolutions

Reyhaneh Aghaei Saem, Ali Hamed Moosavian

Simulating physical systems has been an important application of classical and quantum computers. In this article we present an efficient classical algorithm for simulating time-dependent quantum mechanical Hamiltonians over constant periods of time. The algorithm presented here computes the mean value of an observable over the output state of such short-time Hamiltonian evolutions. In proving the performance of this algorithm we use Lieb-Robinson type bounds to limit the evolution of local operators within a lightcone. This allows us to divide the task of simulating a large quantum system into smaller systems that can be handled on normal classical computers.

arXiv:2301.11420•Jan 26, 2023•1 citation

Classical Simulation of Short-Time Quantum Dynamics

Dominik S. Wild, Alvaro Martin Alhambra

Recent progress in the development of quantum technologies has enabled the direct investigation of the dynamics of increasingly complex quantum many-body systems.This motivates the study of the complexity of classical algorithms for this problem in order to benchmark quantum simulators and to delineate the regime of quantum advantage.Here, we present classical algorithms for approximating the dynamics of local observables and nonlocal quantities such as the Loschmidt echo, where the evolution is governed by a local Hamiltonian.For short times, their computational cost scales polynomially with the system size and the inverse of the approximation error.In the case of local observables, the proposed algorithm has a better dependence on the approximation error than algorithms based on the Lieb-Robinson bound.Our results use cluster-expansion techniques adapted to the dynamical setting, for which we give a novel proof of their convergence.This has important physical consequences besides our efficient algorithms.In particular, we establish a novel quantum speed limit, a bound on dynamical phase transitions, and a concentration bound for product states evolved for short times.

arXiv:2210.11490•PRX Quantum•Jun 12, 2023•42 citations

Complexity of the Guided Local Hamiltonian Problem: Improved Parameters and Extension to Excited States

Chris Cade, Marten Folkertsma, Gharibian, Sevag +4 more

Estimating the ground state energy of a local Hamiltonian is a central problem in quantum chemistry. In order to further investigate its complexity and the potential of quantum algorithms for quantum chemistry, Gharibian and Le Gall (STOC 2022) recently introduced the guided local Hamiltonian problem (GLH), which is a variant of the local Hamiltonian problem where an approximation of a ground state (which is called a guiding state) is given as an additional input. Gharibian and Le Gall showed quantum advantage (more precisely, BQP-completeness) for GLH with 6-local Hamiltonians when the guiding state has fidelity (inverse-polynomially) close to 1/2 with a ground state. In this paper, we optimally improve both the locality and the fidelity parameter: we show that the BQP-completeness persists even with 2-local Hamiltonians, and even when the guiding state has fidelity (inverse-polynomially) close to 1 with a ground state. Moreover, we show that the BQP-completeness also holds for 2-local physically motivated Hamiltonians on a 2D square lattice or a 2D triangular lattice. Beyond the hardness of estimating the ground state energy, we also show BQP-hardness persists when considering estimating energies of excited states of these Hamiltonians instead. Those make further steps towards establishing practical quantum advantage in quantum chemistry.

arXiv:2207.10097•Leibniz international proceedings in informatics•Jul 20, 2022•19 citations

Fast convergence of propagation algorithms for open quantum systems

Giorgio Facelli, Hamza Fawzi, Omar Fawzi +3 more

We establish general conditions for the rapid convergence of propagation algorithms for computing expectation values of local observables in quantum many-body systems, covering both spin and fermionic systems. Our results apply to evolutions that are sufficiently contractive, providing a general mechanism by which contractivity controls the growth generated by local interactions and enables efficient classical simulation. As a first application, we consider noisy time evolution generated by local Hamiltonians on arbitrary interaction graphs. We show that the dynamics can be efficiently simulated when the noise strength $λ$ is sufficiently large compared to the degree of the interaction graph. More generally, for systems with an interaction strength $u$, our bounds determine a time horizon $t_{\text{max}}$ as a function of the interaction strength $u$, the noise strength $λ$, and the interaction structure below which the algorithm is efficient. In the noiseless limit, $λ=0$, our analysis extends the efficiently simulable time scale from $\log(1/u)$ proved in Facelli, Fawzi, and Fawzi (2026) to $t_{\text{max}} \sim 1/u$ matching the recent improvement by Zhao, Marvian and Tong (2026). As a second application, we apply the same framework to the computation of local observables in Gibbs states of local Hamiltonians. We consider a pseudo-Lindbladian whose steady state is the Gibbs state and show that, at sufficiently high temperature, its propagation algorithm converges rapidly. In particular, for weakly-interacting systems with interaction strength $u$, our result applies up to inverse temperatures $β\sim\log(1/u)$.

quant-pharXiv:2610.06769•Oct 6, 2026•2 citations

Efficient Classical Simulation of Weakly Interacting Fermion Dynamics

Chu Zhao, Iman Marvian, Yu Tong

We consider the task of simulating the real-time dynamics of weakly interacting fermionic systems. In particular, we focus on computing the expectation value of a local observable $A$ at time $t$. By analyzing the convergence of the perturbative expansion in the interaction strength $λ$ for the Heisenberg-picture observable, we propose a polynomial-time algorithm for estimating this expectation value in the weakly interacting regime $λ|t|^{2D+1}=\mathcal{O}(1)$, when the Hamiltonian is geometrically local on a $D$-dimensional lattice. Importantly, this condition is independent of the system size. If the goal is instead to approximate the time-evolved observable in normalized Frobenius norm, we extend the convergence regime to $λ|t|=\mathcal{O}(1)$ with quasi-polynomial runtime. When the non-interacting part exhibits Anderson localization, our polynomial-time algorithm can be extended up to $λ|t|=\mathcal{O}(1)$, modulo polylogarithmic factors. Our algorithm brings together ideas from continuous-time QMC, diagrammatic QMC, and Majorana Propagation, but with a new Heisenberg-picture operator-growth analysis that makes the sampling complexity rigorously controllable. This leads to provably efficient classical algorithms in regimes where the interaction is weak enough that the sampling variance remains bounded independently of system size. Together, these results identify broad regimes in which weak interactions, locality, and localization can be leveraged to make real-time fermionic dynamics classically tractable.

quant-pharXiv:2608.19448•Aug 21, 2026•2 citations
The efficient simulation of quantum dynamics and ground states is a central challenge in physics and a key frontier for quantum advantage. While short-time evolution in one-dimensional systems can often be simulated classically, extending this to higher dimensions remains difficult. Here, we introduce an efficient classical algorithm for simulating the short-time dynamics of arbitrary local quantum systems. For any local Hamiltonian HHH and constant evolution time ttt, our method estimates expectation values of the form ⟨ψ∣eiHtOe−iHt∣ψ⟩\langleψ|e^{iHt}Oe^{-iHt}|ψ\rangle⟨ψ∣eiHtOe−iHt∣ψ⟩ for global Pauli observables OOO and stabilizer states ∣ψ⟩|ψ\rangle∣ψ⟩, with high precision and exponentially small failure probability. Furthermore, we present a classical dequantization of a tailored quantum algorithm that efficiently solves the guided local Hamiltonian (GLH) problem to constant additive error - previously considered classically hard and hence a promising candidate for quantum computational advantage. These results reveal unexpected classical tractability in constant-time quantum dynamics and fundamental connections between Hamiltonian dynamics mean value and the GLH problem. Our work refines the boundary between classical and quantum computational power, identifying sharper criteria for regimes where quantum advantage may genuinely emerge.
We construct classical algorithms computing an approximation of the ground state energy of an arbitrary kkk-local Hamiltonian acting on nnn qubits. We first consider the setting where a good ``guiding state'' is available, which is the main setting where quantum algorithms are expected to achieve an exponential speedup over classical methods. We show that a constant approximation (i.e., an approximation with constant relative accuracy) of the ground state energy can be computed classically in poly(1/χ,n)\mathrm{poly}\left(1/χ,n\right)poly(1/χ,n) time and poly(n)\mathrm{poly}(n)poly(n) space, where χχχ denotes the overlap between the guiding state and the ground state (as in prior works in dequantization, we assume sample-and-query access to the guiding state). This gives a significant improvement over the recent classical algorithm by Gharibian and Le Gall (SICOMP 2023), and matches (up a to polynomial overhead) both the time and space complexities of quantum algorithms for constant approximation of the ground state energy. We also obtain classical algorithms for higher-precision approximation. For the setting where no guided state is given (i.e., the standard version of the local Hamiltonian problem), we obtain a classical algorithm computing a constant approximation of the ground state energy in 2O(n)2^{O(n)}2O(n) time and poly(n)\mathrm{poly}(n)poly(n) space. To our knowledge, before this work it was unknown how to classically achieve these bounds simultaneously, even for constant approximation. We also discuss complexity-theoretic aspects of our results.
Simulating physical systems has been an important application of classical and quantum computers. In this article we present an efficient classical algorithm for simulating time-dependent quantum mechanical Hamiltonians over constant periods of time. The algorithm presented here computes the mean value of an observable over the output state of such short-time Hamiltonian evolutions. In proving the performance of this algorithm we use Lieb-Robinson type bounds to limit the evolution of local operators within a lightcone. This allows us to divide the task of simulating a large quantum system into smaller systems that can be handled on normal classical computers.
Recent progress in the development of quantum technologies has enabled the direct investigation of the dynamics of increasingly complex quantum many-body systems.This motivates the study of the complexity of classical algorithms for this problem in order to benchmark quantum simulators and to delineate the regime of quantum advantage.Here, we present classical algorithms for approximating the dynamics of local observables and nonlocal quantities such as the Loschmidt echo, where the evolution is governed by a local Hamiltonian.For short times, their computational cost scales polynomially with the system size and the inverse of the approximation error.In the case of local observables, the proposed algorithm has a better dependence on the approximation error than algorithms based on the Lieb-Robinson bound.Our results use cluster-expansion techniques adapted to the dynamical setting, for which we give a novel proof of their convergence.This has important physical consequences besides our efficient algorithms.In particular, we establish a novel quantum speed limit, a bound on dynamical phase transitions, and a concentration bound for product states evolved for short times.
Estimating the ground state energy of a local Hamiltonian is a central problem in quantum chemistry. In order to further investigate its complexity and the potential of quantum algorithms for quantum chemistry, Gharibian and Le Gall (STOC 2022) recently introduced the guided local Hamiltonian problem (GLH), which is a variant of the local Hamiltonian problem where an approximation of a ground state (which is called a guiding state) is given as an additional input. Gharibian and Le Gall showed quantum advantage (more precisely, BQP-completeness) for GLH with 6-local Hamiltonians when the guiding state has fidelity (inverse-polynomially) close to 1/2 with a ground state. In this paper, we optimally improve both the locality and the fidelity parameter: we show that the BQP-completeness persists even with 2-local Hamiltonians, and even when the guiding state has fidelity (inverse-polynomially) close to 1 with a ground state. Moreover, we show that the BQP-completeness also holds for 2-local physically motivated Hamiltonians on a 2D square lattice or a 2D triangular lattice. Beyond the hardness of estimating the ground state energy, we also show BQP-hardness persists when considering estimating energies of excited states of these Hamiltonians instead. Those make further steps towards establishing practical quantum advantage in quantum chemistry.
We establish general conditions for the rapid convergence of propagation algorithms for computing expectation values of local observables in quantum many-body systems, covering both spin and fermionic systems. Our results apply to evolutions that are sufficiently contractive, providing a general mechanism by which contractivity controls the growth generated by local interactions and enables efficient classical simulation. As a first application, we consider noisy time evolution generated by local Hamiltonians on arbitrary interaction graphs. We show that the dynamics can be efficiently simulated when the noise strength λλλ is sufficiently large compared to the degree of the interaction graph. More generally, for systems with an interaction strength uuu, our bounds determine a time horizon tmaxt_{\text{max}}tmax​ as a function of the interaction strength uuu, the noise strength λλλ, and the interaction structure below which the algorithm is efficient. In the noiseless limit, λ=0λ=0λ=0, our analysis extends the efficiently simulable time scale from log⁡(1/u)\log(1/u)log(1/u) proved in Facelli, Fawzi, and Fawzi (2026) to tmax∼1/ut_{\text{max}} \sim 1/utmax​∼1/u matching the recent improvement by Zhao, Marvian and Tong (2026). As a second application, we apply the same framework to the computation of local observables in Gibbs states of local Hamiltonians. We consider a pseudo-Lindbladian whose steady state is the Gibbs state and show that, at sufficiently high temperature, its propagation algorithm converges rapidly. In particular, for weakly-interacting systems with interaction strength uuu, our result applies up to inverse temperatures β∼log⁡(1/u)β\sim\log(1/u)β∼log(1/u).
We consider the task of simulating the real-time dynamics of weakly interacting fermionic systems. In particular, we focus on computing the expectation value of a local observable AAA at time ttt. By analyzing the convergence of the perturbative expansion in the interaction strength λλλ for the Heisenberg-picture observable, we propose a polynomial-time algorithm for estimating this expectation value in the weakly interacting regime λ∣t∣2D+1=O(1)λ|t|^{2D+1}=\mathcal{O}(1)λ∣t∣2D+1=O(1), when the Hamiltonian is geometrically local on a DDD-dimensional lattice. Importantly, this condition is independent of the system size. If the goal is instead to approximate the time-evolved observable in normalized Frobenius norm, we extend the convergence regime to λ∣t∣=O(1)λ|t|=\mathcal{O}(1)λ∣t∣=O(1) with quasi-polynomial runtime. When the non-interacting part exhibits Anderson localization, our polynomial-time algorithm can be extended up to λ∣t∣=O(1)λ|t|=\mathcal{O}(1)λ∣t∣=O(1), modulo polylogarithmic factors. Our algorithm brings together ideas from continuous-time QMC, diagrammatic QMC, and Majorana Propagation, but with a new Heisenberg-picture operator-growth analysis that makes the sampling complexity rigorously controllable. This leads to provably efficient classical algorithms in regimes where the interaction is weak enough that the sampling variance remains bounded independently of system size. Together, these results identify broad regimes in which weak interactions, locality, and localization can be leveraged to make real-time fermionic dynamics classically tractable.