Inspired by the quantum computing algorithms for Linear Algebra problems [HHL,TaShma] we study how the simulation on a classical computer of this type of "Phase Estimation algorithms" performs when we apply it to solve the Eigen-Problem of Hermitian matrices. The result is a completely new, efficient and stable, parallel algorithm to compute an approximate spectral decomposition of any Hermitian matrix. The algorithm can be implemented by Boolean circuits in
O(log2n) parallel time with a total cost of
O(nω+1) Boolean operations. This Boolean complexity matches the best known rigorous
O(log2n) parallel time algorithms, but unlike those algorithms our algorithm is (logarithmically) stable, so further improvements may lead to practical implementations. All previous efficient and rigorous approaches to solve the Eigen-Problem use randomization to avoid bad condition as we do too. Our algorithm makes further use of randomization in a completely new way, taking random powers of a unitary matrix to randomize the phases of its eigenvalues. Proving that a tiny Gaussian perturbation and a random polynomial power are sufficient to ensure almost pairwise independence of the phases
(mod(2π)) is the main technical contribution of this work. This randomization enables us, given a Hermitian matrix with well separated eigenvalues, to sample a random eigenvalue and produce an approximate eigenvector in
O(log2n) parallel time and
O(nω) Boolean complexity. We conjecture that further improvements of our method can provide a stable solution to the full approximate spectral decomposition problem with complexity similar to the complexity (up to a logarithmic factor) of sampling a single eigenvector.
Quantum subspace diagonalization and quantum Krylov algorithms offer a feasible, pre- or early-fault tolerant alternative to quantum phase estimation for using quantum computers to estimate the low-lying spectra of quantum systems. However, despite promising proof-of-principle results, such methods suffer from high sensitivity to noise (including intrinsic sources such as sampling noise), making their utility for realistic industry-relevant problems an open question. To improve the potential applicability of such methods, we introduce a new variant of thresholding for noisy generalized eigenvalue problems that arise in quantum subspace diagonalization that has the potential to better control sensitivity to noise. Our approach leverages eigenvector-preserving transformations (rotations) of the generalized eigenvalue problem prior to thresholding. We study this effect in practical settings by applying this rotation thresholding scheme to an iterative quantum Krylov algorithm for several chemical systems, including the industry-relevant Fe(III)-NTA chelate complex. We develop a particular heuristic to select the rotation angle from noisy data and find for certain systems and noise regimes that the samples required to reach a target error for ground state estimation can be reduced by a factor of up to 100. Furthermore, with oracle access to the optimal transformation, more dramatic improvements are possible and we observe reductions in sample requirements by up to
104, motivating the continued development of methods that can realize these improvements in practice. While we develop our approach in the context of quantum subspace diagonalization, the improved thresholding scheme we develop could be advantageous in any context where one must solve noisy, ill-conditioned generalized eigenvalue problems.
This paper presents a novel approach to approximating tensor eigenvalues using randomized benchmarking techniques. Traditional methods for tensor eigenvalue computation, particularly for large-scale tensors, often suffer from computational bottlenecks and scalability issues. Our method addresses this challenge by exploiting the inherent redundancy in tensor representations through randomized sampling. We develop a framework that efficiently estimates tensor eigenvalues by iteratively applying randomized measurements and analyzing the resulting data. The core of the method lies in the strategic selection of measurement bases and the subsequent application of benchmarking techniques to minimize the variance of eigenvalue estimates. The resulting algorithm offers a scalable solution suitable for handling tensors with a significantly higher dimensionality compared to conventional methods. This approach demonstrates a promising avenue for accelerating tensor computations and unlocking new possibilities in various scientific and engineering domains. The theoretical analysis provides insights into the convergence properties of the algorithm, and the proposed method is demonstrated with a theoretical framework.
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
2O) 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.
Quantum subspace diagonalization methods are an exciting new class of algorithms for solving large-scale eigenvalue problems using quantum computers. Unfortunately, these methods require the solution of an ill-conditioned generalized eigenvalue problem, with a matrix pencil corrupted by a nonnegligible amount of noise that is far above the machine precision. Despite pessimistic predictions from classical worst-case perturbation theories, these methods can perform reliably well if the generalized eigenvalue problem is solved using a standard truncation strategy. By leveraging and advancing classical results in matrix perturbation theory, we provide a theoretical analysis of this surprising phenomenon, proving that under certain natural conditions, a quantum subspace diagonalization algorithm can accurately compute the smallest eigenvalue of a large Hermitian matrix. We give numerical experiments demonstrating the effectiveness of the theory and providing practical guidance for the choice of truncation level. Our new results can also be of independent interest to solving eigenvalue problems outside the context of quantum computation.
We study quantum spectrum and eigenstate property estimation using multiple initial states and generalized Hadamard tests. Building on the QFAMES (quantum filtering and analysis of multiplicities in eigenvalue spectra) framework, we introduce a new method that samples evolution times independently for each initial-state pair. Under the stated assumptions, when statistical error determines the sampling cost, the total Hamiltonian simulation cost required for fixed-accuracy eigenvalue and observable estimation is independent of the number of initial states, up to logarithmic factors. This improves scalability when many initial states are needed to explore the target eigenspaces. The method also reduces the cost of multiplicity recovery and retains Heisenberg-limited scaling for eigenvalue estimation. Numerical experiments support the predicted statistical error scalings.