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

Preconditioning the non-relativistic many-fermion problem

Timour Ten, Joaquín E. Drut, Timo A. Lähde

Published Aug 21, 2010• 1 citation
arXivHTMLPDF

Abstract

Preconditioning is at the core of modern many-fermion Monte Carlo algorithms, such as Hybrid Monte Carlo, where the repeated solution of a linear problem involving an ill-conditioned matrix is needed. We report on a performance comparison of three preconditioning strategies, namely Chebyshev polynomials, strong-coupling approximation and weak-coupling expansion. We use conjugate gradient (CG) on the normal equations as well as stabilized biconjugate gradient (BiCGStab) as solvers and focus on the fermion matrix of the unitary Fermi gas. Our results indicate that BiCGStab is by far the most efficient strategy, both in terms of the number of iterations and matrix-vector operations.

DOI
10.48550/arxiv.1008.3647

Related papers

A Preconditioned Riemannian Conjugate Gradient Method to Compute Ground States of Spin-1 Bose–Einstein Condensates

Wen Tao Huang, Zilin Yang, Qinglin Tang

Abstract. In this paper, we propose a preconditioned Riemannian conjugate gradient method for computing ground states of spin-1 Bose-Einstein condensates, which can be reformulated as an optimization problem with the mass and magnetization constraints. The energy functional and constraints can be discretized using Fourier pseudospectral schemes, thereby transforming the problem into an optimization task on a manifold. We derive vector transports by differentiating three existing retractions and propose an initial step size selection strategy based on the second-order approximation of the energy function for the proposed Riemannian optimization algorithm. In addition, a preconditioner is derived and used. To further accelerate the convergence, we combine the proposed algorithm with a multigrid method. Numerical experiments demonstrate the efficiency and accuracy of the proposed method while confirming the usefulness of our preconditioning technique and the effectiveness of the proposed strategy for initial step size selection.

SIAM Journal on Scientific Computing•Apr 1, 2026•0 citations

Fast inversion, preconditioned quantum linear system solvers, fast Green's-function computation, and fast evaluation of matrix functions

Yu Tong, Dong An, Nathan Wiebe +1 more

Preconditioning is the most widely used and effective way for treating ill-conditioned linear systems in the context of classical iterative linear system solvers. We introduce a quantum primitive called fast inversion, which can be used as a preconditioner for solving quantum linear systems. The key idea of fast inversion is to directly block encode a matrix inverse through a quantum circuit implementing the inversion of eigenvalues via classical arithmetics. We demonstrate the application of preconditioned linear system solvers for computing single-particle Green's functions of quantum many-body systems, which are widely used in quantum physics, chemistry, and materials science. We analyze the complexities in three scenarios: the Hubbard model, the quantum many-body Hamiltonian in the plane-wave-dual basis, and the Schwinger model. We also provide a method for performing Green's function calculation in second quantization within a fixed-particle manifold and note that this approach may be valuable for simulation more broadly. Aside from solving linear systems, fast inversion also allows us to develop fast algorithms for computing matrix functions, such as the efficient preparation of Gibbs states. We introduce two efficient approaches for such a task, based on the contour-integral formulation and the inverse transform, respectively.

arXiv:2008.13295•Physical Review A•Sep 27, 2021•108 citations

A Monte Carlo Method for Fermion Systems Coupled with Classical Degrees of Freedom

Yukitoshi Motome, Nobuo Furukawa

A new Monte Carlo method is proposed for fermion systems interacting with classical degrees of freedom. To obtain a weight for each Monte Carlo sample with a fixed configuration of classical variables, the moment expansion of the density of states by Chebyshev polynomials is applied instead of the direct diagonalization of the fermion Hamiltonian. This reduces a cpu time to scale as $O(N_{\rm dim}^{2} \log N_{\rm dim})$ compared to $O(N_{\rm dim}^{3})$ for the diagonalization in the conventional technique; $N_{\rm dim}$ is the dimension of the Hamiltonian. Another advantage of this method is that parallel computation with high efficiency is possible. These significantly save total cpu times of Monte Carlo calculations because the calculation of a Monte Carlo weight is the bottleneck part. The method is applied to the double-exchange model as an example. The benchmark results show that it is possible to make a systematic investigation using a system-size scaling even in three dimensions within a realistic cpu timescale.

arXiv:cond-mat/0007407•Journal of the Physical Society of Japan•Dec 15, 1999•71 citations

