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:1807.00821 · Journal of Chemical Theory and Computation

Modern Approaches to Exact Diagonalization and Selected Configuration Interaction with the Adaptive Sampling CI Method

Norm M. Tubman, C. Daniel Freeman, Daniel S. Levine, Diptarka Hait, Martin Head‐Gordon, K. Birgitta Whaley

Published Mar 11, 2020• 193 citations
arXivHTMLPDF

Abstract

Abstract Recent advances in selected configuration interaction methods have made them competitive with the most accurate techniques available and, hence, creating an increasingly powerful tool for solving quantum Hamiltonians. In this work, we build on recent advances from the adaptive sampling configuration interaction (ASCI) algorithm. We show that a useful paradigm for generating efficient selected CI/exact diagonalization algorithms is driven by fast sorting algorithms, much in the same way iterative diagonalization is based on the paradigm of matrix vector multiplication. We present several new algorithms for all parts of performing a selected CI, which includes new ASCI search, dynamic bit masking, fast orbital rotations, fast diagonal matrix elements, and residue arrays. The ASCI search algorithm can be used in several different modes, which includes an integral driven search and a coefficient driven search. The algorithms presented here are fast and scalable, and we find that because they are built on fast sorting algorithms they are more efficient than all other approaches we considered. After introducing these techniques, we present ASCI results applied to a large range of systems and basis sets to demonstrate the types of simulations that can be practically treated at the full-CI level with modern methods and hardware, presenting double- and triple-ζ benchmark data for the G1 data set. The largest of these calculations is Si2H6 which is a simulation of 34 electrons in 152 orbitals. We also present some preliminary results for fast deterministic perturbation theory simulations that use hash functions to maintain high efficiency for treating large basis sets.

DOI
10.1021/acs.jctc.8b00536

Related papers

A parallel, distributed memory implementation of the adaptive sampling configuration interaction method

David B. Williams‐Young, Norm M. Tubman, Carlos Mejuto-Zaera +1 more

The many-body simulation of quantum systems is an active field of research that involves several different methods targeting various computing platforms. Many methods commonly employed, particularly coupled cluster methods, have been adapted to leverage the latest advances in modern high-performance computing. Selected configuration interaction (sCI) methods have seen extensive usage and development in recent years. However, the development of sCI methods targeting massively parallel resources has been explored only in a few research works. Here, we present a parallel, distributed memory implementation of the adaptive sampling configuration interaction approach (ASCI) for sCI. In particular, we will address the key concerns pertaining to the parallelization of the determinant search and selection, Hamiltonian formation, and the variational eigenvalue calculation for the ASCI method. Load balancing in the search step is achieved through the application of memory-efficient determinant constraints originally developed for the ASCI-PT2 method. The presented benchmarks demonstrate near optimal speedup for ASCI calculations of Cr2 (24e, 30o) with 106, 107, and 3 × 108 variational determinants on up to 16 384 CPUs. To the best of the authors' knowledge, this is the largest variational ASCI calculation to date.

arXiv:2303.05688•The Journal of Chemical Physics•Jun 1, 2023•15 citations

A truncated Davidson method for the efficient “chemically accurate” calculation of full configuration interaction wavefunctions without any large matrix diagonalization

Stephen J. Cotton

This work develops and illustrates a new method of calculating “chemically accurate” electronic wavefunctions (and energies) via a truncated full configuration interaction (CI) procedure, which arguably circumvents the large matrix diagonalization that is the core problem of full CI and is also central to modern selective CI approaches. This is accomplished simply by following the standard/ubiquitous Davidson method in its “direct” form—wherein, in each iteration, the electronic Hamiltonian operator is applied directly in second quantization to the Ritz vector/wavefunction from the prior iteration—except that (in this work) only a small portion of the resultant expansion vector is actually even computed (through the application of only a similarly small portion of the Hamiltonian). Specifically, at each iteration of this truncated Davidson approach, the new expansion vector is taken to be twice as large as that from the prior iteration. In this manner, a small set of highly truncated expansion vectors (say 10–30) of increasing precision is incrementally constructed, forming a small subspace within which diagonalization of the Hamiltonian yields clear, consistent, and monotonically variational convergence to the approximate full CI limit. The good efficiency in which convergence to the level of chemical accuracy (1.6 mhartree) is achieved suggests, at least for the demonstrated problem sizes—Hilbert spaces of 1018 and wavefunctions of 108 determinants—that this truncated Davidson methodology can serve as a replacement of standard CI and complete-active space approaches in circumstances where only a few chemically significant digits of accuracy are required and/or meaningful in view of ever-present basis set limitations.

arXiv:2207.12587•The Journal of Chemical Physics•Dec 8, 2022•6 citations

Resource-efficient Quantum Algorithms for Selected Hamiltonian Subspace Diagonalization

