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:2410.11057 · Physical review. B./Physical review. B

Solving the transient Dyson equation with quasilinear complexity via matrix compression

Baptiste Lamic

Published Nov 14, 2025• 4 citations
arXivHTMLPDF

Abstract

We introduce a numerical strategy to efficiently solve the out of equilibrium Dyson equation in the transient regime. By discretizing the equation into a compact matrix form and applying state of the art matrix compression techniques, we achieve significant improvements in computational efficiency which results in quasilinear scaling of both time and space complexity with propagation time. This enables us to compute accurate solutions even for systems with multiple and disparate timescales. We benchmark our solver by simulating a voltage-biased Josephson junction formed by a quantum dot connected to two superconducting leads.

DOI
10.1103/q222-w14m

Related papers

A fast time domain solver for the equilibrium Dyson equation

Jason Kaye, Hugo U. R. Strand

Abstract We consider the numerical solution of the real-time equilibrium Dyson equation, which is used in calculations of the dynamical properties of quantum many-body systems. We show that this equation can be written as a system of coupled, nonlinear, convolutional Volterra integro-differential equations, for which the kernel depends self-consistently on the solution. As is typical in the numerical solution of Volterra-type equations, the computational bottleneck is the quadratic-scaling cost of history integration. However, the structure of the nonlinear Volterra integral operator precludes the use of standard fast algorithms. We propose a quasilinear-scaling FFT-based algorithm which respects the structure of the nonlinear integral operator. The resulting method can reach large propagation times and is thus well-suited to explore quantum many-body phenomena at low energy scales. We demonstrate the solver with two standard model systems: the Bethe graph and the Sachdev-Ye-Kitaev model.

arXiv:2110.06120•Advances in Computational Mathematics•Aug 1, 2023•19 citations

Low rank compression in the numerical solution of the nonequilibrium Dyson equation

Jason Kaye, Denis Golež

We propose a method to improve the computational and memory efficiency of numerical solvers for the nonequilibrium Dyson equation in the Keldysh formalism. It is based on the empirical observation that the nonequilibrium Green's functions and self energies arising in many problems of physical interest, discretized as matrices, have low rank off-diagonal blocks, and can therefore be compressed using a hierarchical low rank data structure. We describe an efficient algorithm to build this compressed representation on the fly during the course of time stepping, and use the representation to reduce the cost of computing history integrals, which is the main computational bottleneck. For systems with the hierarchical low rank property, our method reduces the computational complexity of solving the nonequilibrium Dyson equation from cubic to near quadratic, and the memory complexity from quadratic to near linear. We demonstrate the full solver for the Falicov-Kimball model exposed to a rapid ramp and Floquet driving of system parameters, and are able to increase feasible propagation times substantially. We present examples with 262 144 time steps, which would require approximately five months of computing time and 2.2 TB of memory using the direct time stepping method, but can be completed in just over a day on a laptop with less than 4 GB of memory using our method. We also confirm the hierarchical low rank property for the driven Hubbard model in the weak coupling regime within the GW approximation, and in the strong coupling regime within dynamical mean-field theory.

arXiv:2010.06511•SciPost Physics•Apr 26, 2021•56 citations

Tensor-network simulation of quantum transport in many-quantum-dot systems

Maximilian Streitberger, Marko J. Rančić

Transport through correlated nanoscale systems underpins the operation of quantum-dot and molecular-scale devices, yet accurate simulations of large open quantum systems remain computationally challenging as system size increases. Tensor-network methods offer a promising route past this scaling barrier by efficiently compressing quantum states. Here we extend a tensor-based solver with a jump-counting estimator that enables direct computation of steady-state electron currents from lead-induced tunneling events. We benchmark the resulting currents against the state-of-the-art master-equation solver QmeQ across a range of lead-dot and inter-dot coupling parameters and find quantitative agreement in the tractable regime. Compared with classical approaches, TJM reduces memory requirements and wall-clock time by orders of magnitude, enabling simulations of interacting quantum-dot arrays far beyond the range accessible to density-matrix-based transport solvers and systematic studies of size-dependent nonequilibrium transport in larger arrays. Our approach allow us to model quantum transport in an array of up to fifty (50) quantum dots.

cond-mat.mes-hallCross-listedarXiv:2604.06944•Apr 9, 2026•0 citations

Time-marching based quantum solvers for time-dependent linear differential equations

Di Fang, Lin Lin, Yu Tong

