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:2601.05226

Fast convergence of Majorana Propagation for weakly interacting fermions

Giorgio Facelli, Hamza Fawzi, Omar Fawzi

quant-phSubmitted Jan 8, 2026• Announced Jan 9, 2026• 0 citations
v1 · Jan 8, 2026v2 · Sep 7, 2026
arXivHTMLPDF

Abstract

Simulating the time dynamics of an observable under Hamiltonian evolution is one of the most promising candidates for quantum advantage as we do not expect efficient classical algorithms for this problem except in restricted settings. Here, we introduce such a setting by showing that Majorana Propagation, a simple algorithm combining Trotter steps and truncations, efficiently finds a low-degree approximation of the time-evolved observable as soon as such an approximation exists. This provides the first provable guarantee about Majorana Propagation for Hamiltonian evolution. As an application of this result, we prove that Majorana Propagation can efficiently simulate the time dynamics of any sparse quartic Hamiltonian up to time $t_{\text{max}}(u)$ depending on the interaction strength $u$. For a time horizon $t \leq t_{\text{max}}(u)$, the runtime of the algorithm is $N^{O(\log(t/\varepsilon))}$ where $N$ is the number of Majorana modes and $\varepsilon$ is the error measured in the normalized Frobenius norm. Importantly, in the limit of small $u$, $t_{\text{max}}(u)$ goes to $+\infty$, formalizing the intuition that the algorithm is accurate at all times when the Hamiltonian is quadratic.

Comments
22 pages, 2 figures

Related papers

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•0 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•0 citations

Majorana string simulation of nonequilibrium dynamics in two-dimensional lattice fermion systems

Matteo D'Anna, Jannes Nys, Juan Carrasquilla

The study of real-time dynamics of fermions remains one of the last frontiers beyond the reach of classical simulations and is key to our understanding of quantum behavior in chemistry and materials, with implications for quantum technology. Here we introduce a Heisenberg-picture algorithm that propagates observables expressed in a Majorana-string basis using a truncation scheme that preserves Trotter accuracy and aims at maintaining computational efficiency. The framework is exact for quadratic Hamiltonians -- remaining restricted to a fixed low-weight sector determined by the physical observable -- admits variational initial states, and can be extended to interacting regimes via systematically controlled truncations. We benchmark our approach on one- and two-dimensional Fermi-Hubbard quenches, comparing against tensor network methods (MPS and fPEPS) and recent experimental data. The method achieves high accuracy on timescales comparable to state-of-the-art variational techniques and experiments, demonstrating that controlled Majorana-string truncation is a practical tool for simulating two-dimensional fermionic dynamics.

cond-mat.quant-gasCross-listedarXiv:2511.02809•Physical review. B./Physical review. B•Nov 5, 2025•0 citations

Optimizing sparse fermionic Hamiltonians

Yaroslav Herasymenko, Maarten Stroeks, Jonas Helsen +1 more

We consider the problem of approximating the ground state energy of a fermionic Hamiltonian using a Gaussian state. In sharp contrast to the dense case [1, 2], we prove that strictly q -local sparse fermionic Hamiltonians have a constant Gaussian approximation ratio; the result holds for any connectivity and interaction strengths. Sparsity means that each fermion participates in a bounded number of interactions, and strictly q -local means that each term involves exactly q fermionic (Majorana) operators. We extend our proof to give a constant Gaussian approximation ratio for sparse fermionic Hamiltonians with both quartic and quadratic terms. With additional work, we also prove a constant Gaussian approximation ratio for the so-called sparse SYK model with strictly 4 -local interactions (sparse SYK- 4 model). In each setting we show that the Gaussian state can be efficiently determined. Finally, we prove that the O(n−1/2) Gaussian approximation ratio for the normal (dense) SYK- 4 model extends to SYK- q for even q>4 , with an approximation ratio of O(n1/2–q/4) . Our results identify non-sparseness as the prime reason that the SYK- 4 model can fail to have a constant approximation ratio [1, 2].

arXiv:2211.16518•Quantum•Aug 10, 2023•16 citations

Trotterization with Many-body Coulomb Interactions: Convergence for General Initial Conditions and State-Dependent Improvements

Di Fang, Xiaoxu Wu

