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

IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum

Parallelizing the Hamiltonian Computation in DQMC Simulations: Checkerboard Method for Sparse Matrix Exponentials on Multicore and GPU

Che–Rung Lee, Zhi-Hung Chen, Quey-Liang Kao

Published May 1, 2012• 2 citations
Publisher

Abstract

Determinant Quantum Monte Carlo (DQMC) simulation is one of few numerical methods that can explore the micro properties of fermions, which has many technically important applications in chemistry and material science. Conventionally, its parallelization relies on parallel Monte Carlo method, whose speedup is limited by the thermalization process and the underlying matrix computation. To achieve better performance, fine-grained parallelization on its numerical kernel is essential to utilize the massive parallel processing units, which are multicores and/or GPUs interconnected by high performance network. In this paper, we address the parallelization on one of the matrix kernel in the DQMC simulations: the multiplication of matrix exponentials. The matrix is derived from the kinetic Hamiltonian, which is highly sparse. We approximate its exponential by the checkerboard method, which decomposes the matrix exponential into a product of a sequence of block sparse matrices. We analyze the block sparse matrices of two common used lattice geometry: 2D torus and 3D cubic, and parallelize the computational kernel of multiplying them to a general matrix. The parallel algorithm is designed for multicore CPU and GPU. The results of experiments showed on a quad core processor, 3 times speedup can be observed in average, and on GPU, 145 times speedup is achievable.

DOI
10.1109/ipdpsw.2012.233

Related papers

Accelerating block checkerboard method on GPU for performance enhancement of 2D and 3D Quantum Monte Carlo simulations

Chi-Cheng Chuang, Yu-Sheng Chiu, Quey-Liang Kao +2 more

Quantum Monte Carlo (QMC) simulations for the recent studies on complex materials were confronted by new computational challenges. Traditional approach to accelerate the simulations by parallel Monte Carlo chains faces serious scalability problems since the speedup is reaching the limitation predicted by Amdahl's law. Fine-grained parallelization of matrix kernels is essential to achieve better performance. In this paper, we investigate the performance optimization techniques on GPU for the most time consuming computational kernel in the Determinant Quantum Monte Carlo (DQMC) simulation: multiplication of matrix exponentials. The matrix, derived from the kinetic Hamiltonian, is highly sparse, and its exponential is approximated by the block checkerboard method, which can represent a matrix exponential as a product of a sequence of sparse matrices. The matrix exponentials from 2D and 3D toruses are focused, and various optimization techniques, such as data streaming and concurrent kernels, are proposed. Experiments show that the proposed optimization techniques can improve the SpMM (Sparse Matrix Multiplication) function, modified from the CUDA SKD SpMV function, up to 16 times and 117 times for 2D and 3D problems respectively.

IEEE International Conference on Cloud Computing Technology and Science•Dec 1, 2012•0 citations

Efficient Computing for Reduced Density Matrix on GPUs

Wenhao Liang, Runfeng Jin, Yingqi Tian +2 more

The reduced density matrix (RDM) plays an important role in quantum physics. With the RDM, we can accurately describe the energy of the quantum system. However, solving the RDM is a computationally intensive task where matrix multiplication accounts for more than 95% of the computation time, and exponential complexity, large memory consumption, and tensor sparsity make it challenging to achieve efficient computation. This paper proposes an efficient, scalable and multi-GPU solver for computing the RDM. The complexity of computing RDM is reduced to polynomial by using a tensor network approach in the form of matrix product state (MPS). The sparsity blocks are composed of contiguous memory locations using the list algorithm. The precomputation approach uses a small memory overhead to replace some redundant computations. Furthermore, the sparsity blocks are computed on the GPU using variable-size batch general matrix multiplication (GEMM). We benchmark the performance using a water molecule, and our results show that we achieve a 22.4 × speedup when using four MI50 GPUs compared to a 32-core CPU. Additionally, we demonstrate excellent strong scaling, achieving over 92% parallel efficiency when comparing the performance on 256 nodes versus 16 nodes.

IEEE International Conference on High Performance Computing and Communications; IEEE International Conference on Smart City; IEEE International Conference on Data Science and Systems (HPCC/SmartCity/DSS)•Dec 17, 2023•1 citation

Hybrid parallel optimization of density matrix renormalization group method

Fuzhou Chen, Chen Cheng, Hong‐Gang Luo

