Computing electronic structures of quantum systems is a key task underpinning many applications in photonics, solid-state physics, and quantum technologies. This task is typically performed through iterative algorithms to find the energy eigenstates of a Hamiltonian, which are usually computationally expensive and suffer from convergence issues. In this work, we develop and implement the Quantum Jacobi-Davidson (QJD) method and its quantum diagonalization variant, the Sample-Based Quantum Jacobi-Davidson (SBQJD) method, and demonstrate their fast convergence for ground state energy estimation. We assess the intrinsic algorithmic performance of our methods through exact numerical simulations on a variety of quantum systems, including 8-qubit diagonally dominant matrices, 12-qubit one-dimensional Ising models, and a 10-qubit water molecule (H$_2$O) Hamiltonian. Our results show that both QJD and SBQJD achieve significantly faster convergence and require fewer Pauli measurements compared to the recently reported Quantum Davidson method, with SBQJD further benefiting from optimized reference state preparation. These findings establish the QJD framework as an efficient general-purpose subspace-based technique for solving quantum eigenvalue problems, providing a promising foundation for sparse Hamiltonian calculations on future fault-tolerant quantum hardware.
Computing electronic structures of quantum systems is a key task underpinning many applications in photonics, solid-state physics, and quantum technologies. This task is typically performed through iterative algorithms to find the energy eigenstates of a Hamiltonian, which are usually computationally expensive and suffer from convergence issues. In this work, we develop and implement the Quantum Jacobi-Davidson (QJD) method and its quantum diagonalization variant, the Sample-Based Quantum Jacobi-Davidson (SBQJD) method, and demonstrate their fast convergence for ground state energy estimation. We assess the intrinsic algorithmic performance of our methods through exact numerical simulations on a variety of quantum systems, including 8-qubit diagonally dominant matrices, 12-qubit one-dimensional Ising models, and a 10-qubit water molecule (H2O) Hamiltonian. Our results show that both QJD and SBQJD achieve significantly faster convergence and require fewer Pauli measurements compared to the recently reported Quantum Davidson method, with SBQJD further benefiting from optimized reference state preparation. These findings establish the QJD framework as an efficient general-purpose subspace-based technique for solving quantum eigenvalue problems, providing a promising foundation for sparse Hamiltonian calculations on future fault-tolerant quantum hardware.
Abstract Excited state properties play a pivotal role in various chemical and physical phenomena, such as charge separation and light emission. However, the primary focus of most existing quantum algorithms has been the ground state, as seen in quantum phase estimation and the variational quantum eigensolver (VQE). Although VQE-type methods have been extended to explore excited states, these methods grapple with optimization challenges. In contrast, the quantum Krylov subspace (QKS) method has been introduced to address both ground and excited states, positioning itself as a cost-effective alternative to quantum phase estimation. However, conventional QKS methodologies depend on a pre-generated subspace through real or imaginary-time evolutions. This subspace is inherently expansive and can be plagued with issues like slow convergence or numerical instabilities, often leading to relatively deep circuits. Our research presents an economic QKS algorithm, which we term the quantum Davidson (QDavidson) algorithm. This innovation hinges on the iterative expansion of the Krylov subspace and the incorporation of a pre-conditioner within the Davidson framework. By using the residues of eigenstates to expand the Krylov subspace, we manage to formulate a compact subspace that aligns closely with the exact solutions. This iterative subspace expansion paves the way for a more rapid convergence in comparison to other QKS techniques, such as the quantum Lanczos. Using quantum simulators, we employ the novel QDavidson algorithm to delve into the excited state properties of various systems, spanning from the Heisenberg spin model to real molecules. Compared to the existing QKS methods, the QDavidson algorithm not only converges swiftly but also demands a significantly shallower circuit. This efficiency establishes the QDavidson method as a pragmatic tool for elucidating both ground and excited state properties on quantum computing platforms.
We present a comprehensive theoretical analysis of quantum subspace diagonalization methods for molecular electronic structure calculations, establishing rigorous complexity bounds and convergence guarantees. Building on recent developments in adaptive quantum algorithms for chemical systems, we formulate a general mathematical framework that describes how quantum computers can efficiently explore molecular potential energy surfaces through iterative subspace construction. Our theory characterizes the relationship between subspace dimension, basis set selection, and solution accuracy for ground and excited state calculations. We derive analytical expressions for the number of quantum measurements required to achieve chemical accuracy and establish conditions under which quantum subspace methods offer polynomial advantages over classical approaches. The framework incorporates realistic noise models, providing performance predictions for near-term quantum devices. We analyze trade-offs between circuit depth, measurement overhead, and solution quality, identifying optimal operating regimes for different molecular systems. Special attention is devoted to transition-state mapping for chemical reactions, where we prove that adaptive subspace selection achieves exponential reduction in required measurements compared to uniform sampling. Applications to battery electrolyte reactions, drug discovery, and materials design demonstrate the practical utility of our theoretical predictions. This work establishes quantum subspace methods as a rigorous alternative to variational approaches, offering theoretical guarantees absent in parameter-optimization-based algorithms while maintaining compatibility with near-term quantum hardware constraints.
Recently, sample-based quantum diagonalization (SQD) has emerged as a promising approach to compute ground and excited states of problem Hamiltonians.This method classically diagonalizes a Hamiltonian in a subspace that is spanned by samples obtained from a quantum computer. However, by its nature, SQD suffers from a fundamental sampling problem, as some basis states that are required for a targeted accuracy may only be sampled extremely rarely. To alleviate this limitation, we introduce the SQD-AA algorithm that combines SQD with amplitude amplification (AA). SQD-AA uses AA to sequentially reduce probabilities of already measured bitstrings, thus making the observation of new ones more likely. We observe a reduction in the total query complexity of more than a factor 100 for algebraically and exponentially decaying model distributions, and analytically show a quadratic advantage for the latter. Moreover, we evaluate real molecules in an early fault-tolerant scenario and compare SQD-AA to SQD and iterative quantum phase estimation (iQPE). For all considered examples, we observe the lowest total number of T-gates for SQD-AA while only requiring circuits that are 3-4 orders of magnitude shallower than those needed for iQPE. Given this substantial reduction in circuit depth compared to iQPE while saving 2 orders of magnitude in total runtime compared to SQD, we expect a significant regime in early fault-tolerance where SQD-AA runs feasibly, but iQPE circuits are too deep to execute confidently.
Simulating quantum systems is one of the most promising tasks where quantum computing can potentially outperform classical computing. However, the robustness needed for reliable simulations of medium to large systems is beyond the reach of existing quantum devices. To address this, Quantum Krylov Subspace (QKS) methods have been developed, enhancing the ability to perform accelerated simulations on noisy intermediate-scale quantum computers. In this study, we introduce and evaluate two QKS methods derived from the QDavidson algorithm, a novel approach for determining the ground and excited states of many-body systems. Unlike other QKS methods that pre-generate the Krylov subspace through real- or imaginary-time evolution, QDavidson iteratively adds basis vectors into the Krylov subspace. This iterative process enables faster convergence with fewer iterations and necessitates shallower circuit depths, marking a significant advancement in the field of quantum simulation.
In ab-initio quantum chemistry, solving the electronic structure problem of a molecular system of interest to obtain an approximation of the ground and, in some cases, the excited state energies is a core and central task in various quantum chemistry processes. These include, but certainly not limited to, the calculation of the activation energy–that is the minimal energy required to launch a given chemical reaction–, the dipole and multipole moments which describe the polarity of the molecule, performing the optimization of the geometry of the molecule and searching for transition states. Furthermore, many quantum chemistry applications are predicated, not merely on the approximation of the ground state energy, but also on the corresponding first order derivatives. The body of literature of classical algorithms approximating the ground state energy and its first order derivative is extensively rich with a plethora of methods such as self-consistent mean-field methods, coupled-cluster methods, density matrix renormalization group and many more, each of which has intrinsic set of properties and characteristics that makes it suitable for specific tasks and cases. However, classical methods face a practically insurmountable challenge: the efficient computation of high accuracy approximation of ground state energies of large system sizes. This is fundamentally because the electronic structure problem provably belongs to the complexity class of QMA-hard problems. Which also means that it is out of reach for quantum algorithms as well in general. However, with certain assumptions that are expected to hold molecules of interest–that so far proved to be classically challenging because the required accuracy set by the standard of chemical accuracy threshold (generally held in quantum chemistry)– quantum algorithms can efficiently treat such cases. While originally theorized by Richard Feynmann as a potentially efficient way of simulating some classically intractable many-body systems, quantum computing has since proven to have a stronger and richer potential paving the way for the inception of new algorithms such as Shor’s algorithm for integer factorization, HHL for solving linear system of equation and Grover’s algorithm for constrained binary search, just to name a few. These algorithms provably exhibit an improvement rate that goes respectively exponentially and quadratically in the time complexity. Quantum chemistry is considered a prominent candidate to benefit from quantum computing given the variety of quantum algorithms put forth to solve the electronic structure problem of particular systems of interest. These quantum algorithm proposals can be broadly categorized in three main categories that span the spectrum: from noisy intermediate scale quantum (NISQ) computers to early and full scale fault tolerant quantum ((E)FTQC) computers. Firstly, the variational quantum eigensolver (VQE) family of quantum algorithms which variationally search for the ground state energy through the optimization of the energy of a parametrized state prepared in a quantum computer using an ansatz. Secondly, the quantum Krylov subspace diagonalization (QKSD) methods, which generate a subspace of the original Hilbert space and efficiently produce the lowest energy in said subspace as its output. Lastly, we have the quantum phase estimation (QPE) algorithms, which provably produce the ground state energy in Heisenberg scaling presenting hence a provable efficient solution. In this thesis, we firstly set to work on the problem of efficient Hamiltonian linear combination of unitaries (LCU) representation. This is mainly motivated by the wide-range impact an efficient compression of the Hamiltonian can potentially have on several quantum algorithms such as VQE, QPE...etc. We designed a method that efficiently compress the Hamiltonian representation in a way that is beneficially impactful across the set of the aforementioned quantum algorithms. Namely, we motivate and present in Sections 1.3 and 1.4 respectively, the regularized compressed double-factorization (RC-DF) and show how it reduces the energy measurement complexity both in terms of number of distinct observables and number of samples. Moreover, it also reduces the total depth of the quantum phase estimation circuit thanks to its low normalization factor. Secondly, given the importance of the energy derivatives, in Sections 2.1 and 2.2, we introduce and present an efficient quantum algorithm for the calculation of the analytic gradient of VQE energies of double-factorized Hamiltonians. Furthermore, in Section 2.1, we expand on the utility of RC-DF by presenting a quantum algorithm that determines the analytic gradient of energies measured with respect to RC-DF Hamiltonains. Third, in Section 3.1, we summarize the theoretical results of purification error-mitigation techniques, namely echo verification and virtual distillation. In Section 3.2, we report on the results of the experimental bench mark, of said techniques, performed on on Google’s Sycamore device to validate the theoretical scaling of error suppression and extrapolate the resources needed for classically intractable system sizes. Fourth, in Section 4 we establish the challenges of computing energy gradients in a quantum Krylov frame work. To overcome the problem, we provide, in Section 4.3, an efficient quantum algorithm for calculating energy derivative obtained through QKSD procedures. Our approach shows how the QKSD ground state can be prepared using quantum signal processing (QSP) and reduces the number of observables to O(1) per reduced density matrix (RDM). Lastly, in light of the importance of quantum RAMs due to their utility in a variety of quantum algorithms that require efficient initial state preparation, as explained in Section 5.5, we address the problematic exponential depth of the bucket-brigade QRAM (when decomposed). We present in Section 5.6 a very efficient Clifford+T decomposition of the bucket-brigade QRAM, which preserves the linear scaling of the depth of the circuit without introducing any additional ancilla.
Approximating the ground state of many-body systems is a key computational bottleneck underlying important applications in physics and chemistry. The most widely known quantum algorithm for ground state approximation, quantum phase estimation, is out of reach of current quantum processors due to its high circuit-depths. Subspace-based quantum diagonalization methods offer a viable alternative for pre- and early-fault-tolerant quantum computers. Here, we introduce a quantum diagonalization algorithm which combines two key ideas on quantum subspaces: a classical diagonalization based on quantum samples, and subspaces constructed with quantum Krylov states. We prove that our algorithm converges in polynomial time under the working assumptions of Krylov quantum diagonalization and sparseness of the ground state. We then demonstrate the scalability of our approach by performing the largest ground-state quantum simulation of impurity models using a Heron quantum processors and the Frontier supercomputer. We consider both the single-impurity Anderson model with 41 bath sites, and a system with 4 impurities and 7 bath sites per impurity. Our results are in excellent agreement with Density Matrix Renormalization Group calculations.