Analysis of quantum Krylov algorithms with errors

Abstract

This work provides a nonasymptotic error analysis of quantum Krylov algorithms based on real-time evolutions, subject to generic errors in the outputs of the quantum circuits. We prove upper and lower bounds on the resulting ground state energy estimates, and the error associated to the upper bound is linear in the input error rates. This resolves a misalignment between known numerics, which exhibit approximately linear error scaling, and prior theoretical analysis, which only provably obtained scaling with the error rate to the power $\frac{2}{3}$. Our main technique is to express generic errors in terms of an effective target Hamiltonian studied in an effective Krylov space. These results provide a theoretical framework for understanding the main features of quantum Krylov errors.

arXiv commentFinal version, 27 pages (main text 12 pages), 1 figure. Source code available at https://github.com/wmkirby1/krylov-analysis-paper-numerics. Typos fixed

References in corpus (35)

• Hamiltonian Simulation by Qubitization
• Exponential algorithmic speedup by quantum walk
• Optimal Hamiltonian Simulation by Quantum Signal Processing
• Determining eigenstates and thermal states on a quantum computer using quantum imaginary time evolution
• Efficient quantum algorithms for simulating sparse Hamiltonians
• Quantum Computation by Adiabatic Evolution
• Hybrid Quantum-Classical Hierarchy for Mitigation of Decoherence and Determination of Excited States
• A Theory of Trotter Error
• Robust determination of molecular spectra on a quantum processor
• On the relationship between continuous- and discrete-time quantum walk
• Hamiltonian simulation with nearly optimal dependence on all parameters
• Exponential improvement in precision for simulating sparse Hamiltonians
• Heisenberg-limited ground state energy estimation for early fault-tolerant quantum computers
• Increasing the representation accuracy of quantum simulations of chemistry without extra quantum resources
• Ground state preparation and energy estimation on early fault-tolerant quantum computers via quantum eigenvalue transformation of unitary matrices
• A Non-Orthogonal Variational Quantum Eigensolver
• Quantum Krylov subspace algorithms for ground and excited state energy estimation
• Time-dependent Hamiltonian simulation with $L^1$-norm scaling
• Quantum Power Method by a Superposition of Time-Evolved States
• Real time evolution for ultracompact Hamiltonian eigenstates on quantum hardware
• Generalized quantum subspace expansion
• Locality and digital quantum simulation of power-law interactions
• Exact and efficient Lanczos method on a quantum computer
• Quantum Filter Diagonalization with Double-Factorized Hamiltonians
• Quantum Filter Diagonalization: Quantum Eigendecomposition without Full Quantum Phase Estimation
• A theory of quantum subspace diagonalization
• Quantum inverse iteration algorithm for programmable quantum simulators
• Hamiltonian Simulation in the Interaction Picture
• Chemistry on quantum computers with virtual quantum subspace expansion
• Real-Time Krylov Theory for Quantum Computing Algorithms
• Hamiltonian operator approximation for energy measurement and ground state preparation
• Diagonalization of large many-body Hamiltonians on a quantum processor
• Quantum subspace expansion algorithm for Green's functions
• Leveraging hardware-control imperfections for error mitigation via generalized quantum subspace
• Shadow-based quantum subspace algorithm for the nuclear shell model

Cited by in corpus (13)

• Quantum-centric Supercomputing for Materials Science: A Perspective on Challenges and Future Directions
• Diagonalization of large many-body Hamiltonians on a quantum processor
• Spin coupling is all you need: Encoding strong electron correlation in molecules on quantum computers
• Measurement-efficient quantum Krylov subspace diagonalisation
• Solving lattice gauge theories using the quantum Krylov algorithm and qubitization
• Molecular Properties from Quantum Krylov Subspace Diagonalization
• Quantum subspace expansion approach for simulating dynamical response functions of Kitaev spin liquids
• Partitioned Quantum Subspace Expansion
• Systematic many-fermion Hamiltonian input scheme and spectral calculations on quantum computers
• Approximating dynamical correlation functions with constant depth quantum circuits
• Adiabatic state preparation from general initial states
• Cheaper and more noise-resilient quantum state preparation using eigenvector continuation
• Variational Quantum Subspace Construction via Symmetry-Preserving Cost Functions