Density matrix renormalization group (DMRG), as a numerical method of solving the ground state of one-dimensional strongly-correlated lattice model with very high accuracy, requires expensive computational and memory cost when applied to two- and quasi-two-dimensional problems. The number of DMRG kept states is generally very large to achieve a reliable accuracy for these applications, which results in numerous matrix and vector operations and unbearably consuming time in the absence of the proper parallelization. However, due to its sequential nature, the parallelization of DMRG algorithm is usually not straightforward. In this work, we propose a new hybrid parallelization strategy for the DMRG method. It takes advantage of the computing capability of both central processing unit (CPU) and graphics processing unit (GPU) of the computer. In order to achieve as many as DMRG kept states within a limited GPU memory, we adopt the four-block formulation of the Hamiltonian rather than the two-block formulation. The later consumes much more memories, which has been used in another pioneer work on the hybrid parallelization of the DMRG algorithm, and only a small number of DMRG kept states are available. Our parallel strategy focuses on the diagonalization of the Hamiltonian, which is the most time-consuming part of the whole DMRG procedure. A hybrid parallelization strategy of diagonalization method is implemented, in which the required data for diagonalization are distributed on both the host and GPU memory, and the data exchange between them is negligible in our data partitioning scheme. The matrix operations are also shared on both CPU and GPU when the Hamiltonian acts on a wave function, while the distribution of these operations is determined by a load balancing strategy. Taking fermionic Hubbard model for example, we examine the running performance of the hybrid parallelization strategy with different DMRG kept states and provide corresponding performance benchmark. On a 4-leg ladder, we employ the conserved quantities with U(1) symmetry of the model and a good-quantum number based task scheduling to further reduce the GPU memory cost. We manage to obtain a moderate speedup of the hybrid parallelization for a wide range of DMRG kept states. In our example, the ground state energy with high accuracy is obtained by the extrapolation of the results, with different numbers of states kept, and we show charge stripes which are usually experimentally observed in high-temperature superconductors. In this case, we keep 104 DMRG states and the GPU memory cost is less than 12 Gigabytes.

Acta Physica Sinica•Jan 1, 2019•4 citations

Accelerating lattice quantum Monte Carlo simulations using artificial neural networks: Application to the Holstein model

Shaozhi Li, Philip M. Dee, Ehsan Khatami +1 more

Monte Carlo (MC) simulations are essential computational approaches with widespread use throughout all areas of science. We present a method for accelerating lattice MC simulations using fully connected and convolutional artificial neural networks that are trained to perform local and global moves in configuration space, respectively. Both networks take local spacetime MC configurations as input features and can, therefore, be trained using samples generated by conventional MC runs on smaller lattices before being utilized for simulations on larger systems. This approach is benchmarked for the case of determinant quantum Monte Carlo (DQMC) studies of the two-dimensional Holstein model. We find that both artificial neural networks are capable of learning an unspecified effective model that accurately reproduces the MC configuration weights of the original Hamiltonian and achieve an order of magnitude speedup over the conventional DQMC algorithm. Our approach is broadly applicable to many classical and quantum lattice MC algorithms.

arXiv:1905.07440•Physical review. B./Physical review. B•Jul 22, 2019•38 citations

Two-dimensional quantum lattice models via mode optimized hybrid CPU-GPU density matrix renormalization group method

Andor Menczer, Kornél Kapás, Miklós Antal Werner +1 more

We present a hybrid numerical approach to simulate quantum many-body problems on two spatial dimensional quantum lattice models via the non-Abelian ab initio version of the density matrix renormalization group method on state-of-the-art high-performance computing infrastructures. We demonstrate that for the two-dimensional spinless fermion model and for the Hubbard model on torus geometry, altogether several orders of magnitude in computational time can be saved by performing calculations on an optimized basis and by utilizing hybrid CPU-multiGPU parallelization. At least an order of magnitude reduction in computational complexity results from mode optimization, while a further order of reduction in wall time is achieved by massive parallelization. Our results are measured directly in the number of floating point operations and seconds. A detailed scaling analysis of the obtained performance as a function of matrix ranks and as a function of system size up to $12\ifmmode\times\else\texttimes\fi{}12$ lattice topology is discussed. Our CPU-multiGPU model also tremendously accelerates the calculation of the one- and two-particle reduced density matrices, which can be used to construct various order parameters and trace quantum phase transitions with high fidelity.

arXiv:2311.14106•Physical review. B./Physical review. B•May 14, 2024•11 citations

Determinant Quantum-Quantum Monte Carlo: Coherent Auxiliary-Field Sampling

Xuepeng Wang, Sagnik Banerjee, Debanjan Chowdhury

