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:2209.02083 · Physical Review Research

Trimmed sampling algorithm for the noisy generalized eigenvalue problem

Caleb Hicks, Dean Lee

Published Apr 3, 2023• 9 citations
arXivHTMLPDF

Abstract

Solving the generalized eigenvalue problem is a useful method for finding energy eigenstates of large quantum systems.It uses projection onto a set of basis states which are typically not orthogonal.One needs to invert a matrix whose entries are inner products of the basis states, and the process is unfortunately susceptible to even small errors.The problem is especially bad when matrix elements are evaluated using stochastic methods and have significant error bars.In this work, we introduce the trimmed sampling algorithm in order to solve this problem.Using the framework of Bayesian inference, we sample prior probability distributions determined by uncertainty estimates of the various matrix elements and likelihood functions composed of physics-informed constraints.The result is a probability distribution for the eigenvectors and observables which automatically comes with a reliable estimate of the error and performs far better than standard regularization methods.The method should have immediate use for a wide range of applications involving classical and quantum computing calculations of large quantum systems.

DOI
10.1103/physrevresearch.5.l022001

Related papers

Quantum State Vector Reconstruction via Bayesian Inference

Jincheng Zhang

Quantum state vector reconstruction is a fundamental problem in quantum information theory, crucial for tasks like quantum state tomography and quantum error correction. Traditional methods often struggle with noisy measurements and lack a principled framework for uncertainty quantification. This paper introduces a novel algorithm, Quantum State Vector Reconstruction via Bayesian Inference, that leverages Bayesian inference to reconstruct a quantum state vector from a set of measurements, enhancing accuracy and offering a more robust approach compared to existing methods. We detail the core mechanism, emphasizing the integration of Bayesian estimation for uncertainty quantification and refinement of the reconstruction process. The algorithm incorporates a probabilistic approach to estimate the state vector distribution, improving reconstruction by incorporating uncertainty estimates directly into the reconstruction process. This results in a more reliable and accurate state vector reconstruction, particularly when dealing with noisy measurements. This work addresses the limitations of conventional methods by providing a principled Bayesian framework for state vector reconstruction, offering a significant advancement in this field.

•Sep 3, 2026•0 citations

Quantum Eigensolver for Non-Normal Matrices via Ground State Energy Estimation

Honghong Lin, Yun Shang

Large-scale eigenvalue problems pose a significant challenge to classical computers. While there are efficient quantum algorithms for unitary or Hermitian matrices, eigenvalue problems for non-normal matrices remain open in quantum computing. In this work, we propose a quantum algorithm that given a non-normal matrix, outputs an estimate of an eigenvalue to within additive error $ε$ with probability at least $1-p_{\rm fail}$. Our estimation strategy is to sample points on the complex plane and examine the distance between the sampled point and the eigenvalues. We show that the distance is related to the smallest singular value of the shifted matrix, hence reducing the problem to ground state energy estimation via Hermitianization. With the knowledge of an eigenvalue, we are able to prepare the associated eigenvector using ground state preparation. Our estimating scheme can also be modified to approximate the extreme eigenvalue, and in particular the spectral gap. The algorithm is implemented based on the block encoding input model and requires $O(κ^2ε^{-(2m-1)}\log(1/p_{\rm fail}))$ queries to the block encoding oracle. Our algorithm is the first general eigenvalue algorithm that achieves this scaling. We also perform numerical simulation to validate the algorithms.

arXiv:2502.18119•Feb 25, 2025•0 citations

Quantum algorithm for solving generalized eigenvalue problems with application to the Schrödinger equation

Grzegorz Rajchel-Mieldzioć, Szymon Pliś, E. J. Zak

