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 (41)

• Quantum algorithm for solving linear systems of equations
• A Quantum Approximate Optimization Algorithm
• Continuous-time Monte Carlo methods for quantum impurity models
• Adiabatic Quantum Computing
• Quantum Amplitude Amplification and Estimation
• Hamiltonian Simulation by Qubitization
• Exponential algorithmic speedup by quantum walk
• Optimal Hamiltonian Simulation by Quantum Signal Processing
• Simulating Hamiltonian dynamics with a truncated Taylor series
• Efficient quantum algorithms for simulating sparse Hamiltonians
• Quantum algorithm for systems of linear equations with exponentially improved dependence on precision
• Bounds for the adiabatic approximation with applications to quantum computation
• Quantum Metropolis Sampling
• Preconditioned quantum linear system algorithm
• Low Depth Quantum Simulation of Electronic Structure
• Hybrid quantum-classical approach to correlated materials
• A quantum linear system algorithm for dense matrices
• The power of quantum systems on a line
• Sampling from the thermal quantum Gibbs state and evaluating partition functions with a quantum computer
• Variational Quantum Linear Solver
• Quantum algorithm and circuit design solving the Poisson equation
• Quantum algorithms for systems of linear equations inspired by adiabatic quantum computing
• Variational algorithms for linear algebra
• Near-optimal ground state preparation
• Tomography and Generative Data Modeling via Quantum Boltzmann Training
• A Quantum-Quantum Metropolis Algorithm
• Efficient phase-factor evaluation in quantum signal processing
• The methodology of resonant equiangular composite quantum gates
• Quantum Algorithms for Simulating the Lattice Schwinger Model
• Quantum principal component analysis only achieves an exponential speedup because of its state preparation assumptions
• Quantum-inspired algorithms in practice
• Preparing ground states of quantum many-body systems on a quantum computer
• Optimal polynomial based quantum eigenstate filtering with application to solving quantum linear systems
• Compilation of Fault-Tolerant Quantum Heuristics for Combinatorial Optimization
• Calculation of the Green's function on near-term quantum computers
• Quantum SDP-Solvers: Better upper and lower bounds
• Product Decomposition of Periodic Functions in Quantum Signal Processing
• Quantum computation of molecular response properties
• Finding Angles for Quantum Signal Processing with Machine Precision
• Quantum Circulant Preconditioner for Linear System of Equations
• Quantum linear system solver based on time-optimal adiabatic quantum computing and quantum approximate optimization algorithm

Cited by in corpus (49)

• 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
• Random circuit block-encoded matrix and a proposal of quantum LINPACK benchmark
• 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
• Quantum simulation of discrete linear dynamical systems and simple iterative methods in linear algebra via Schrodingerisation
• Computation of Green's function by local variational quantum compilation
• 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
• Mixing Time of Open Quantum Systems via Hypocoercivity
• Explicit block encodings of boundary value problems for many-body elliptic operators
• Halving the Cost of Quantum Algorithms with Randomization
• Limitations of the Macaulay matrix approach for using the HHL algorithm to solve multivariate polynomial systems
• 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
• Quantum algorithms for spectral sums
• Simulating optically-active spin defects with a quantum computer
• 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
• Quantum linear system algorithm with optimal queries to initial state preparation
• Dissipative ground state preparation in ab initio electronic structure theory
• Optimizing Quantum Chemistry Simulations with a Hybrid Quantization Scheme
• Preconditioned Block Encodings for Quantum Linear Systems
• Improving quantum linear system solvers via a gradient descent perspective
• Quantum Algorithm for Matrix Logarithm by Integral Formula
• Block encoding the 3D heterogeneous Poisson equation with application to fracture flow
• Optimal Hamiltonian recognition of unknown quantum dynamics