We introduce determinant quantum-quantum Monte Carlo (DQ$^2$MC), a quantum algorithm that lifts the auxiliary-field sampling and averaging at the operational core of determinant quantum Monte Carlo onto a quantum computer. A determinant oracle synthesizes the DQMC amplitudes directly from a block encoding of the single-particle action matrix via quantum singular value transformations, so that the exponentially many Hubbard-Stratonovich weights are never enumerated, precomputed, or stored. Since the fermions are free for fixed auxiliary fields, the construction operates entirely at the single-particle level, requiring $O(\log N_{\mathrm{st}})$ system qubits and no Jordan-Wigner or Bravyi-Kitaev encoding, where $N_{\mathrm{st}}$ is the space-time volume. A full-quantum protocol makes observables interference amplitudes, eliminating the Markov chain and its autocorrelation time altogether; a hybrid quantum-classical protocol retains a constant-size active block of qubits and replaces the Metropolis-Hastings acceptance step with an exact heat-bath draw, so that cluster updates of any size are rejection-free, and passes only classical information between updates, admitting parallel tempering and distributed execution across quantum processors. The circuit-depth scales more favorably with spatial volume than classical DQMC, at the price of a post-selection overhead determined exactly by the largest target probability --- polynomial for smooth distributions, exponential for sharply peaked ones. Finally, the reweighting estimator underlying the fermion sign problem maps exactly onto a quantum weak value, placing the exponential cost of sign-problematic DQMC in precise correspondence with the post-selection overhead of weak-value extraction.