Accurate computation of multiple eigenvalues of quantum Hamiltonians is essential in quantum chemistry, materials science, and molecular spectroscopy. Estimating excited-state energies is challenging for classical algorithms due to exponential scaling with system size, posing an even harder problem than ground-state calculations. We present a quantum algorithm for estimating eigenvalues and singular values of parametrized matrix families, including solving generalized eigenvalue problems that frequently arise in quantum simulations. Our method uses quantum amplitude amplification and phase estimation to identify matrix eigenvalues by locating minima in the singular value spectrum. We demonstrate our algorithm by proposing a quantum computing formulation of the pseudospectral collocation method for the Schrödinger equation. We estimate fault-tolerant quantum resource requirements for the quantum collocation method, showing favorable scaling in the size of the problem N [up to O ̃ ( N ) ] compared to classical implementations with O ̃ ( N ) , for certain well-behaved potentials. Additionally, unlike the standard collocation method, which results in a generalized eigenvalue problem requiring matrix inversion, our algorithm circumvents the associated numerical instability by scanning a parametrized matrix family and detecting eigenvalues through singular value minimization. This approach is particularly effective when multiple eigenvalues are needed or when the generalized eigenvalue problem involves a high condition number. In the fault-tolerant era, our method may thus be useful for simulating high-dimensional molecular systems with dense spectra involving highly excited states, such as those encountered in molecular photodynamics or quasicontinuum regimes in many-body and solid-state systems.

arXiv:2506.13534•Physical Review Research•Apr 11, 2026•1 citation

A New Angle on Quantum Subspace Diagonalization for Quantum Chemistry

Xeno De Vriendt, Jacob Bringewatt, Nik O. Gjonbalaj +5 more

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 $10^4$, 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.

quant-pharXiv:2602.11985•Feb 13, 2026•0 citations

A Theory of Quantum Subspace Diagonalization

Ethan N. Epperly, Lin Lin, Yuji Nakatsukasa

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.

arXiv:2110.07492•SIAM Journal on Matrix Analysis and Applications•Aug 1, 2022•67 citations

Quantum expectation-value estimation by computational basis sampling

Masaya Kohda, Ryosuke Imai, Keita Kanno +3 more

Measuring expectation values of observables is an essential ingredient in variational quantum algorithms. A practical obstacle is the necessity of a large number of measurements for statistical convergence to meet requirements of precision, such as chemical accuracy in the application to quantum chemistry computations. Here we propose an algorithm to estimate the expectation value based on its approximate expression as a weighted sum of classically tractable matrix elements with some modulation, where the weight and modulation factors are evaluated by sampling appropriately prepared quantum states in the computational basis on quantum computers. Each of those states is prepared by applying a unitary transformation consisting of at most $N$ CNOT gates, where $N$ is the number of qubits, to a target quantum state whose expectation value is evaluated. Our algorithm is expected to require fewer measurements than conventional methods for a required statistical precision of the expectation value when the target quantum state is concentrated in particular computational basis states. We provide numerical comparisons of our method with existing ones for measuring electronic ground-state energies (expectation values of electronic Hamiltonians for the lowest-energy states) of various small molecules. Numerical results show that our method can reduce the numbers of measurements to obtain the ground-state energies for a targeted precision by several orders of magnitudes for molecules whose ground states are concentrated. Our results provide another route to measure expectation values of observables, which could accelerate the variational quantum algorithms.