OrderNMonte Carlo Algorithm for Fermion Systems Coupled with Fluctuating Adiabatical Fields

Nobuo Furukawa, Yukitoshi Motome

An improved algorithm is proposed for Monte Carlo methods to study fermion systems interacting with adiabatical fields. To obtain a weight for each Monte Carlo sample with a fixed configuration of adiabatical fields, a series expansion using Chebyshev polynomials is applied. By introducing truncations of matrix operations in a systematic and controlled way, it is shown that the cpu time is reduced from O(N^3) to O(N) where N is the system size. Benchmark results show that the implementation of the algorithm makes it possible to perform systematic investigations of critical phenomena using system-size scalings even for an electronic model in three dimensions, within a realistic cpu timescale.

arXiv:cond-mat/0308298•Journal of the Physical Society of Japan•Jun 15, 2004•41 citations

Simulations of strongly-interacting fermion systems

Evgeni Burovski

A generic scenario of a crossover between weak-coupling and strong-coupling limits of a many-body quantum system is studied. Powerful numerical methods of investigating the strongly correlated regime are developed and applied to answering a number of important questions of the strongly correlated fermions physics. The internal structure of an exciton in an insulating medium is studied throughout the crossover between the (analytically solvable) strong- and weak-coupling limits. In the intermediate regime, accurate results for the exciton ground state are obtained and used to establish the limits of applicability of the corresponding limiting cases for the first time. A novel combination of the diagrammatic determinant Monte Carlo and the worm algorithm is developed and used for investigating the unitarity regime of the BEC-BCS crossover via simulating the dilute Fermi-Hubbard model. Superfluid phase transition and thermodynamic properties of the normal state are characterized for both lattice fermions and continuum unitary Fermi gas. The relation to current experiments with trapped ultracold quantum gases is discussed.

•Jan 1, 2007•0 citations

Factorized approximate inverse preconditioners in the tensor train format

Pau Torrente Badia, Daniel Pérez García, Artur Garcia-Saez +1 more

We present a preconditioning pipeline that accelerates Tensor Train (TT) linear solvers for symmetric positive-definite problems. Extending the Factorized Sparse Approximate Inverse framework to tensor networks, we construct a preconditioner as the product of a TT operator and its transpose. This formulation is positive semidefinite for any bond dimension and truncation, and definite whenever the factor is non-singular, satisfying the mathematical requirements of the Conjugate Gradient method. We detail the construction of this preconditioner and its integration into Density Matrix Renormalization Group (DMRG)-like linear solvers. Performance evaluations show consistent iteration reductions for anisotropic diffusion and Poisson problems across various configurations, leading to net speedups of up to 25% in ill-conditioned settings of time stepping schemes that can reuse the approximate inverses. These benchmarks were performed with the open-source Julia library DifferenTT.jl, which we also introduce in this work to provide out-of-the-box access to these preconditioned pipelines.