Vincent Graves, Manqoba Q. Hlatshwayo, Theodoros Kapourniotis +1 more

Quantum algorithms for selecting a subspace of Hamiltonians to diagonalize have emerged as a promising alternative to variational algorithms in the NISQ era. So far, such algorithms, which include the quantum selected configuration interaction (QSCI) and sample-based quantum diagonalization (SQD), have been formulated within second-quantization in Fock space, which leads to inefficient usage of qubit resources. We introduce the first QSCI algorithm developed in the CI-matrix (CIM) framework, which is known to have optimal qubit scaling of exactly $\lceil \log_2 (N) \rceil$ where $N$ is the size of the CIM. In addition, we introduce a novel single-bit flip error mitigation which comes at the overhead of a single qubit and we combine this with a stochastic approximate Trotterization evolution adapted from qDRIFT. Simulating benchmark N$_2$ and naphthalene molecules on quantum hardware, our results achieved similar accuracy as SQD methods but with significantly less quantum resources. However, our CIM-QSCI algorithm and SQD methods could not match the performance of classical heat-bath CI (HCI) for the same task. Hence, we introduce an augmented version of QSCI called quantum selected heat-bath CI (QSHCI). This variant replaces classical heat-bath sampling with quantum sampling from QSCI to achieve performance comparable to HCI. We note that a current drawback of our approach is the preprocessing cost of $\mathcal{O}(N^2\log N)$ for constructing the CIM and performing the Pauli decomposition. This can be further improved by considering efficient CIM access models for the stochastic Trotter evolution.

quant-pharXiv:2603.13160•Journal of Chemical Theory and Computation•Mar 16, 2026•0 citations

An efficient deterministic perturbation theory for selected configuration interaction methods

Norm M. Tubman, Daniel S. Levine, Diptarka Hait +2 more

The interplay between advances in stochastic and deterministic algorithms has recently led to development of interesting new selected configuration interaction (SCI) methods for solving the many body Schrödinger equation. The performance of these SCI methods can be greatly improved with a second order perturbation theory (PT2) correction, which is often evaluated in a stochastic or hybrid-stochastic manner. In this work, we present a highly efficient, fully deterministic PT2 algorithm for SCI methods and demonstrate that our approach is orders of magnitude faster than recent proposals for stochastic SCI+PT2. We also show that it is important to have a compact reference SCI wave function, in order to obtain optimal SCI+PT2 energies. This indicates that it advantageous to use accurate search algorithms such as 'ASCI search' rather than more approximate approaches. Our deterministic PT2 algorithm is based on sorting techniques that have been developed for modern computing architectures and is inherently straightforward to use on parallel computing architectures. Related architectures such as GPU implementations can be also used to further increase the efficiency. Overall, we demonstrate that the algorithms presented in this work allow for efficient evaluation of trillions of PT2 contributions with modest computing resources.

arXiv:1808.02049•Aug 6, 2018•39 citations

Next Generation Dynamical Mean-Field Theory Simulations with the Adaptive Sampling Configuration Interaction Method

Carlos Mejuto-Zaera, Norm M. Tubman, K. Birgitta Whaley

In the pursuit of accurate descriptions of strongly correlated quantum many-body systems, dynamical mean field theory (DMFT) has been an invaluable tool for elucidating the spectral properties and quantum phases of both phenomenological models and ab initio descriptions of real materials. Key to the DMFT process is the self-consistent map of the original system into an Anderson impurity model, the ground state of which is computed using an impurity solver. The power of the method is thus limited by the complexity of the impurity model the solver can handle. Simulating realistic systems generally requires many correlated sites. By adapting the recently proposed adaptive sampling configuration interaction (ASCI) method as an impurity solver, we enable much more efficient zero temperature DMFT simulations. The key feature of the ASCI method is that it selects only the most relevant Hilbert space degrees of freedom to describe the ground state. This reduces the numerical complexity of the calculation, which will allow us to pursue future DMFT simulations with more correlated impurity sites than in previous works. In this Letter, we present the ASCI-DMFT method and use the one- and two-dimensional Hubbard models to exemplify its efficient convergence and timing properties. We show that the ASCI approach is several orders of magnitude faster than the current best published ground state DMFT simulations. Our approach can also be adapted for other embedding methods such as density matrix embedding theory and self-energy embedding theory.

•Nov 13, 2017•1 citation

Quantum Algorithm for a Convergent Series of Approximations towards the Exact Solution of the Lowest Eigenstates of a Hamiltonian

Zhiyong Zhang