arXiv:2112.07416•Physical Review Research•Sep 2, 2022•31 citations
Solving the generalized eigenvalue problem is a useful method for finding energy eigenstates of large quantum systems.It uses projection onto a set of basis states which are typically not orthogonal.One needs to invert a matrix whose entries are inner products of the basis states, and the process is unfortunately susceptible to even small errors.The problem is especially bad when matrix elements are evaluated using stochastic methods and have significant error bars.In this work, we introduce the trimmed sampling algorithm in order to solve this problem.Using the framework of Bayesian inference, we sample prior probability distributions determined by uncertainty estimates of the various matrix elements and likelihood functions composed of physics-informed constraints.The result is a probability distribution for the eigenvectors and observables which automatically comes with a reliable estimate of the error and performs far better than standard regularization methods.The method should have immediate use for a wide range of applications involving classical and quantum computing calculations of large quantum systems.
Quantum state vector reconstruction is a fundamental problem in quantum information theory, crucial for tasks like quantum state tomography and quantum error correction. Traditional methods often struggle with noisy measurements and lack a principled framework for uncertainty quantification. This paper introduces a novel algorithm, Quantum State Vector Reconstruction via Bayesian Inference, that leverages Bayesian inference to reconstruct a quantum state vector from a set of measurements, enhancing accuracy and offering a more robust approach compared to existing methods. We detail the core mechanism, emphasizing the integration of Bayesian estimation for uncertainty quantification and refinement of the reconstruction process. The algorithm incorporates a probabilistic approach to estimate the state vector distribution, improving reconstruction by incorporating uncertainty estimates directly into the reconstruction process. This results in a more reliable and accurate state vector reconstruction, particularly when dealing with noisy measurements. This work addresses the limitations of conventional methods by providing a principled Bayesian framework for state vector reconstruction, offering a significant advancement in this field.
Large-scale eigenvalue problems pose a significant challenge to classical computers. While there are efficient quantum algorithms for unitary or Hermitian matrices, eigenvalue problems for non-normal matrices remain open in quantum computing. In this work, we propose a quantum algorithm that given a non-normal matrix, outputs an estimate of an eigenvalue to within additive error εεε with probability at least 1−pfail1-p_{\rm fail}1−pfail​. Our estimation strategy is to sample points on the complex plane and examine the distance between the sampled point and the eigenvalues. We show that the distance is related to the smallest singular value of the shifted matrix, hence reducing the problem to ground state energy estimation via Hermitianization. With the knowledge of an eigenvalue, we are able to prepare the associated eigenvector using ground state preparation. Our estimating scheme can also be modified to approximate the extreme eigenvalue, and in particular the spectral gap. The algorithm is implemented based on the block encoding input model and requires O(κ2ε−(2m−1)log⁡(1/pfail))O(κ^2ε^{-(2m-1)}\log(1/p_{\rm fail}))O(κ2ε−(2m−1)log(1/pfail​)) queries to the block encoding oracle. Our algorithm is the first general eigenvalue algorithm that achieves this scaling. We also perform numerical simulation to validate the algorithms.
Accurate computation of multiple eigenvalues of quantum Hamiltonians is essential in quantum chemistry, materials science, and molecular spectroscopy. Estimating excited-state energies is challenging for classical algorithms due to exponential scaling with system size, posing an even harder problem than ground-state calculations. We present a quantum algorithm for estimating eigenvalues and singular values of parametrized matrix families, including solving generalized eigenvalue problems that frequently arise in quantum simulations. Our method uses quantum amplitude amplification and phase estimation to identify matrix eigenvalues by locating minima in the singular value spectrum. We demonstrate our algorithm by proposing a quantum computing formulation of the pseudospectral collocation method for the Schrödinger equation. We estimate fault-tolerant quantum resource requirements for the quantum collocation method, showing favorable scaling in the size of the problem N [up to O ̃ ( N ) ] compared to classical implementations with O ̃ ( N ) , for certain well-behaved potentials. Additionally, unlike the standard collocation method, which results in a generalized eigenvalue problem requiring matrix inversion, our algorithm circumvents the associated numerical instability by scanning a parametrized matrix family and detecting eigenvalues through singular value minimization. This approach is particularly effective when multiple eigenvalues are needed or when the generalized eigenvalue problem involves a high condition number. In the fault-tolerant era, our method may thus be useful for simulating high-dimensional molecular systems with dense spectra involving highly excited states, such as those encountered in molecular photodynamics or quasicontinuum regimes in many-body and solid-state systems.
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 10410^4104, 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.
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.
Measuring expectation values of observables is an essential ingredient in variational quantum algorithms. A practical obstacle is the necessity of a large number of measurements for statistical convergence to meet requirements of precision, such as chemical accuracy in the application to quantum chemistry computations. Here we propose an algorithm to estimate the expectation value based on its approximate expression as a weighted sum of classically tractable matrix elements with some modulation, where the weight and modulation factors are evaluated by sampling appropriately prepared quantum states in the computational basis on quantum computers. Each of those states is prepared by applying a unitary transformation consisting of at most NNN CNOT gates, where NNN is the number of qubits, to a target quantum state whose expectation value is evaluated. Our algorithm is expected to require fewer measurements than conventional methods for a required statistical precision of the expectation value when the target quantum state is concentrated in particular computational basis states. We provide numerical comparisons of our method with existing ones for measuring electronic ground-state energies (expectation values of electronic Hamiltonians for the lowest-energy states) of various small molecules. Numerical results show that our method can reduce the numbers of measurements to obtain the ground-state energies for a targeted precision by several orders of magnitudes for molecules whose ground states are concentrated. Our results provide another route to measure expectation values of observables, which could accelerate the variational quantum algorithms.