⚛️ quantum physics

Fast convergence of Majorana Propagation for weakly interacting fermions

This paper establishes the first provable guarantee for the Majorana Propagation algorithm, demonstrating that it efficiently simulates the time dynamics of weakly interacting sparse quartic fermionic systems by finding low-degree approximations of observables with a runtime that scales polylogarithmically with time and becomes efficient for all times in the limit of vanishing interaction strength.

Original authors: Giorgio Facelli, Hamza Fawzi, Omar Fawzi

Published 2026-09-09

📖 4 min read🧠 Deep dive

CC BY 4.0

Original authors: Giorgio Facelli, Hamza Fawzi, Omar Fawzi

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the microscopic world of quantum physics, particles known as fermions, such as electrons, do not simply sit still; they constantly interact, collide, and influence one another in ways that are incredibly difficult to predict. When scientists try to simulate how these particles move and change over time, they face a massive computational hurdle. The mathematical description of a system with many interacting particles grows so complex so quickly that even the most powerful supercomputers struggle to keep up, often failing after just a short period of time. This limitation is particularly acute for systems where particles interact through a specific type of force that involves four particles at once, a scenario common in materials science and chemistry. While quantum computers promise to solve these problems naturally, they are not yet perfect, and researchers need reliable classical methods to test and verify their results. The challenge, therefore, is to find a way to track the evolution of these quantum systems without getting bogged down by an explosion of mathematical complexity, allowing us to see how the system behaves for as long as possible.

A team of researchers has developed a new method called Majorana Propagation to tackle this exact problem. Their work focuses on a specific class of quantum systems described by a mathematical framework involving "Majorana modes," which are a way of representing fermions that simplifies the description of their interactions. The core idea of their approach is to break the passage of time into tiny, manageable steps. At each step, the researchers calculate how the system changes, but they introduce a clever filter: they discard any part of the calculation that becomes too complicated. Specifically, they ignore mathematical terms that involve more than a certain number of particles interacting at once. This might sound like throwing away important information, but the researchers proved that for systems where the interactions between particles are relatively weak, this simplification does not ruin the accuracy. Instead, it keeps the calculation efficient enough to run on a standard computer while still capturing the essential physics of the system.

The study demonstrates that this method works remarkably well when the interactions between particles are small. In these cases, the system behaves almost like a collection of independent particles, and the researchers showed that their simplified algorithm can track the system's behavior for a very long time, effectively indefinitely if the interactions were to vanish completely. As the strength of the interactions increases, the time window during which the method remains accurate shrinks, but the researchers were able to calculate exactly how long the simulation can be trusted based on the strength of the interaction. They proved mathematically that the error introduced by their method grows slowly and predictably, meaning that by choosing the right settings for their time steps and their complexity filter, they can achieve any desired level of precision. This provides the first solid mathematical guarantee that this type of algorithm can efficiently simulate the time evolution of these complex quantum systems, rather than just hoping it works.

To verify their theory, the team ran numerical experiments using a famous model of electrons in materials known as the Fermi-Hubbard model. They simulated systems of different sizes, ranging from small one-dimensional chains to larger two-dimensional grids, and tested how the method performed under various conditions. The results confirmed their theoretical predictions: as they increased the complexity limit of their filter, the accuracy of the simulation improved exponentially, quickly converging toward the true behavior of the system. They observed that for weaker interactions, the simulation remained accurate for longer periods, while stronger interactions caused the simulation to diverge from the true answer sooner, exactly as their formulas had predicted. These experiments showed that the method is not just a theoretical curiosity but a practical tool that can handle realistic physical scenarios, including the complex dynamics of electrons in a lattice.

This work is significant because it establishes a clear boundary for when classical computers can effectively simulate quantum dynamics. It shows that for weakly interacting systems, which are common in many physical scenarios, we do not need to wait for perfect quantum computers to understand how these systems evolve. The researchers provided a concrete recipe for how to set up the simulation to get the best possible result, balancing the speed of the calculation with the accuracy of the answer. By proving that the error is controlled and that the method scales efficiently with the size of the system, they have opened a new path for studying quantum materials and chemical reactions using classical algorithms. The findings suggest that with the right approach, we can push the limits of what is computable, allowing scientists to explore the time-dependent behavior of quantum matter in regimes that were previously out of reach.

Technical Summary: Fast Convergence of Majorana Propagation for Weakly Interacting Fermions

Problem Statement
Simulating the time dynamics of a local observable under Hamiltonian evolution is a BQP-complete problem, implying that efficient classical algorithms are generally not expected except in restricted settings. This work focuses on a system of interacting fermions described by a quartic Hamiltonian $H$ acting on $N$ Majorana modes $\gamma_1, \dots, \gamma_N$ . The objective is to approximate the Heisenberg evolution of an observable $A$ , defined as $A(t) = e^{iHt}Ae^{-iHt}$ . While the exact evolution can generate observables with maximal degree $N$ (where degree is the length of the longest Majorana string with a non-zero coefficient) immediately for $t>0$ , the authors investigate settings where a low-degree approximation exists and can be found efficiently.