cond-mat.str-elCross-listedarXiv:2608.28742•Sep 1, 2026•0 citations
Determinant Quantum Monte Carlo (DQMC) simulation is one of few numerical methods that can explore the micro properties of fermions, which has many technically important applications in chemistry and material science. Conventionally, its parallelization relies on parallel Monte Carlo method, whose speedup is limited by the thermalization process and the underlying matrix computation. To achieve better performance, fine-grained parallelization on its numerical kernel is essential to utilize the massive parallel processing units, which are multicores and/or GPUs interconnected by high performance network. In this paper, we address the parallelization on one of the matrix kernel in the DQMC simulations: the multiplication of matrix exponentials. The matrix is derived from the kinetic Hamiltonian, which is highly sparse. We approximate its exponential by the checkerboard method, which decomposes the matrix exponential into a product of a sequence of block sparse matrices. We analyze the block sparse matrices of two common used lattice geometry: 2D torus and 3D cubic, and parallelize the computational kernel of multiplying them to a general matrix. The parallel algorithm is designed for multicore CPU and GPU. The results of experiments showed on a quad core processor, 3 times speedup can be observed in average, and on GPU, 145 times speedup is achievable.
Quantum Monte Carlo (QMC) simulations for the recent studies on complex materials were confronted by new computational challenges. Traditional approach to accelerate the simulations by parallel Monte Carlo chains faces serious scalability problems since the speedup is reaching the limitation predicted by Amdahl's law. Fine-grained parallelization of matrix kernels is essential to achieve better performance. In this paper, we investigate the performance optimization techniques on GPU for the most time consuming computational kernel in the Determinant Quantum Monte Carlo (DQMC) simulation: multiplication of matrix exponentials. The matrix, derived from the kinetic Hamiltonian, is highly sparse, and its exponential is approximated by the block checkerboard method, which can represent a matrix exponential as a product of a sequence of sparse matrices. The matrix exponentials from 2D and 3D toruses are focused, and various optimization techniques, such as data streaming and concurrent kernels, are proposed. Experiments show that the proposed optimization techniques can improve the SpMM (Sparse Matrix Multiplication) function, modified from the CUDA SKD SpMV function, up to 16 times and 117 times for 2D and 3D problems respectively.
The reduced density matrix (RDM) plays an important role in quantum physics. With the RDM, we can accurately describe the energy of the quantum system. However, solving the RDM is a computationally intensive task where matrix multiplication accounts for more than 95% of the computation time, and exponential complexity, large memory consumption, and tensor sparsity make it challenging to achieve efficient computation. This paper proposes an efficient, scalable and multi-GPU solver for computing the RDM. The complexity of computing RDM is reduced to polynomial by using a tensor network approach in the form of matrix product state (MPS). The sparsity blocks are composed of contiguous memory locations using the list algorithm. The precomputation approach uses a small memory overhead to replace some redundant computations. Furthermore, the sparsity blocks are computed on the GPU using variable-size batch general matrix multiplication (GEMM). We benchmark the performance using a water molecule, and our results show that we achieve a 22.4 × speedup when using four MI50 GPUs compared to a 32-core CPU. Additionally, we demonstrate excellent strong scaling, achieving over 92% parallel efficiency when comparing the performance on 256 nodes versus 16 nodes.
Density matrix renormalization group (DMRG), as a numerical method of solving the ground state of one-dimensional strongly-correlated lattice model with very high accuracy, requires expensive computational and memory cost when applied to two- and quasi-two-dimensional problems. The number of DMRG kept states is generally very large to achieve a reliable accuracy for these applications, which results in numerous matrix and vector operations and unbearably consuming time in the absence of the proper parallelization. However, due to its sequential nature, the parallelization of DMRG algorithm is usually not straightforward. In this work, we propose a new hybrid parallelization strategy for the DMRG method. It takes advantage of the computing capability of both central processing unit (CPU) and graphics processing unit (GPU) of the computer. In order to achieve as many as DMRG kept states within a limited GPU memory, we adopt the four-block formulation of the Hamiltonian rather than the two-block formulation. The later consumes much more memories, which has been used in another pioneer work on the hybrid parallelization of the DMRG algorithm, and only a small number of DMRG kept states are available. Our parallel strategy focuses on the diagonalization of the Hamiltonian, which is the most time-consuming part of the whole DMRG procedure. A hybrid parallelization strategy of diagonalization method is implemented, in which the required data for diagonalization are distributed on both the host and GPU memory, and the data exchange between them is negligible in our data partitioning scheme. The matrix operations are also shared on both CPU and GPU when the Hamiltonian acts on a wave function, while the distribution of these operations is determined by a load balancing strategy. Taking fermionic Hubbard model for example, we examine the running performance of the hybrid parallelization strategy with different DMRG kept states and provide corresponding performance benchmark. On a 4-leg ladder, we employ the conserved quantities with U(1) symmetry of the model and a good-quantum number based task scheduling to further reduce the GPU memory cost. We manage to obtain a moderate speedup of the hybrid parallelization for a wide range of DMRG kept states. In our example, the ground state energy with high accuracy is obtained by the extrapolation of the results, with different numbers of states kept, and we show charge stripes which are usually experimentally observed in high-temperature superconductors. In this case, we keep 104 DMRG states and the GPU memory cost is less than 12 Gigabytes.
Monte Carlo (MC) simulations are essential computational approaches with widespread use throughout all areas of science. We present a method for accelerating lattice MC simulations using fully connected and convolutional artificial neural networks that are trained to perform local and global moves in configuration space, respectively. Both networks take local spacetime MC configurations as input features and can, therefore, be trained using samples generated by conventional MC runs on smaller lattices before being utilized for simulations on larger systems. This approach is benchmarked for the case of determinant quantum Monte Carlo (DQMC) studies of the two-dimensional Holstein model. We find that both artificial neural networks are capable of learning an unspecified effective model that accurately reproduces the MC configuration weights of the original Hamiltonian and achieve an order of magnitude speedup over the conventional DQMC algorithm. Our approach is broadly applicable to many classical and quantum lattice MC algorithms.
We present a hybrid numerical approach to simulate quantum many-body problems on two spatial dimensional quantum lattice models via the non-Abelian ab initio version of the density matrix renormalization group method on state-of-the-art high-performance computing infrastructures. We demonstrate that for the two-dimensional spinless fermion model and for the Hubbard model on torus geometry, altogether several orders of magnitude in computational time can be saved by performing calculations on an optimized basis and by utilizing hybrid CPU-multiGPU parallelization. At least an order of magnitude reduction in computational complexity results from mode optimization, while a further order of reduction in wall time is achieved by massive parallelization. Our results are measured directly in the number of floating point operations and seconds. A detailed scaling analysis of the obtained performance as a function of matrix ranks and as a function of system size up to $12\ifmmode\times\else\texttimes\fi{}12$ lattice topology is discussed. Our CPU-multiGPU model also tremendously accelerates the calculation of the one- and two-particle reduced density matrices, which can be used to construct various order parameters and trace quantum phase transitions with high fidelity.
We introduce determinant quantum-quantum Monte Carlo (DQ2^22MC), a quantum algorithm that lifts the auxiliary-field sampling and averaging at the operational core of determinant quantum Monte Carlo onto a quantum computer. A determinant oracle synthesizes the DQMC amplitudes directly from a block encoding of the single-particle action matrix via quantum singular value transformations, so that the exponentially many Hubbard-Stratonovich weights are never enumerated, precomputed, or stored. Since the fermions are free for fixed auxiliary fields, the construction operates entirely at the single-particle level, requiring O(log⁡Nst)O(\log N_{\mathrm{st}})O(logNst​) system qubits and no Jordan-Wigner or Bravyi-Kitaev encoding, where NstN_{\mathrm{st}}Nst​ is the space-time volume. A full-quantum protocol makes observables interference amplitudes, eliminating the Markov chain and its autocorrelation time altogether; a hybrid quantum-classical protocol retains a constant-size active block of qubits and replaces the Metropolis-Hastings acceptance step with an exact heat-bath draw, so that cluster updates of any size are rejection-free, and passes only classical information between updates, admitting parallel tempering and distributed execution across quantum processors. The circuit-depth scales more favorably with spatial volume than classical DQMC, at the price of a post-selection overhead determined exactly by the largest target probability --- polynomial for smooth distributions, exponential for sharply peaked ones. Finally, the reweighting estimator underlying the fermion sign problem maps exactly onto a quantum weak value, placing the exponential cost of sign-problematic DQMC in precise correspondence with the post-selection overhead of weak-value extraction.