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

Fast principal minor algorithms for diagrammatic Monte Carlo

Fedor Šimkovic, Michel Ferrero

Published Mar 3, 2022• 10 citations
arXivHTMLPDF

Abstract

The computation of determinants plays a central role in diagrammatic Monte Carlo algorithms for strongly correlated systems. The evaluation of large numbers of determinants can often be the limiting computational factor determining the number of attainable diagrammatic expansion orders. In this work we build on the algorithm presented in [K. Griffin and M. J. Tsatsomeros, Principal minors, part i: A method for computing all the principal minors of a matrix, Linear Algebra Appl. 419, 107 (2006)] which computes all principal minors of a matrix in $O({2}^{n})$ operations. We present multiple generalizations of the algorithm to the efficient evaluation of certain subsets of all principal minors with immediate applications to connected determinant diagrammatic Monte Carlo within the normal and symmetry-broken phases as well as continuous-time quantum Monte Carlo. Additionally, we improve the asymptotic scaling of diagrammatic Monte Carlo formulated in real time to $O({2}^{n})$ and report speedups of up to a factor 25 at computationally realistic expansion orders. We further show that all permanent principal minors, corresponding to sums of bosonic Feynman diagrams, can be computed in $O({3}^{n})$, thus encouraging the investigation of bosonic and mixed systems by means of diagrammatic Monte Carlo.

DOI
10.1103/physrevb.105.125104

Related papers

Determinant Diagrammatic Monte Carlo Algorithm in the Thermodynamic Limit

Riccardo Rossi

We present a simple trick that allows us to consider the sum of all connected Feynman diagrams at fixed position of interaction vertices for general fermionic models, such that the thermodynamic limit can be taken analytically. With our approach one can achieve superior performance compared to conventional diagrammatic Monte Carlo algorithm, while rendering the algorithmic part dramatically simpler. By considering the sum of all connected diagrams at once, we allow for massive cancellations between different diagrams, greatly reducing the sign problem. In the end, the computational effort increases only exponentially with the order of the expansion, which should be contrasted with the factorial growth of the standard diagrammatic technique. We illustrate the efficiency of the technique for the two-dimensional Fermi-Hubbard model.

arXiv:1612.05184•Physical Review Letters•Jul 25, 2017•110 citations

New Developments in Diagrammatic Monte Carlo for Interacting Lattice Fermions: Efficient Algorithms and Applications

Boyuan Shi

This thesis develops diagrammatic methods for thermodynamic and subsystem quantities of interacting lattice fermions, providing reference calculations for quantum simulators and many-body approximations. I formulate an inverse-flavour expansion about a self-consistent Hartree saddle, enumerate non-Gaussian diagrams, and use a discrete Lehmann representation to integrate selected internal vertices analytically. Density results cover 31 state points of the six-flavour Hubbard model on a $70\times70$ lattice at $T/t=0.15$. I generalize combinatorial summation to flavour-dependent propagators and expansion shifts. CoS++ combines partial contractions to obtain connected sums for interaction subsets. A determinant-polynomial sieve evaluates the same sums through local coefficient filters; at ninth order it is 24--25 times faster than the specified CoS baselines in three-flavour dense-random-matrix benchmarks. Thermodynamic applications include a 2048-site honeycomb lattice and a three-flavour square lattice with 1024 sites. For the second Renyi entropy, I derive a fermionic replica path integral and a stable evaluation of its two-time Green functions. The connected-determinant calculation reaches tenth order on a $3\times3$ cluster and ninth order on larger lattices. On $50\times50$ sites at $(U/t,μ/t,βt)=(3,1,8)$, the ninth-order continuation at shift $α=1.3$ gives $S_2/N_s=0.06695$ with propagated Monte Carlo uncertainty $3.0\times10^{-5}$. Comparing two expansion shifts at their respective retained orders gives an endpoint difference of $2.6\times10^{-4}$.

arXiv:2610.37505•Oct 27, 2026•0 citations

Determinant Monte Carlo algorithm for dynamical quantities in fermionic quantum systems