math.NACross-listedarXiv:2611.03859•Nov 4, 2026•0 citations
Preconditioning is at the core of modern many-fermion Monte Carlo algorithms, such as Hybrid Monte Carlo, where the repeated solution of a linear problem involving an ill-conditioned matrix is needed. We report on a performance comparison of three preconditioning strategies, namely Chebyshev polynomials, strong-coupling approximation and weak-coupling expansion. We use conjugate gradient (CG) on the normal equations as well as stabilized biconjugate gradient (BiCGStab) as solvers and focus on the fermion matrix of the unitary Fermi gas. Our results indicate that BiCGStab is by far the most efficient strategy, both in terms of the number of iterations and matrix-vector operations.
Abstract. In this paper, we propose a preconditioned Riemannian conjugate gradient method for computing ground states of spin-1 Bose-Einstein condensates, which can be reformulated as an optimization problem with the mass and magnetization constraints. The energy functional and constraints can be discretized using Fourier pseudospectral schemes, thereby transforming the problem into an optimization task on a manifold. We derive vector transports by differentiating three existing retractions and propose an initial step size selection strategy based on the second-order approximation of the energy function for the proposed Riemannian optimization algorithm. In addition, a preconditioner is derived and used. To further accelerate the convergence, we combine the proposed algorithm with a multigrid method. Numerical experiments demonstrate the efficiency and accuracy of the proposed method while confirming the usefulness of our preconditioning technique and the effectiveness of the proposed strategy for initial step size selection.
Preconditioning is the most widely used and effective way for treating ill-conditioned linear systems in the context of classical iterative linear system solvers. We introduce a quantum primitive called fast inversion, which can be used as a preconditioner for solving quantum linear systems. The key idea of fast inversion is to directly block encode a matrix inverse through a quantum circuit implementing the inversion of eigenvalues via classical arithmetics. We demonstrate the application of preconditioned linear system solvers for computing single-particle Green's functions of quantum many-body systems, which are widely used in quantum physics, chemistry, and materials science. We analyze the complexities in three scenarios: the Hubbard model, the quantum many-body Hamiltonian in the plane-wave-dual basis, and the Schwinger model. We also provide a method for performing Green's function calculation in second quantization within a fixed-particle manifold and note that this approach may be valuable for simulation more broadly. Aside from solving linear systems, fast inversion also allows us to develop fast algorithms for computing matrix functions, such as the efficient preparation of Gibbs states. We introduce two efficient approaches for such a task, based on the contour-integral formulation and the inverse transform, respectively.
A new Monte Carlo method is proposed for fermion systems interacting with classical degrees of freedom. To obtain a weight for each Monte Carlo sample with a fixed configuration of classical variables, the moment expansion of the density of states by Chebyshev polynomials is applied instead of the direct diagonalization of the fermion Hamiltonian. This reduces a cpu time to scale as O(Ndim2log⁡Ndim)O(N_{\rm dim}^{2} \log N_{\rm dim})O(Ndim2​logNdim​) compared to O(Ndim3)O(N_{\rm dim}^{3})O(Ndim3​) for the diagonalization in the conventional technique; NdimN_{\rm dim}Ndim​ is the dimension of the Hamiltonian. Another advantage of this method is that parallel computation with high efficiency is possible. These significantly save total cpu times of Monte Carlo calculations because the calculation of a Monte Carlo weight is the bottleneck part. The method is applied to the double-exchange model as an example. The benchmark results show that it is possible to make a systematic investigation using a system-size scaling even in three dimensions within a realistic cpu timescale.
An improved algorithm is proposed for Monte Carlo methods to study fermion systems interacting with adiabatical fields. To obtain a weight for each Monte Carlo sample with a fixed configuration of adiabatical fields, a series expansion using Chebyshev polynomials is applied. By introducing truncations of matrix operations in a systematic and controlled way, it is shown that the cpu time is reduced from O(N^3) to O(N) where N is the system size. Benchmark results show that the implementation of the algorithm makes it possible to perform systematic investigations of critical phenomena using system-size scalings even for an electronic model in three dimensions, within a realistic cpu timescale.
A generic scenario of a crossover between weak-coupling and strong-coupling limits of a many-body quantum system is studied. Powerful numerical methods of investigating the strongly correlated regime are developed and applied to answering a number of important questions of the strongly correlated fermions physics. The internal structure of an exciton in an insulating medium is studied throughout the crossover between the (analytically solvable) strong- and weak-coupling limits. In the intermediate regime, accurate results for the exciton ground state are obtained and used to establish the limits of applicability of the corresponding limiting cases for the first time. A novel combination of the diagrammatic determinant Monte Carlo and the worm algorithm is developed and used for investigating the unitarity regime of the BEC-BCS crossover via simulating the dilute Fermi-Hubbard model. Superfluid phase transition and thermodynamic properties of the normal state are characterized for both lattice fermions and continuum unitary Fermi gas. The relation to current experiments with trapped ultracold quantum gases is discussed.
We present a preconditioning pipeline that accelerates Tensor Train (TT) linear solvers for symmetric positive-definite problems. Extending the Factorized Sparse Approximate Inverse framework to tensor networks, we construct a preconditioner as the product of a TT operator and its transpose. This formulation is positive semidefinite for any bond dimension and truncation, and definite whenever the factor is non-singular, satisfying the mathematical requirements of the Conjugate Gradient method. We detail the construction of this preconditioner and its integration into Density Matrix Renormalization Group (DMRG)-like linear solvers. Performance evaluations show consistent iteration reductions for anisotropic diffusion and Poisson problems across various configurations, leading to net speedups of up to 25% in ill-conditioned settings of time stepping schemes that can reuse the approximate inverses. These benchmarks were performed with the open-source Julia library DifferenTT.jl, which we also introduce in this work to provide out-of-the-box access to these preconditioned pipelines.