The power of block-encoded matrix powers: improved regression techniques via faster Hamiltonian simulation

Abstract

We apply the framework of block-encodings, introduced by Low and Chuang (under the name standard-form), to the study of quantum machine learning algorithms and derive general results that are applicable to a variety of input models, including sparse matrix oracles and matrices stored in a data structure. We develop several tools within the block-encoding framework, such as singular value estimation of a block-encoded matrix, and quantum linear system solvers using block-encodings. The presented results give new techniques for Hamiltonian simulation of non-sparse matrices, which could be relevant for certain quantum chemistry applications, and which in turn imply an exponential improvement in the dependence on precision in quantum linear systems solvers for non-sparse matrices. In addition, we develop a technique of variable-time amplitude estimation, based on Ambainis' variable-time amplitude amplification technique, which we are also able to apply within the framework. As applications, we design the following algorithms: (1) a quantum algorithm for the quantum weighted least squares problem, exhibiting a 6-th power improvement in the dependence on the condition number and an exponential improvement in the dependence on the precision over the previous best algorithm of Kerenidis and Prakash; (2) the first quantum algorithm for the quantum generalized least squares problem; and (3) quantum algorithms for estimating electrical-network quantities, including effective resistance and dissipated power, improving upon previous work.

58 pages

References in corpus (5)

• Quantum random access memory
• Simulating Hamiltonian dynamics with a truncated Taylor series
• Quantum simulation of time-dependent Hamiltonians and the convenient illusion of Hilbert space
• Creating superpositions that correspond to efficiently integrable probability distributions
• Quantum Walks and Electric Networks

Cited by in corpus (46)

• Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics
• Variational Quantum Linear Solver
• Optimal polynomial based quantum eigenstate filtering with application to solving quantum linear systems
• Improved quantum algorithms for linear and nonlinear differential equations
• On the representation of Boolean and real functions as Hamiltonians for quantum computing
• Trading T gates for dirty qubits in state preparation and unitary synthesis
• Time-marching based quantum solvers for time-dependent linear differential equations
• General quantum algorithms for Hamiltonian simulation with applications to a non-Abelian lattice gauge theory
• An improved quantum-inspired algorithm for linear regression
• Computing Ground State Properties with Early Fault-Tolerant Quantum Computers
• Towards quantum advantage via topological data analysis
• Block-encoding structured matrices for data input in quantum computing
• Time-dependent Hamiltonian Simulation of Highly Oscillatory Dynamics and Superconvergence for Schrödinger Equation
• Efficient quantum amplitude encoding of polynomial functions
• Quantum algorithms for Second-Order Cone Programming and Support Vector Machines
• Quantum Deep Hedging
• Implementing any Linear Combination of Unitaries on Intermediate-term Quantum Computers
• Tower: Data Structures in Quantum Superposition
• Quantum algorithm for Neighborhood Preserving Embedding
• Quantum Regularized Least Squares
• Perturbation theory with quantum signal processing
• Block-encoding dense and full-rank kernels using hierarchical matrices: applications in quantum numerical linear algebra
• Spacetime-Efficient Low-Depth Quantum State Preparation with Applications
• Quantum exploration algorithms for multi-armed bandits
• Quantum algorithms for scientific computing
• Quantum Next Generation Reservoir Computing: An Efficient Quantum Algorithm for Forecasting Quantum Dynamics
• Quantum algorithms for SVD-based data representation and analysis
• Parallel Quantum Algorithm for Hamiltonian Simulation
• Fast digital methods for adiabatic state preparation
• Tight Bound for Estimating Expectation Values from a System of Linear Equations
• End-to-end complexity for simulating the Schwinger model on quantum computers
• Limitations of the Macaulay matrix approach for using the HHL algorithm to solve multivariate polynomial systems
• Quantum advantage from energy measurements of many-body quantum systems
• An Early Investigation of the HHL Quantum Linear Solver for Scientific Applications
• Quantum Algorithms for the Pathwise Lasso
• Nearly-frustration-free ground state preparation
• Dictionary-based Block Encoding of Sparse Matrices with Low Subnormalization and Circuit Depth
• Double-bracket algorithm for quantum signal processing without post-selection
• Parallelization techniques for quantum simulation of fermionic systems
• QKAN: quantum Kolmogorov-Arnold networks with applications in machine learning and multivariate state preparation
• On solving classes of positive-definite quantum linear systems with quadratically improved runtime in the condition number
• Des-q: a quantum algorithm to provably speedup retraining of decision trees
• Unstructured Adiabatic Quantum Optimization: Optimality with Limitations
• Quantum linear system algorithm with optimal queries to initial state preparation
• Lower bounds for quantum-inspired classical algorithms via communication complexity
• Quantum Computation