A theory of quantum subspace diagonalization
arXiv:2110.07492 · doi:10.1137/21M145954X
Abstract
Quantum subspace diagonalization methods are an exciting new class of algorithms for solving large\rev{-}scale eigenvalue problems using quantum computers. Unfortunately, these methods require the solution of an ill-conditioned generalized eigenvalue problem, with a matrix pair corrupted by a non-negligible amount of noise that is far above the machine precision. Despite pessimistic predictions from classical \rev{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.
40 pages, 13 figures
References in corpus (3)
Cited by in corpus (40)
- The Variational Quantum Eigensolver: a review of methods and best practices
- Even shorter quantum circuit for phase estimation on early fault-tolerant quantum computers with applications to ground-state energy estimation
- Quantum-centric Supercomputing for Materials Science: A Perspective on Challenges and Future Directions
- Exact and efficient Lanczos method on a quantum computer
- Simultaneous estimation of multiple eigenvalues with short-depth quantum circuit on early fault-tolerant quantum computers
- Real-Time Krylov Theory for Quantum Computing Algorithms
- Error-resilient Monte Carlo quantum simulation of imaginary time
- Quantum-Selected Configuration Interaction: classical diagonalization of Hamiltonians in subspaces selected by quantum computers
- Diagonalization of large many-body Hamiltonians on a quantum processor
- Quantum Multiple Eigenvalue Gaussian filtered Search: an efficient and versatile quantum phase estimation method
- Quantum-assisted Monte Carlo algorithms for fermions
- A stochastic quantum Krylov protocol with double factorized Hamiltonians
- Analysis of quantum Krylov algorithms with errors
- Spin coupling is all you need: Encoding strong electron correlation in molecules on quantum computers
- Sampling Error Analysis in Quantum Krylov Subspace Diagonalization
- Measurement-efficient quantum Krylov subspace diagonalisation
- Quantum subspace expansion in the presence of hardware noise
- Fast-forwarding quantum simulation with real-time quantum Krylov subspace algorithms
- Quantum Computed Green's Functions using a Cumulant Expansion of the Lanczos Method
- Efficient Strategies for Reducing Sampling Error in Quantum Krylov Subspace Diagonalization
- A Quantum Algorithmic Approach to Multiconfigurational Valence Bond Theory: Insights from Interpretable Circuit Design
- Double-bracket quantum algorithms for quantum imaginary-time evolution
- Molecular Properties from Quantum Krylov Subspace Diagonalization
- Solving lattice gauge theories using the quantum Krylov algorithm and qubitization
- Quantum subspace expansion approach for simulating dynamical response functions of Kitaev spin liquids
- Subspace-Based Local Compilation of Variational Quantum Circuits for Large-Scale Quantum Many-Body Simulation
- Partitioned Quantum Subspace Expansion
- Estimating Eigenenergies from Quantum Dynamics: A Unified Noise-Resilient Measurement-Driven Approach
- Resource-efficient Generalized Quantum Subspace Expansion
- Systematic many-fermion Hamiltonian input scheme and spectral calculations on quantum computers
- Efficient Quantum Simulation of Non-Adiabatic Molecular Dynamics with Precise Electronic Structure
- Approximating dynamical correlation functions with constant depth quantum circuits
- Adaptive measurement strategy for quantum subspace methods
- An Error Mitigated Non-Orthogonal Quantum Eigensolver via Shadow Tomography
- Controlled Gate Networks: Theory and Application to Eigenvalue Estimation
- Cheaper and more noise-resilient quantum state preparation using eigenvector continuation
- Transversal architecture for megaquop-scale quantum simulation with neutral atoms
- Variational Quantum Subspace Construction via Symmetry-Preserving Cost Functions
- A quantum eigenvalue solver based on tensor networks
- Exploring fixed points and eigenstates of quantum systems with reinforcement learning