Efficiently simulating many-body quantum systems with Coulomb interactions is a fundamental question in quantum physics, quantum chemistry, and quantum computing, yet it presents unique challenges: the Hamiltonian is an unbounded operator; its Hilbert space dimension grows exponentially with particle number; and the Coulomb potential is singular, long-ranged, and non-smooth, violating the regularity assumptions of many prior state-of-the-art many-body simulation analyses. In this work, we establish rigorous error bounds for Trotter formulas applied to these systems. Our first main result shows that for general initial conditions in the domain of the Hamiltonian, second-order Trotter achieves a $1/4$ convergence rate with explicit polynomial dependence of the error prefactor on the particle number. The polynomial dependence on system size suggests that the algorithm remains quantumly efficient, even without introducing any regularization of the Coulomb singularity. Such a worst-case rate has been observed in prior work for the hydrogen ground state, demonstrating its physical relevance. We further establish one-step local error lower bounds of order $5/4$ for both formulas, showing that the local exponent is sharp. Our second main result identifies a set of physically meaningful conditions on the initial state under which the convergence rates improve, with the full first-order and second-order rates recovered at sufficiently high angular momentum. Our theoretical findings are consistent with prior numerical observations. Our third main result establishes improved convergence rates for many-body fermionic Coulomb systems with initial data of different Sobolev regularity. In particular, even without imposing any additional regularity beyond the natural domain of the Hamiltonian, both the first- and second-order Trotter formulas converge with rate $1/2$, rather than the general $1/4$ rate.

quant-pharXiv:2604.07704•Apr 10, 2026•0 citations

Complexity of Implementing Trotter Steps

Guang Hao Low, Yuan Su, Yu Tong +1 more

Quantum dynamics can be simulated on a quantum computer by exponentiating elementary terms from the Hamiltonian in a sequential manner.However, such an implementation of Trotter steps has gate complexity depending on the total Hamiltonian term number, comparing unfavorably to algorithms using more advanced techniques.We develop methods to perform faster Trotter steps with complexity sublinear in the number of terms.We achieve this for a class of Hamiltonians whose interaction strength decays with distance according to power law.Our methods include one based on a recursive block encoding and one based on an average-cost simulation, overcoming the normalization-factor barrier of these advanced quantum simulation techniques.We also realize faster Trotter steps when certain blocks of Hamiltonian coefficients have low rank.Combining with a tighter error analysis, we show that it suffices to use η 1/3 n 1/3 + n 2/3 /η 2/3 n 1+o(1) gates to simulate uniform electron gas with n spin orbitals and η electrons in second quantization in real space, asymptotically improving over the best previous work.We obtain an analogous result when the external potential of nuclei is introduced under the Born-Oppenheimer approximation.We prove a circuit lower bound when the Hamiltonian coefficients take a continuum range of values, showing that generic n-qubit two-local Hamiltonians with commuting terms require at least (n 2 ) gates to evolve with accuracy = (1/poly(n)) for time t = ( ).Our proof is based on a gateefficient reduction from the approximate synthesis of diagonal unitaries within the Hamming weight-2 subspace, which may be of independent interest.Our result thus suggests the use of Hamiltonian structural properties as both necessary and sufficient to implement Trotter steps with lower gate complexity.

