Exact and efficient Lanczos method on a quantum computer

Abstract

We present an algorithm that uses block encoding on a quantum computer to exactly construct a Krylov space, which can be used as the basis for the Lanczos method to estimate extremal eigenvalues of Hamiltonians. While the classical Lanczos method has exponential cost in the system size to represent the Krylov states for quantum systems, our efficient quantum algorithm achieves this in polynomial time and memory. The construction presented is exact in the sense that the resulting Krylov space is identical to that of the Lanczos method, so the only approximation with respect to the exact method is due to finite sample noise. This is possible because, unlike previous quantum Krylov methods, our algorithm does not require simulating real or imaginary time evolution. We provide an explicit error bound for the resulting ground state energy estimate in the presence of noise. For our method to be successful efficiently, the only requirement on the input problem is that the overlap of the initial state with the true ground state must be $\Omega (1/\text{poly}(n))$ for $n$ qubits.

arXiv comment33 pages, 9 figures; minor corrections and new numerics included in this version

References in corpus (44)

• A variational eigenvalue solver on a quantum processor
• Hardware-efficient Variational Quantum Eigensolver for Small Molecules and Quantum Magnets
• Barren plateaus in quantum neural network training landscapes
• Quantum computational chemistry
• Simulated Quantum Computation of Molecular Energies
• Quantum fingerprinting
• Cost Function Dependent Barren Plateaus in Shallow Parametrized Quantum Circuits
• Hamiltonian Simulation by Qubitization
• Noise-Induced Barren Plateaus in Variational Quantum Algorithms
• Scalable Quantum Simulation of Molecular Energies
• Optimal Hamiltonian Simulation by Quantum Signal Processing
• Stabilizer Codes and Quantum Error Correction
• Determining eigenstates and thermal states on a quantum computer using quantum imaginary time evolution
• Quantum Computation by Adiabatic Evolution
• Hybrid Quantum-Classical Hierarchy for Mitigation of Decoherence and Determination of Excited States
• Quantum measurements and the Abelian Stabilizer Problem
• Simulation of Electronic Structure Hamiltonians Using Quantum Computers
• Robust determination of molecular spectra on a quantum processor
• Simulating Physical Phenomena by Quantum Networks
• Low Depth Quantum Simulation of Electronic Structure
• Efficient estimation of Pauli observables by derandomization
• Heisenberg-limited ground state energy estimation for early fault-tolerant quantum computers
• Near-optimal ground state preparation
• 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
• Fault-Tolerant Quantum Simulations of Chemistry in First Quantization
• On barren plateaus and cost function locality in variational quantum algorithms
• 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
• Generalized quantum subspace expansion
• Quantum Filter Diagonalization: Quantum Eigendecomposition without Full Quantum Phase Estimation
• Quantum Filter Diagonalization with Double-Factorized Hamiltonians
• A theory of quantum subspace diagonalization
• Overlapped grouping measurement: A unified framework for measuring quantum states
• Adaptive estimation of quantum observables
• FABLE: Fast Approximate Quantum Circuits for Block-Encodings
• Decision Diagrams for Quantum Measurements with Shallow Circuits
• Adaptive Pauli Shadows for Energy Estimation
• Explicit Quantum Circuits for Block Encodings of Certain Sparse Matrices
• Quantum Davidson Algorithm for Excited States
• Quantum simulation by qubitization without Toffoli gates
• Say NO to Optimization: A Non-Orthogonal Quantum Eigensolver

Cited by in corpus (41)

• Challenges and Opportunities in Quantum Optimization
• Quantum Dynamics in Krylov Space: Methods and Applications
• Early Fault-Tolerant Quantum Computing
• Quantum-centric Supercomputing for Materials Science: A Perspective on Challenges and Future Directions
• Variational Benchmarks for Quantum Many-Body Problems
• Nuclear shell-model simulation in digital quantum computers
• Hunting for quantum-classical crossover in condensed matter problems
• Quantum entanglement patterns in the structure of atomic nuclei within the nuclear shell model
• Quantum-centric computation of molecular excited states with extended sample-based quantum diagonalization
• Quantum-Selected Configuration Interaction: classical diagonalization of Hamiltonians in subspaces selected by quantum computers
• Nearly-optimal state preparation for quantum simulations of lattice gauge theories
• Diagonalization of large many-body Hamiltonians on a quantum processor
• Analysis of quantum Krylov algorithms with errors
• PauliComposer: Compute Tensor Products of Pauli Matrices Efficiently
• Spin coupling is all you need: Encoding strong electron correlation in molecules on quantum computers
• Algorithmic Shadow Spectroscopy
• Krylov Subspace Methods for Quantum Dynamics with Time-Dependent Generators
• Quantum state preparation for multivariate functions
• Measurement-efficient quantum Krylov subspace diagonalisation
• Quantum subspace expansion in the presence of hardware noise
• Quantum Computed Green's Functions using a Cumulant Expansion of the Lanczos Method
• Quantum simulation of discrete linear dynamical systems and simple iterative methods in linear algebra via Schrodingerisation
• Efficient Strategies for Reducing Sampling Error in Quantum Krylov Subspace Diagonalization
• Double-bracket quantum algorithms for quantum imaginary-time evolution
• A Quantum Algorithmic Approach to Multiconfigurational Valence Bond Theory: Insights from Interpretable Circuit Design
• Precision ground-state energy calculation for the water molecule on a superconducting quantum processor
• Molecular Properties from Quantum Krylov Subspace Diagonalization
• Solving lattice gauge theories using the quantum Krylov algorithm and qubitization
• Partitioned Quantum Subspace Expansion
• Emergent random matrix universality in quantum operator dynamics
• Estimating Eigenenergies from Quantum Dynamics: A Unified Noise-Resilient Measurement-Driven Approach
• Reducing circuit depth with qubitwise diagonalization
• Systematic many-fermion Hamiltonian input scheme and spectral calculations on quantum computers
• NISQ algorithm for the matrix elements of a generic observable
• Quantum implicit representation of vortex filaments in turbulence
• Adiabatic state preparation from general initial states
• Numerical investigation of the quantum inverse algorithm on small molecules
• Hybrid Quantum-Classical Clustering for Preparing a Prior Distribution of Eigenspectrum
• A penalty-free quantum algorithm to find energy eigenstates
• Perturbation theory, irrep truncations, and state preparation methods for quantum simulations of SU(3) lattice gauge theory
• Variational Quantum Subspace Construction via Symmetry-Preserving Cost Functions