Measurement-efficient quantum Krylov subspace diagonalisation

Abstract

The Krylov subspace methods, being one category of the most important classical numerical methods for linear algebra problems, can be much more powerful when generalised to quantum computing. However, quantum Krylov subspace algorithms are prone to errors due to inevitable statistical fluctuations in quantum measurements. To address this problem, we develop a general theoretical framework to analyse the statistical error and measurement cost. Based on the framework, we propose a quantum algorithm to construct the Hamiltonian-power Krylov subspace that can minimise the measurement cost. In our algorithm, the product of power and Gaussian functions of the Hamiltonian is expressed as an integral of the real-time evolution, such that it can be evaluated on a quantum computer. We compare our algorithm with other established quantum Krylov subspace algorithms in solving two prominent examples. To achieve an error comparable to that of the classical Lanczos algorithm at the same subspace dimension, our algorithm typically requires orders of magnitude fewer measurements than others. Such an improvement can be attributed to the reduced cost of composing projectors onto the ground state. These results show that our algorithm is exceptionally robust to statistical fluctuations and promising for practical applications.

29 pages, 9 figures

References in corpus (39)

• A variational eigenvalue solver on a quantum processor
• Correlated Electrons in High Temperature Superconductors
• Barren plateaus in quantum neural network training landscapes
• The Shell Model as Unified View of Nuclear Structure
• Simulating Hamiltonian dynamics with a truncated Taylor series
• Determining eigenstates and thermal states on a quantum computer using quantum imaginary time evolution
• Efficient quantum algorithms for simulating sparse Hamiltonians
• Hybrid Quantum-Classical Hierarchy for Mitigation of Decoherence and Determination of Excited States
• Direct estimations of linear and non-linear functionals of a quantum state
• Universal Quantum Estimator
• Encoding Electronic Spectra in Quantum Circuits with Linear T Complexity
• A random compiler for fast Hamiltonian simulation
• Subspace-search variational quantum eigensolver for excited states
• Quantum Computation of Electronic Transitions using a Variational Quantum Eigensolver
• Even more efficient quantum computations of chemistry through tensor hypercontraction
• Is there evidence for exponential quantum advantage in quantum chemistry?
• Higher Order Decompositions of Ordered Operator Exponentials
• A Non-Orthogonal Variational Quantum Eigensolver
• Decoding quantum errors with subspace expansions
• Algorithms for quantum simulation at finite energies
• Quantum Krylov subspace algorithms for ground and excited state energy estimation
• Quantum Power Method by a Superposition of Time-Evolved States
• Real time evolution for ultracompact Hamiltonian eigenstates on quantum hardware
• Symmetry-adapted variational quantum eigensolver
• Generalized quantum subspace expansion
• Exact and efficient Lanczos method on a quantum computer
• Quantum Filter Diagonalization with Double-Factorized Hamiltonians
• Error mitigation via verified phase estimation
• A theory of quantum subspace diagonalization
• Quantum inverse iteration algorithm for programmable quantum simulators
• Randomizing multi-product formulas for Hamiltonian simulation
• Accelerated quantum Monte Carlo with mitigated error on noisy quantum computer
• Real-Time Krylov Theory for Quantum Computing Algorithms
• Hamiltonian operator approximation for energy measurement and ground state preparation
• Error-resilient Monte Carlo quantum simulation of imaginary time
• Tailoring Term Truncations for Electronic Structure Calculations Using a Linear Combination of Unitaries
• A stochastic quantum Krylov protocol with double factorized Hamiltonians
• Analysis of quantum Krylov algorithms with errors
• Improved Hardness Results for the Guided Local Hamiltonian Problem

Cited by in corpus (7)

• Quantum-centric Supercomputing for Materials Science: A Perspective on Challenges and Future Directions
• Diagonalization of large many-body Hamiltonians on a quantum processor
• Hamiltonian simulation-based quantum-selected configuration interaction for large-scale electronic structure calculations with a quantum computer
• Molecular Properties from Quantum Krylov Subspace Diagonalization
• Cheaper and more noise-resilient quantum state preparation using eigenvector continuation
• Variational Quantum Subspace Construction via Symmetry-Preserving Cost Functions
• Hierarchical Fusion Method for Scalable Quantum Eigenstate Preparation