We present quantum algorithms, for Hamiltonians of linear combinations of local unitary operators, for Hamiltonian matrix-vector products and for preconditioning with the inverse of shifted reduced Hamiltonian operator that contributes to the diagonal matrix elements only. The algorithms implement a convergent series of approximations towards the exact solution of the full CI (configuration interaction) problem. The algorithm scales with O(m^5 ), with m the number of one-electron orbitals in the case of molecular electronic structure calculations. Full CI results can be obtained with a scaling of O(nm^5 ), with n the number of electrons and a prefactor on the order of 10 to 20. With low orders of Hamiltonian matrix-vector products, a whole repertoire of approximations widely used in modern electronic structure theory, including various orders of perturbation theory and/or truncated CI at different orders of excitations can be implemented for quantum computing for both routine and benchmark results at chemical accuracy. The lowest order matrix-vector product with preconditioning, basically the second-order perturbation theory, is expected to be a leading algorithm for demonstrating quantum supremacy for Ab Initio simulations, one of the most anticipated real world applications. The algorithm is also applicable for the hybrid variational quantum eigensolver.

arXiv:2009.03537•Sep 8, 2020•0 citations
Abstract Recent advances in selected configuration interaction methods have made them competitive with the most accurate techniques available and, hence, creating an increasingly powerful tool for solving quantum Hamiltonians. In this work, we build on recent advances from the adaptive sampling configuration interaction (ASCI) algorithm. We show that a useful paradigm for generating efficient selected CI/exact diagonalization algorithms is driven by fast sorting algorithms, much in the same way iterative diagonalization is based on the paradigm of matrix vector multiplication. We present several new algorithms for all parts of performing a selected CI, which includes new ASCI search, dynamic bit masking, fast orbital rotations, fast diagonal matrix elements, and residue arrays. The ASCI search algorithm can be used in several different modes, which includes an integral driven search and a coefficient driven search. The algorithms presented here are fast and scalable, and we find that because they are built on fast sorting algorithms they are more efficient than all other approaches we considered. After introducing these techniques, we present ASCI results applied to a large range of systems and basis sets to demonstrate the types of simulations that can be practically treated at the full-CI level with modern methods and hardware, presenting double- and triple-ζ benchmark data for the G1 data set. The largest of these calculations is Si2H6 which is a simulation of 34 electrons in 152 orbitals. We also present some preliminary results for fast deterministic perturbation theory simulations that use hash functions to maintain high efficiency for treating large basis sets.
The many-body simulation of quantum systems is an active field of research that involves several different methods targeting various computing platforms. Many methods commonly employed, particularly coupled cluster methods, have been adapted to leverage the latest advances in modern high-performance computing. Selected configuration interaction (sCI) methods have seen extensive usage and development in recent years. However, the development of sCI methods targeting massively parallel resources has been explored only in a few research works. Here, we present a parallel, distributed memory implementation of the adaptive sampling configuration interaction approach (ASCI) for sCI. In particular, we will address the key concerns pertaining to the parallelization of the determinant search and selection, Hamiltonian formation, and the variational eigenvalue calculation for the ASCI method. Load balancing in the search step is achieved through the application of memory-efficient determinant constraints originally developed for the ASCI-PT2 method. The presented benchmarks demonstrate near optimal speedup for ASCI calculations of Cr2 (24e, 30o) with 106, 107, and 3 × 108 variational determinants on up to 16 384 CPUs. To the best of the authors' knowledge, this is the largest variational ASCI calculation to date.
This work develops and illustrates a new method of calculating “chemically accurate” electronic wavefunctions (and energies) via a truncated full configuration interaction (CI) procedure, which arguably circumvents the large matrix diagonalization that is the core problem of full CI and is also central to modern selective CI approaches. This is accomplished simply by following the standard/ubiquitous Davidson method in its “direct” form—wherein, in each iteration, the electronic Hamiltonian operator is applied directly in second quantization to the Ritz vector/wavefunction from the prior iteration—except that (in this work) only a small portion of the resultant expansion vector is actually even computed (through the application of only a similarly small portion of the Hamiltonian). Specifically, at each iteration of this truncated Davidson approach, the new expansion vector is taken to be twice as large as that from the prior iteration. In this manner, a small set of highly truncated expansion vectors (say 10–30) of increasing precision is incrementally constructed, forming a small subspace within which diagonalization of the Hamiltonian yields clear, consistent, and monotonically variational convergence to the approximate full CI limit. The good efficiency in which convergence to the level of chemical accuracy (1.6 mhartree) is achieved suggests, at least for the demonstrated problem sizes—Hilbert spaces of 1018 and wavefunctions of 108 determinants—that this truncated Davidson methodology can serve as a replacement of standard CI and complete-active space approaches in circumstances where only a few chemically significant digits of accuracy are required and/or meaningful in view of ever-present basis set limitations.
Quantum algorithms for selecting a subspace of Hamiltonians to diagonalize have emerged as a promising alternative to variational algorithms in the NISQ era. So far, such algorithms, which include the quantum selected configuration interaction (QSCI) and sample-based quantum diagonalization (SQD), have been formulated within second-quantization in Fock space, which leads to inefficient usage of qubit resources. We introduce the first QSCI algorithm developed in the CI-matrix (CIM) framework, which is known to have optimal qubit scaling of exactly ⌈log⁡2(N)⌉\lceil \log_2 (N) \rceil⌈log2​(N)⌉ where NNN is the size of the CIM. In addition, we introduce a novel single-bit flip error mitigation which comes at the overhead of a single qubit and we combine this with a stochastic approximate Trotterization evolution adapted from qDRIFT. Simulating benchmark N2_22​ and naphthalene molecules on quantum hardware, our results achieved similar accuracy as SQD methods but with significantly less quantum resources. However, our CIM-QSCI algorithm and SQD methods could not match the performance of classical heat-bath CI (HCI) for the same task. Hence, we introduce an augmented version of QSCI called quantum selected heat-bath CI (QSHCI). This variant replaces classical heat-bath sampling with quantum sampling from QSCI to achieve performance comparable to HCI. We note that a current drawback of our approach is the preprocessing cost of O(N2log⁡N)\mathcal{O}(N^2\log N)O(N2logN) for constructing the CIM and performing the Pauli decomposition. This can be further improved by considering efficient CIM access models for the stochastic Trotter evolution.
The interplay between advances in stochastic and deterministic algorithms has recently led to development of interesting new selected configuration interaction (SCI) methods for solving the many body Schrödinger equation. The performance of these SCI methods can be greatly improved with a second order perturbation theory (PT2) correction, which is often evaluated in a stochastic or hybrid-stochastic manner. In this work, we present a highly efficient, fully deterministic PT2 algorithm for SCI methods and demonstrate that our approach is orders of magnitude faster than recent proposals for stochastic SCI+PT2. We also show that it is important to have a compact reference SCI wave function, in order to obtain optimal SCI+PT2 energies. This indicates that it advantageous to use accurate search algorithms such as 'ASCI search' rather than more approximate approaches. Our deterministic PT2 algorithm is based on sorting techniques that have been developed for modern computing architectures and is inherently straightforward to use on parallel computing architectures. Related architectures such as GPU implementations can be also used to further increase the efficiency. Overall, we demonstrate that the algorithms presented in this work allow for efficient evaluation of trillions of PT2 contributions with modest computing resources.
In the pursuit of accurate descriptions of strongly correlated quantum many-body systems, dynamical mean field theory (DMFT) has been an invaluable tool for elucidating the spectral properties and quantum phases of both phenomenological models and ab initio descriptions of real materials. Key to the DMFT process is the self-consistent map of the original system into an Anderson impurity model, the ground state of which is computed using an impurity solver. The power of the method is thus limited by the complexity of the impurity model the solver can handle. Simulating realistic systems generally requires many correlated sites. By adapting the recently proposed adaptive sampling configuration interaction (ASCI) method as an impurity solver, we enable much more efficient zero temperature DMFT simulations. The key feature of the ASCI method is that it selects only the most relevant Hilbert space degrees of freedom to describe the ground state. This reduces the numerical complexity of the calculation, which will allow us to pursue future DMFT simulations with more correlated impurity sites than in previous works. In this Letter, we present the ASCI-DMFT method and use the one- and two-dimensional Hubbard models to exemplify its efficient convergence and timing properties. We show that the ASCI approach is several orders of magnitude faster than the current best published ground state DMFT simulations. Our approach can also be adapted for other embedding methods such as density matrix embedding theory and self-energy embedding theory.
We present quantum algorithms, for Hamiltonians of linear combinations of local unitary operators, for Hamiltonian matrix-vector products and for preconditioning with the inverse of shifted reduced Hamiltonian operator that contributes to the diagonal matrix elements only. The algorithms implement a convergent series of approximations towards the exact solution of the full CI (configuration interaction) problem. The algorithm scales with O(m^5 ), with m the number of one-electron orbitals in the case of molecular electronic structure calculations. Full CI results can be obtained with a scaling of O(nm^5 ), with n the number of electrons and a prefactor on the order of 10 to 20. With low orders of Hamiltonian matrix-vector products, a whole repertoire of approximations widely used in modern electronic structure theory, including various orders of perturbation theory and/or truncated CI at different orders of excitations can be implemented for quantum computing for both routine and benchmark results at chemical accuracy. The lowest order matrix-vector product with preconditioning, basically the second-order perturbation theory, is expected to be a leading algorithm for demonstrating quantum supremacy for Ab Initio simulations, one of the most anticipated real world applications. The algorithm is also applicable for the hybrid variational quantum eigensolver.