Fast Principal Minor Algorithms for Quantum Many Body Systems

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 upon the algorithm presented in [\emph{Linear Algebra and its applications} 419.1 (2006), 107-124] 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)$, making diagrammatic Monte Carlo for bosonic and mixed systems a viable path worth exploring.

References in corpus (42)

• Continuous-time Monte Carlo methods for quantum impurity models
• Continuous Time Quantum Monte Carlo method for fermions
• Fermi-Polaron: Diagrammatic Monte Carlo for Divergent Sign-Alternating Series
• Monte Carlo study of two-dimensional Bose-Hubbard model
• Critical Temperature and Thermodynamics of Attractive Fermions at Unitarity
• Feynman diagrams versus Fermi-gas Feynman emulator
• Dynamics and Thermodynamics of the Bose-Hubbard model
• Tracking the Footprints of Spin Fluctuations: A MultiMethod, MultiMessenger Study of the Two-Dimensional Hubbard Model
• Diagrammatic Monte Carlo for Correlated Fermions
• Mott insulating states with competing orders in the triangular lattice Hubbard model
• Recent developments in Quantum Monte-Carlo simulations with applications for cold gases
• Determinant Diagrammatic Monte Carlo in the Thermodynamic Limit
• Extended crossover from Fermi liquid to quasi-antiferromagnet in the half-filled 2D Hubbard model
• Sub-matrix updates for the Continuous-Time Auxiliary Field algorithm
• Phase diagram of Bose-Fermi mixtures in one-dimensional optical lattices
• Dynamical mean field solution of the Bose-Hubbard model
• Quantum Monte-Carlo for correlated out-of-equilibrium nanoelectronics devices
• Emergent BCS regime of the two-dimensional fermionic Hubbard model: ground-state phase diagram
• Néel temperature and thermodynamics of the half-filled 3D Hubbard model by Diagrammatic Determinant Monte Carlo
• Reconstructing non-equilibrium regimes of quantum many-body systems from the analytical structure of perturbative expansions
• Spin-Ice State of the Quantum Heisenberg Antiferromagnet on the Pyrochlore Lattice
• Spin and charge correlations across the metal-to-insulator crossover in the half-filled $2d$ Hubbard model
• Resummation of diagrammatic series with zero convergence radius for strongly correlated fermions
• Determinant Monte Carlo for irreducible Feynman diagrams in the strongly correlated regime
• Temperature changes when adiabatically ramping up an optical lattice
• Quantum Quasi-Monte Carlo Technique for Many-Body Perturbative Expansions
• Algorithmic Matsubara Integration for Hubbard-like models
• Inclusion-Exclusion Principle for Many-Body Diagrammatics
• Real-frequency Diagrammatic Monte Carlo at Finite Temperature
• From the Cooper problem to canted supersolids in Bose-Fermi mixtures
• Renormalized perturbation theory at large expansion orders
• Quantum Quasi-Monte Carlo algorithm for out-of-equilibrium Green functions at long times
• High-precision numerical solution of the Fermi polaron problem and large-order behavior of its diagrammatic series
• Real-space cluster dynamical mean-field theory: Center focused extrapolation on the one- and two particle level
• Mean-field phase diagram of the Bose-Fermi Hubbard model
• Homotopic Action: A Pathway to Convergent Diagrammatic Theories
• Entropy in the non-Fermi-liquid regime of the doped $2d$ Hubbard model
• Inclusion-Exclusion Principle for Open Quantum Systems with Bosonic Bath
• Cancellation of vacuum diagrams and long-time limit in out-of-equilibrium diagrammatic Quantum Monte Carlo
• Efficient One-Loop-Renormalized Vertex Expansions with Connected Determinant Diagrammatic Monte Carlo
• Diagrammatic Monte Carlo Method for Impurity Models with General Interactions and Hybridizations
• Direct sampling of the self-energy with Connected Determinant Monte Carlo

Cited by in corpus (3)

• Learning Feynman Diagrams with Tensor Trains
• Origin and fate of the pseudogap in the doped Hubbard model
• Combinatorial summation of Feynman diagrams: Equation of state of the 2D SU(N) Hubbard model