Alice Moutenet, Wéi Wú, Michel Ferrero

We introduce a Monte Carlo determinantal algorithm that allows to efficiently sample dynamical quantities, such as the self-energy, of fermionic quantum systems in their thermodynamic limit. The method expresses the sum of a factorial number of one-particle-irreducible diagrams as a recursive sum of determinants with exponential complexity. By comparing results of this algorithm for the lattice Hubbard model with those obtained from diagrammatic Monte Carlo and the recently introduced connected determinant approach, we show that we can reach higher perturbation orders and greater accuracy for the same computational effort.

arXiv:1712.10304?context=cond-mat•Dec 29, 2017•0 citations

Statistical physics of principal minors: Cavity approach

Abolfazl Ramezanpour, M. A. Rajabpour

Determinants are useful to represent the state of an interacting system of (effectively) repulsive and independent elements, like fermions in a quantum system and training samples in a learning problem. A computationally challenging problem is to compute the sum of powers of principal minors of a matrix which is relevant to the study of critical behaviors in quantum fermionic systems and finding a subset of maximally informative training data for a learning algorithm. Specifically, principal minors of positive square matrices can be considered as statistical weights of a random point process on the set of the matrix indices. The probability of each subset of the indices is in general proportional to a positive power of the determinant of the associated submatrix. We use Gaussian representation of the determinants for symmetric and positive matrices to estimate the partition function (or free energy) and the entropy of principal minors within the Bethe approximation. The results are expected to be asymptotically exact for diagonally dominant matrices with locally treelike structures. We consider the Laplacian matrix of random regular graphs of degree K=2,3,4 and exactly characterize the structure of the relevant minors in a mean-field model of such matrices. No (finite-temperature) phase transition is observed in this class of diagonally dominant matrices by increasing the positive power of the principal minors, which here plays the role of an inverse temperature.

arXiv:2405.19904•Physical review. E•Jun 18, 2024•0 citations

Determinant Monte Carlo algorithms for dynamical quantities in fermionic systems

Alice Moutenet, Wéi Wú, Michel Ferrero

We introduce and compare three different Monte Carlo determinantal algorithms that allow one to compute dynamical quantities, such as the self-energy, of fermionic systems in their thermodynamic limit. We show that the most efficient approach expresses the sum of a factorial number of one-particle-irreducible diagrams as a recursive sum of determinants with exponential complexity. By comparing results for the two-dimensional Hubbard model with those obtained from state-of-the-art diagrammatic Monte Carlo, we show that we can reach higher perturbation orders and greater accuracy for the same computational effort.

arXiv:1712.10304•Physical review. B./Physical review. B•Feb 12, 2018•49 citations

Diagrammatic Methods for Strongly-Correlated Electrons in Realistic Systems

Jia Li

This thesis is devoted to the development of numerical methods for correlated electrons in realistic systems based on perturbation theories using Feynman diagrams. Electron correlations in realistic systems give rise to a wide range of interesting physical properties. Diagrammatic expansions and its low-order approximations are key building blocks of theoretical and numerical methods for studying correlated electrons. Recent developments of the diagrammatic quantum Monte Carlo (DiagMC) methods enable efficient stochastic evaluations of diagrams and does not suffer from numerical sign problem which worsens with increasing system size. It is therefore a promising direction to apply DiagMC techniques to realistic electron systems in the pursuit of ab initio calculations of correlated materials. This thesis starts by reviewing basic concepts and definitions of realistic electron systems, the perturbation theory based on Feynman diagrams, Monte Carlo evaluations of the series, as well as self-consistent diagrammatic methods. Low-order diagrammatic methods are applied to realistic calculations and benchmarked against large collections of state-of-the-art many-body methods. The thesis then proposes a diagrammatic Monte Carlo solver for realistic molecules and impurities based on a recursive evaluation of diagrams, which is tested on realistic molecules and impurities with varying temperature, system size, and interaction strength. We observe that this method is ideal for problems with many orbitals with moderate correlations, but may suffer from series divergence at strong correlations. Next, we propose the inchworm Monte Carlo algorithm for interaction expansion, which overcomes limitations of divergent diagrammatic series by replacing the standard perturbation series with a sequence of incremental series expansions. A prototype implementation is presented for system with on-site Hubbard interactions. Finally, we discuss technical aspects of numerical representations of the Green's function, which has significant impact on the efficiency of diagrammatic methods. We review several common numerical representations, and introduce our development of the sparse sampling method, which provides compact representations of the Green's function in both imaginary time and frequency as well as fast transformation formula between the two.

