Fast inversion, preconditioned quantum linear system solvers, and fast evaluation of matrix functions

Abstract

Preconditioning is the most widely used and effective way for treating ill-conditioned linear systems in the context of classical iterative linear system solvers. We introduce a quantum primitive called fast inversion, which can be used as a preconditioner for solving quantum linear systems. The key idea of fast inversion is to directly block-encode a matrix inverse through a quantum circuit implementing the inversion of eigenvalues via classical arithmetics. We demonstrate the application of preconditioned linear system solvers for computing single-particle Green's functions of quantum many-body systems, which are widely used in quantum physics, chemistry, and materials science. We analyze the complexities in three scenarios: the Hubbard model, the quantum many-body Hamiltonian in the planewave-dual basis, and the Schwinger model. We also provide a method for performing Green's function calculation in second quantization within a fixed particle manifold and note that this approach may be valuable for simulation more broadly. Besides solving linear systems, fast inversion also allows us to develop fast algorithms for computing matrix functions, such as the efficient preparation of Gibbs states. We introduce two efficient approaches for such a task, based on the contour integral formulation and the inverse transform respectively.

References in corpus (9)

• Quantum algorithm for solving linear systems of equations
• A Quantum Approximate Optimization Algorithm
• Continuous-time Monte Carlo methods for quantum impurity models
• Exponential algorithmic speedup by quantum walk
• Simulating Hamiltonian dynamics with a truncated Taylor series
• Bounds for the adiabatic approximation with applications to quantum computation
• The power of quantum systems on a line
• Quantum algorithm and circuit design solving the Poisson equation
• Compilation of Fault-Tolerant Quantum Heuristics for Combinatorial Optimization

Cited by in corpus (48)

• The Variational Quantum Eigensolver: a review of methods and best practices
• Linear combination of Hamiltonian simulation for nonunitary dynamics with optimal state preparation cost
• Time-marching based quantum solvers for time-dependent linear differential equations
• Quantum-accelerated multilevel Monte Carlo methods for stochastic differential equations in mathematical finance
• Variational Quantum Computation of Molecular Linear Response Properties on a Superconducting Quantum Processor
• Computing Ground State Properties with Early Fault-Tolerant Quantum Computers
• Enhancing the Quantum Linear Systems Algorithm using Richardson Extrapolation
• A variational quantum eigensolver for dynamic correlation functions
• Two-Unitary Decomposition Algorithm and Open Quantum System Simulation
• Real-Time Krylov Theory for Quantum Computing Algorithms
• Multivariable quantum signal processing (M-QSP): prophecies of the two-headed oracle
• Lanczos recursion on a quantum computer for the Green's function and ground state
• Quantum algorithms from fluctuation theorems: Thermal-state preparation
• Linear-depth quantum circuits for loading Fourier approximations of arbitrary functions
• Quantum Computing and Preconditioners for Hydrological Linear Systems
• A quantum hamiltonian simulation benchmark
• Qubit-Efficient Randomized Quantum Algorithms for Linear Algebra
• Perturbation theory with quantum signal processing
• On efficient quantum block encoding of pseudo-differential operators
• Block-encoding dense and full-rank kernels using hierarchical matrices: applications in quantum numerical linear algebra
• Quantum differential equation solvers: limitations and fast-forwarding
• On quantum algorithms for the Schrödinger equation in the semi-classical regime
• Quantum algorithms for matrix operations and linear systems of equations
• Quantum algorithm for linear non-unitary dynamics with near-optimal dependence on all parameters
• Computation of Green's function by local variational quantum compilation
• Quantum simulation of discrete linear dynamical systems and simple iterative methods in linear algebra via Schrodingerisation
• Quantum algorithms for group convolution, cross-correlation, and equivariant transformations
• Solving the Hele-Shaw flow using the Harrow-Hassidim-Lloyd algorithm on superconducting devices: A study of efficiency and challenges
• Entanglement-assisted phase estimation algorithm for calculating dynamical response functions
• Limitations of the Macaulay matrix approach for using the HHL algorithm to solve multivariate polynomial systems
• Halving the Cost of Quantum Algorithms with Randomization
• Mixing Time of Open Quantum Systems via Hypocoercivity
• Explicit block encodings of boundary value problems for many-body elliptic operators
• Near-term quantum algorithm for computing molecular and materials properties based on recursive variational series methods
• Quantum algorithms for calculating determinant and inverse of matrix and solving linear algebraic systems
• Simulating optically-active spin defects with a quantum computer
• Quantum algorithms for spectral sums
• On solving classes of positive-definite quantum linear systems with quadratically improved runtime in the condition number
• Quantum Realization of the Finite Element Method
• Quantum Machine Learning For Classical Data
• Optimizing Quantum Chemistry Simulations with a Hybrid Quantization Scheme
• Dissipative ground state preparation in ab initio electronic structure theory
• Quantum linear system algorithm with optimal queries to initial state preparation
• Improving quantum linear system solvers via a gradient descent perspective
• Quantum Algorithm for Matrix Logarithm by Integral Formula
• Optimal Hamiltonian recognition of unknown quantum dynamics
• Preconditioned Block Encodings for Quantum Linear Systems
• Block encoding the 3D heterogeneous Poisson equation with application to fracture flow