arXiv:2211.09133•PRX Quantum•May 9, 2023•29 citations
Simulating the time dynamics of an observable under Hamiltonian evolution is one of the most promising candidates for quantum advantage as we do not expect efficient classical algorithms for this problem except in restricted settings. Here, we introduce such a setting by showing that Majorana Propagation, a simple algorithm combining Trotter steps and truncations, efficiently finds a low-degree approximation of the time-evolved observable as soon as such an approximation exists. This provides the first provable guarantee about Majorana Propagation for Hamiltonian evolution. As an application of this result, we prove that Majorana Propagation can efficiently simulate the time dynamics of any sparse quartic Hamiltonian up to time tmax(u)t_{\text{max}}(u)tmax​(u) depending on the interaction strength uuu. For a time horizon t≤tmax(u)t \leq t_{\text{max}}(u)t≤tmax​(u), the runtime of the algorithm is NO(log⁡(t/ε))N^{O(\log(t/\varepsilon))}NO(log(t/ε)) where NNN is the number of Majorana modes and ε\varepsilonε is the error measured in the normalized Frobenius norm. Importantly, in the limit of small uuu, tmax(u)t_{\text{max}}(u)tmax​(u) goes to +∞+\infty+∞, formalizing the intuition that the algorithm is accurate at all times when the Hamiltonian is quadratic.
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.
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).
The study of real-time dynamics of fermions remains one of the last frontiers beyond the reach of classical simulations and is key to our understanding of quantum behavior in chemistry and materials, with implications for quantum technology. Here we introduce a Heisenberg-picture algorithm that propagates observables expressed in a Majorana-string basis using a truncation scheme that preserves Trotter accuracy and aims at maintaining computational efficiency. The framework is exact for quadratic Hamiltonians -- remaining restricted to a fixed low-weight sector determined by the physical observable -- admits variational initial states, and can be extended to interacting regimes via systematically controlled truncations. We benchmark our approach on one- and two-dimensional Fermi-Hubbard quenches, comparing against tensor network methods (MPS and fPEPS) and recent experimental data. The method achieves high accuracy on timescales comparable to state-of-the-art variational techniques and experiments, demonstrating that controlled Majorana-string truncation is a practical tool for simulating two-dimensional fermionic dynamics.
We consider the problem of approximating the ground state energy of a fermionic Hamiltonian using a Gaussian state. In sharp contrast to the dense case [1, 2], we prove that strictly q -local sparse fermionic Hamiltonians have a constant Gaussian approximation ratio; the result holds for any connectivity and interaction strengths. Sparsity means that each fermion participates in a bounded number of interactions, and strictly q -local means that each term involves exactly q fermionic (Majorana) operators. We extend our proof to give a constant Gaussian approximation ratio for sparse fermionic Hamiltonians with both quartic and quadratic terms. With additional work, we also prove a constant Gaussian approximation ratio for the so-called sparse SYK model with strictly 4 -local interactions (sparse SYK- 4 model). In each setting we show that the Gaussian state can be efficiently determined. Finally, we prove that the O(n−1/2) Gaussian approximation ratio for the normal (dense) SYK- 4 model extends to SYK- q for even q>4 , with an approximation ratio of O(n1/2–q/4) . Our results identify non-sparseness as the prime reason that the SYK- 4 model can fail to have a constant approximation ratio [1, 2].
Efficiently simulating many-body quantum systems with Coulomb interactions is a fundamental question in quantum physics, quantum chemistry, and quantum computing, yet it presents unique challenges: the Hamiltonian is an unbounded operator; its Hilbert space dimension grows exponentially with particle number; and the Coulomb potential is singular, long-ranged, and non-smooth, violating the regularity assumptions of many prior state-of-the-art many-body simulation analyses. In this work, we establish rigorous error bounds for Trotter formulas applied to these systems. Our first main result shows that for general initial conditions in the domain of the Hamiltonian, second-order Trotter achieves a 1/41/41/4 convergence rate with explicit polynomial dependence of the error prefactor on the particle number. The polynomial dependence on system size suggests that the algorithm remains quantumly efficient, even without introducing any regularization of the Coulomb singularity. Such a worst-case rate has been observed in prior work for the hydrogen ground state, demonstrating its physical relevance. We further establish one-step local error lower bounds of order 5/45/45/4 for both formulas, showing that the local exponent is sharp. Our second main result identifies a set of physically meaningful conditions on the initial state under which the convergence rates improve, with the full first-order and second-order rates recovered at sufficiently high angular momentum. Our theoretical findings are consistent with prior numerical observations. Our third main result establishes improved convergence rates for many-body fermionic Coulomb systems with initial data of different Sobolev regularity. In particular, even without imposing any additional regularity beyond the natural domain of the Hamiltonian, both the first- and second-order Trotter formulas converge with rate 1/21/21/2, rather than the general 1/41/41/4 rate.
Quantum dynamics can be simulated on a quantum computer by exponentiating elementary terms from the Hamiltonian in a sequential manner.However, such an implementation of Trotter steps has gate complexity depending on the total Hamiltonian term number, comparing unfavorably to algorithms using more advanced techniques.We develop methods to perform faster Trotter steps with complexity sublinear in the number of terms.We achieve this for a class of Hamiltonians whose interaction strength decays with distance according to power law.Our methods include one based on a recursive block encoding and one based on an average-cost simulation, overcoming the normalization-factor barrier of these advanced quantum simulation techniques.We also realize faster Trotter steps when certain blocks of Hamiltonian coefficients have low rank.Combining with a tighter error analysis, we show that it suffices to use η 1/3 n 1/3 + n 2/3 /η 2/3 n 1+o(1) gates to simulate uniform electron gas with n spin orbitals and η electrons in second quantization in real space, asymptotically improving over the best previous work.We obtain an analogous result when the external potential of nuclei is introduced under the Born-Oppenheimer approximation.We prove a circuit lower bound when the Hamiltonian coefficients take a continuum range of values, showing that generic n-qubit two-local Hamiltonians with commuting terms require at least (n 2 ) gates to evolve with accuracy = (1/poly(n)) for time t = ( ).Our proof is based on a gateefficient reduction from the approximate synthesis of diagonal unitaries within the Hamming weight-2 subspace, which may be of independent interest.Our result thus suggests the use of Hamiltonian structural properties as both necessary and sufficient to implement Trotter steps with lower gate complexity.