•Jan 1, 2021•0 citations
The computation of determinants plays a central role in diagrammatic Monte Carlo algorithms for strongly correlated systems. The evaluation of large numbers of determinants can often be the limiting computational factor determining the number of attainable diagrammatic expansion orders. In this work we build on the algorithm presented in [K. Griffin and M. J. Tsatsomeros, Principal minors, part i: A method for computing all the principal minors of a matrix, Linear Algebra Appl. 419, 107 (2006)] which computes all principal minors of a matrix in O(2n)O({2}^{n})O(2n) operations. We present multiple generalizations of the algorithm to the efficient evaluation of certain subsets of all principal minors with immediate applications to connected determinant diagrammatic Monte Carlo within the normal and symmetry-broken phases as well as continuous-time quantum Monte Carlo. Additionally, we improve the asymptotic scaling of diagrammatic Monte Carlo formulated in real time to O(2n)O({2}^{n})O(2n) and report speedups of up to a factor 25 at computationally realistic expansion orders. We further show that all permanent principal minors, corresponding to sums of bosonic Feynman diagrams, can be computed in O(3n)O({3}^{n})O(3n), thus encouraging the investigation of bosonic and mixed systems by means of diagrammatic Monte Carlo.
We present a simple trick that allows us to consider the sum of all connected Feynman diagrams at fixed position of interaction vertices for general fermionic models, such that the thermodynamic limit can be taken analytically. With our approach one can achieve superior performance compared to conventional diagrammatic Monte Carlo algorithm, while rendering the algorithmic part dramatically simpler. By considering the sum of all connected diagrams at once, we allow for massive cancellations between different diagrams, greatly reducing the sign problem. In the end, the computational effort increases only exponentially with the order of the expansion, which should be contrasted with the factorial growth of the standard diagrammatic technique. We illustrate the efficiency of the technique for the two-dimensional Fermi-Hubbard model.
This thesis develops diagrammatic methods for thermodynamic and subsystem quantities of interacting lattice fermions, providing reference calculations for quantum simulators and many-body approximations. I formulate an inverse-flavour expansion about a self-consistent Hartree saddle, enumerate non-Gaussian diagrams, and use a discrete Lehmann representation to integrate selected internal vertices analytically. Density results cover 31 state points of the six-flavour Hubbard model on a 70×7070\times7070×70 lattice at T/t=0.15T/t=0.15T/t=0.15. I generalize combinatorial summation to flavour-dependent propagators and expansion shifts. CoS++ combines partial contractions to obtain connected sums for interaction subsets. A determinant-polynomial sieve evaluates the same sums through local coefficient filters; at ninth order it is 24--25 times faster than the specified CoS baselines in three-flavour dense-random-matrix benchmarks. Thermodynamic applications include a 2048-site honeycomb lattice and a three-flavour square lattice with 1024 sites. For the second Renyi entropy, I derive a fermionic replica path integral and a stable evaluation of its two-time Green functions. The connected-determinant calculation reaches tenth order on a 3×33\times33×3 cluster and ninth order on larger lattices. On 50×5050\times5050×50 sites at (U/t,μ/t,βt)=(3,1,8)(U/t,μ/t,βt)=(3,1,8)(U/t,μ/t,βt)=(3,1,8), the ninth-order continuation at shift α=1.3α=1.3α=1.3 gives S2/Ns=0.06695S_2/N_s=0.06695S2​/Ns​=0.06695 with propagated Monte Carlo uncertainty 3.0×10−53.0\times10^{-5}3.0×10−5. Comparing two expansion shifts at their respective retained orders gives an endpoint difference of 2.6×10−42.6\times10^{-4}2.6×10−4.
We introduce a Monte Carlo determinantal algorithm that allows to efficiently sample dynamical quantities, such as the self-energy, of fermionic quantum systems in their thermodynamic limit. The method expresses the sum of a factorial number of one-particle-irreducible diagrams as a recursive sum of determinants with exponential complexity. By comparing results of this algorithm for the lattice Hubbard model with those obtained from diagrammatic Monte Carlo and the recently introduced connected determinant approach, we show that we can reach higher perturbation orders and greater accuracy for the same computational effort.
Determinants are useful to represent the state of an interacting system of (effectively) repulsive and independent elements, like fermions in a quantum system and training samples in a learning problem. A computationally challenging problem is to compute the sum of powers of principal minors of a matrix which is relevant to the study of critical behaviors in quantum fermionic systems and finding a subset of maximally informative training data for a learning algorithm. Specifically, principal minors of positive square matrices can be considered as statistical weights of a random point process on the set of the matrix indices. The probability of each subset of the indices is in general proportional to a positive power of the determinant of the associated submatrix. We use Gaussian representation of the determinants for symmetric and positive matrices to estimate the partition function (or free energy) and the entropy of principal minors within the Bethe approximation. The results are expected to be asymptotically exact for diagonally dominant matrices with locally treelike structures. We consider the Laplacian matrix of random regular graphs of degree K=2,3,4 and exactly characterize the structure of the relevant minors in a mean-field model of such matrices. No (finite-temperature) phase transition is observed in this class of diagonally dominant matrices by increasing the positive power of the principal minors, which here plays the role of an inverse temperature.
We introduce and compare three different Monte Carlo determinantal algorithms that allow one to compute dynamical quantities, such as the self-energy, of fermionic systems in their thermodynamic limit. We show that the most efficient approach expresses the sum of a factorial number of one-particle-irreducible diagrams as a recursive sum of determinants with exponential complexity. By comparing results for the two-dimensional Hubbard model with those obtained from state-of-the-art diagrammatic Monte Carlo, we show that we can reach higher perturbation orders and greater accuracy for the same computational effort.
This thesis is devoted to the development of numerical methods for correlated electrons in realistic systems based on perturbation theories using Feynman diagrams. Electron correlations in realistic systems give rise to a wide range of interesting physical properties. Diagrammatic expansions and its low-order approximations are key building blocks of theoretical and numerical methods for studying correlated electrons. Recent developments of the diagrammatic quantum Monte Carlo (DiagMC) methods enable efficient stochastic evaluations of diagrams and does not suffer from numerical sign problem which worsens with increasing system size. It is therefore a promising direction to apply DiagMC techniques to realistic electron systems in the pursuit of ab initio calculations of correlated materials. This thesis starts by reviewing basic concepts and definitions of realistic electron systems, the perturbation theory based on Feynman diagrams, Monte Carlo evaluations of the series, as well as self-consistent diagrammatic methods. Low-order diagrammatic methods are applied to realistic calculations and benchmarked against large collections of state-of-the-art many-body methods. The thesis then proposes a diagrammatic Monte Carlo solver for realistic molecules and impurities based on a recursive evaluation of diagrams, which is tested on realistic molecules and impurities with varying temperature, system size, and interaction strength. We observe that this method is ideal for problems with many orbitals with moderate correlations, but may suffer from series divergence at strong correlations. Next, we propose the inchworm Monte Carlo algorithm for interaction expansion, which overcomes limitations of divergent diagrammatic series by replacing the standard perturbation series with a sequence of incremental series expansions. A prototype implementation is presented for system with on-site Hubbard interactions. Finally, we discuss technical aspects of numerical representations of the Green's function, which has significant impact on the efficiency of diagrammatic methods. We review several common numerical representations, and introduce our development of the sparse sampling method, which provides compact representations of the Green's function in both imaginary time and frequency as well as fast transformation formula between the two.