The time-marching strategy, which propagates the solution from one time step to the next, is a natural strategy for solving time-dependent differential equations on classical computers, as well as for solving the Hamiltonian simulation problem on quantum computers. For more general homogeneous linear differential equations ddt|ψ(t)⟩=A(t)|ψ(t)⟩,|ψ(0)⟩=|ψ0⟩ , a time-marching based quantum solver can suffer from exponentially vanishing success probability with respect to the number of time steps and is thus considered impractical. We solve this problem by repeatedly invoking a technique called the uniform singular value amplification, and the overall success probability can be lower bounded by a quantity that is independent of the number of time steps. The success probability can be further improved using a compression gadget lemma. This provides a path of designing quantum differential equation solvers that is alternative to those based on quantum linear systems algorithms (QLSA). We demonstrate the performance of the time-marching strategy with a high-order integrator based on the truncated Dyson series. The complexity of the algorithm depends linearly on the amplification ratio, which quantifies the deviation from a unitary dynamics. We prove that the linear dependence on the amplification ratio attains the query complexity lower bound and thus cannot be improved in the worst case. This algorithm also surpasses existing QLSA based solvers in three aspects: (1) A(t) does not need to be diagonalizable. (2) A(t) can be non-smooth, and is only of bounded variation. (3) It can use fewer queries to the initial state |ψ0⟩ . Finally, we demonstrate the time-marching strategy with a first-order truncated Magnus series, which simplifies the implementation compared to high-order truncated Dyson series approach, while retaining the aforementioned benefits. Our analysis also raises some open questions concerning the differences between time-marching and QLSA based methods for solving differential equations.

arXiv:2208.06941•Quantum•Mar 20, 2023•61 citations

Quantum algorithm for time-dependent differential equations using Dyson series

Dominic William Berry, Pedro C. S. Costa

Time-dependent linear differential equations are a common type of problem that needs to be solved in classical physics. Here we provide a quantum algorithm for solving time-dependent linear differential equations with logarithmic dependence of the complexity on the error and derivative. As usual, there is an exponential improvement over classical approaches in the scaling of the complexity with the dimension, with the caveat that the solution is encoded in the amplitudes of a quantum state. Our method is to encode the Dyson series in a system of linear equations, then solve via the optimal quantum linear equation solver. Our method also provides a simplified approach in the case of time-independent differential equations.

arXiv:2212.03544•Quantum•Jun 13, 2024•31 citations

Legendre-spectral Dyson equation solver with super-exponential convergence

Xinyang Dong, Dominika Zgid, Emanuel Gull +1 more

Quantum many-body systems in thermal equilibrium can be described by the imaginary time Green’s function formalism. However, the treatment of large molecular or solid ab initio problems with a fully realistic Hamiltonian in large basis sets is hampered by the storage of the Green’s function and the precision of the solution of the Dyson equation. We present a Legendre-spectral algorithm for solving the Dyson equation that addresses both of these issues. By formulating the algorithm in Legendre coefficient space, our method inherits the known faster-than-exponential convergence of the Green’s function’s Legendre series expansion. In this basis, the fast recursive method for Legendre polynomial convolution enables us to develop a Dyson equation solver with quadratic scaling. We present benchmarks of the algorithm by computing the dissociation energy of the helium dimer He2 within dressed second-order perturbation theory. For this system, the application of the Legendre spectral algorithm allows us to achieve an energy accuracy of 10−9Eh with only a few hundred expansion coefficients.