Methodology: Majorana Propagation (MP)
The paper analyzes the Majorana Propagation (MP) algorithm, which combines Trotterization with degree-based truncation. The algorithm proceeds as follows:

Hamiltonian Decomposition: The quartic Hamiltonian $H$ is partitioned into $G \le 4\Delta$ groups $H = H_1 + \dots + H_G$ , where $\Delta$ is the sparsity parameter (each Majorana mode appears in at most $\Delta$ terms). Within each group $H_g$ , the Majorana strings have disjoint supports and thus pairwise commute.
Trotterization: The time evolution is discretized into steps of size $\delta t$ . The evolution operator is approximated by a first-order Trotter product: $\tau^{\text{trot}}_{\delta t}(A) = e^{iH_G \delta t} \dots e^{iH_1 \delta t} A e^{-iH_1 \delta t} \dots e^{-iH_G \delta t}$ .
Propagation and Truncation: The observable is propagated through each Trotter step. Crucially, after each step, a truncation map $\text{Trunc}_\ell$ is applied, which discards all Majorana strings in the observable's expansion with degree greater than a threshold $\ell$ .
Iteration: This process is repeated $t/\delta t$ times to approximate $A(t)$ .

Key Technical Contributions
The paper establishes two primary theoretical pillars supporting the MP algorithm:

Degree-Dependent Norm Inequalities: The authors derive new bounds on the Frobenius norm of commutators and Trotter errors that depend on the degree of the observable rather than the system size $N$ .
- Commutator Bound: For a $\Delta$ -sparse quartic Hamiltonian and an observable $A$ of degree $d$ , $\|[H, A]\|_F \le 2\Delta\sqrt{d(d+2)}\|A\|_F$ . This contrasts with standard bounds that scale with $N$ .
- Trotter Error Bound: The error between the exact evolution and the Trotter approximation for a low-degree observable is shown to be independent of $N$ , scaling instead with the degree $d$ , sparsity $\Delta$ , and the number of groups $G$ . Specifically, $\|\tau_t(A) - \tau^{\text{trot}}_t(A)\|_F \le C \cdot (d\Delta G)^2 t^2$ .
Convergence Analysis: The main theorem (Theorem 1.1/3.3) proves that the error of the MP algorithm is bounded by the sum of the Trotter discretization error and the error of the best possible degree- $\ell$ approximation of the true time-evolved observable.
$\|A^{\ell, \delta t}_{\text{MP}}(t) - A(t)\|_F = O\left( \ell^2 t \delta t + (t/\delta t)\eta^\star_F(H, A, t, \ell) \right)$
where $\eta^\star_F$ quantifies the distance to the best degree- $\ell$ approximant. This result provides the first provable guarantee that MP efficiently finds a low-degree approximation whenever one exists.

Results for Weakly Interacting Hamiltonians
The paper applies these results to Hamiltonians of the form $H = H_0 + uV$ , where $H_0$ is quadratic, $V$ is quartic, and $u \le 1$ is a small interaction strength.

Existence of Low-Degree Approximants: Using perturbation theory, the authors prove that for times $t < t_{\max}(u) \propto \log(e/u)/\Delta$ , the time-evolved observable $A(t)$ can be approximated by a low-degree polynomial with error decaying exponentially in the degree $\ell$ .
Efficient Simulation: Combining the existence of these approximants with the convergence guarantee of MP, the authors prove (Corollary 1.3) that MP can simulate the dynamics of any $\Delta$ -sparse weakly interacting Hamiltonian up to time $t_{\max}(u)$ with a runtime of $N^{O(\log((1+t)/\varepsilon))}$ to achieve an error $\varepsilon$ in the normalized Frobenius norm.
Limit Behavior: As the interaction strength $u \to 0$ , $t_{\max}(u) \to +\infty$ , recovering the known fact that quadratic (free) fermion systems are exactly simulable with constant degree.

Numerical Validation
The authors validate their theoretical findings using the Fermi-Hubbard model in 1D and 2D lattices. Numerical experiments demonstrate:

Exponential convergence of the MP output towards the ideal Trotter evolution as the truncation degree $\ell$ increases.
The behavior of the characteristic time $t_{\max}(u)$ , where simulations with fixed $\ell$ begin to diverge from the exact solution as the interaction strength $U$ increases.
High accuracy in simulating hole density dynamics in 2D lattices for various interaction strengths.

Significance and Claims
The paper claims to provide the first provable guarantee regarding the efficiency of Majorana Propagation for Hamiltonian evolution. It formalizes the intuition that algorithms based on truncating high-degree terms are accurate for weakly interacting systems over long time horizons. The work extends the applicability of classical simulation techniques beyond short-time dynamics or specific geometrically local settings, relying instead on the sparsity of the interaction graph and the weakness of the interaction. The authors note that while the results are derived for fermionic systems, they generalize straightforwardly to spin systems (Pauli propagation). The significance lies in identifying a specific regime (weakly interacting, sparse quartic Hamiltonians) where classical simulation remains efficient, offering a benchmark for quantum advantage studies.

More like this