arXiv:2001.11603•The Journal of Chemical Physics•Apr 2, 2020•34 citations
We introduce a numerical strategy to efficiently solve the out of equilibrium Dyson equation in the transient regime. By discretizing the equation into a compact matrix form and applying state of the art matrix compression techniques, we achieve significant improvements in computational efficiency which results in quasilinear scaling of both time and space complexity with propagation time. This enables us to compute accurate solutions even for systems with multiple and disparate timescales. We benchmark our solver by simulating a voltage-biased Josephson junction formed by a quantum dot connected to two superconducting leads.
Abstract We consider the numerical solution of the real-time equilibrium Dyson equation, which is used in calculations of the dynamical properties of quantum many-body systems. We show that this equation can be written as a system of coupled, nonlinear, convolutional Volterra integro-differential equations, for which the kernel depends self-consistently on the solution. As is typical in the numerical solution of Volterra-type equations, the computational bottleneck is the quadratic-scaling cost of history integration. However, the structure of the nonlinear Volterra integral operator precludes the use of standard fast algorithms. We propose a quasilinear-scaling FFT-based algorithm which respects the structure of the nonlinear integral operator. The resulting method can reach large propagation times and is thus well-suited to explore quantum many-body phenomena at low energy scales. We demonstrate the solver with two standard model systems: the Bethe graph and the Sachdev-Ye-Kitaev model.
We propose a method to improve the computational and memory efficiency of numerical solvers for the nonequilibrium Dyson equation in the Keldysh formalism. It is based on the empirical observation that the nonequilibrium Green's functions and self energies arising in many problems of physical interest, discretized as matrices, have low rank off-diagonal blocks, and can therefore be compressed using a hierarchical low rank data structure. We describe an efficient algorithm to build this compressed representation on the fly during the course of time stepping, and use the representation to reduce the cost of computing history integrals, which is the main computational bottleneck. For systems with the hierarchical low rank property, our method reduces the computational complexity of solving the nonequilibrium Dyson equation from cubic to near quadratic, and the memory complexity from quadratic to near linear. We demonstrate the full solver for the Falicov-Kimball model exposed to a rapid ramp and Floquet driving of system parameters, and are able to increase feasible propagation times substantially. We present examples with 262 144 time steps, which would require approximately five months of computing time and 2.2 TB of memory using the direct time stepping method, but can be completed in just over a day on a laptop with less than 4 GB of memory using our method. We also confirm the hierarchical low rank property for the driven Hubbard model in the weak coupling regime within the GW approximation, and in the strong coupling regime within dynamical mean-field theory.
Transport through correlated nanoscale systems underpins the operation of quantum-dot and molecular-scale devices, yet accurate simulations of large open quantum systems remain computationally challenging as system size increases. Tensor-network methods offer a promising route past this scaling barrier by efficiently compressing quantum states. Here we extend a tensor-based solver with a jump-counting estimator that enables direct computation of steady-state electron currents from lead-induced tunneling events. We benchmark the resulting currents against the state-of-the-art master-equation solver QmeQ across a range of lead-dot and inter-dot coupling parameters and find quantitative agreement in the tractable regime. Compared with classical approaches, TJM reduces memory requirements and wall-clock time by orders of magnitude, enabling simulations of interacting quantum-dot arrays far beyond the range accessible to density-matrix-based transport solvers and systematic studies of size-dependent nonequilibrium transport in larger arrays. Our approach allow us to model quantum transport in an array of up to fifty (50) quantum dots.
The time-marching strategy, which propagates the solution from one time step to the next, is a natural strategy for solving time-dependent differential equations on classical computers, as well as for solving the Hamiltonian simulation problem on quantum computers. For more general homogeneous linear differential equations ddt|ψ(t)⟩=A(t)|ψ(t)⟩,|ψ(0)⟩=|ψ0⟩ , a time-marching based quantum solver can suffer from exponentially vanishing success probability with respect to the number of time steps and is thus considered impractical. We solve this problem by repeatedly invoking a technique called the uniform singular value amplification, and the overall success probability can be lower bounded by a quantity that is independent of the number of time steps. The success probability can be further improved using a compression gadget lemma. This provides a path of designing quantum differential equation solvers that is alternative to those based on quantum linear systems algorithms (QLSA). We demonstrate the performance of the time-marching strategy with a high-order integrator based on the truncated Dyson series. The complexity of the algorithm depends linearly on the amplification ratio, which quantifies the deviation from a unitary dynamics. We prove that the linear dependence on the amplification ratio attains the query complexity lower bound and thus cannot be improved in the worst case. This algorithm also surpasses existing QLSA based solvers in three aspects: (1) A(t) does not need to be diagonalizable. (2) A(t) can be non-smooth, and is only of bounded variation. (3) It can use fewer queries to the initial state |ψ0⟩ . Finally, we demonstrate the time-marching strategy with a first-order truncated Magnus series, which simplifies the implementation compared to high-order truncated Dyson series approach, while retaining the aforementioned benefits. Our analysis also raises some open questions concerning the differences between time-marching and QLSA based methods for solving differential equations.
Time-dependent linear differential equations are a common type of problem that needs to be solved in classical physics. Here we provide a quantum algorithm for solving time-dependent linear differential equations with logarithmic dependence of the complexity on the error and derivative. As usual, there is an exponential improvement over classical approaches in the scaling of the complexity with the dimension, with the caveat that the solution is encoded in the amplitudes of a quantum state. Our method is to encode the Dyson series in a system of linear equations, then solve via the optimal quantum linear equation solver. Our method also provides a simplified approach in the case of time-independent differential equations.
Quantum many-body systems in thermal equilibrium can be described by the imaginary time Green’s function formalism. However, the treatment of large molecular or solid ab initio problems with a fully realistic Hamiltonian in large basis sets is hampered by the storage of the Green’s function and the precision of the solution of the Dyson equation. We present a Legendre-spectral algorithm for solving the Dyson equation that addresses both of these issues. By formulating the algorithm in Legendre coefficient space, our method inherits the known faster-than-exponential convergence of the Green’s function’s Legendre series expansion. In this basis, the fast recursive method for Legendre polynomial convolution enables us to develop a Dyson equation solver with quadratic scaling. We present benchmarks of the algorithm by computing the dissociation energy of the helium dimer He2 within dressed second-order perturbation theory. For this system, the application of the Legendre spectral algorithm allows us to achieve an energy accuracy of 10−9Eh with only a few hundred expansion coefficients.