Quantum gradient descent for linear systems and least squares

Abstract

Quantum machine learning and optimization are exciting new areas that have been brought forward by the breakthrough quantum algorithm of Harrow, Hassidim and Lloyd for solving systems of linear equations. The utility of {classical} linear system solvers extends beyond linear algebra as they can be leveraged to solve optimization problems using iterative methods like gradient descent. In this work, we provide the first quantum method for performing gradient descent when the gradient is an affine function. Performing $\tau$ steps of the gradient descent requires time $O(\tau C_S)$ for weighted least squares problems, where $C_S$ is the cost of performing one step of the gradient descent quantumly, which at times can be considerably smaller than the classical cost. We illustrate our method by providing two applications: first, for solving positive semidefinite linear systems, and, second, for performing stochastic gradient descent for the weighted least squares problem with reduced quantum memory requirements. We also provide a quantum linear system solver in the QRAM data structure model that provides significant savings in cost for large families of matrices.

References in corpus (7)

• Quantum algorithm for solving linear systems of equations
• Quantum Data Fitting
• Architectures for a quantum random access memory
• A quantum linear system algorithm for dense matrices
• Quantum algorithm for linear differential equations with exponentially improved dependence on precision
• q-means: A quantum algorithm for unsupervised machine learning
• Quantum basin hopping with gradient-based local optimisation

Cited by in corpus (65)

• Quantum-assisted quantum compiling
• Quantum computing for finance
• Challenges and Opportunities in Quantum Optimization
• q-means: A quantum algorithm for unsupervised machine learning
• Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning
• A Hardware-Aware Heuristic for the Qubit Mapping Problem in the NISQ Era
• Quantum Algorithms for Deep Convolutional Neural Networks
• Quantum Spectral Clustering
• Resilience of quantum random access memory to generic noise
• Quantum linear systems algorithms: a primer
• Quantum classification of the MNIST dataset with Slow Feature Analysis
• Enabling Multi-programming Mechanism for Quantum Computing in the NISQ Era
• An improved quantum-inspired algorithm for linear regression
• Practical Quantum Computing: solving the wave equation using a quantum approach
• Towards quantum advantage via topological data analysis
• Quantum Machine Learning for Finance
• Advances in Quantum Deep Learning: An Overview
• Style-based quantum generative adversarial networks for Monte Carlo events
• Prospects and challenges of quantum finance
• Machine learning \& artificial intelligence in the quantum domain
• Quantum algorithms and lower bounds for convex optimization
• Quantum algorithms for Second-Order Cone Programming and Support Vector Machines
• Quantum Differentially Private Sparse Regression Learning
• Quantum Reinforcement Learning via Policy Iteration
• Quantum Circulant Preconditioner for Linear System of Equations
• Optimizing a Polynomial Function on a Quantum Simulator
• Dual-Parameterized Quantum Circuit GAN Model in High Energy Physics
• Evaluating the Potential of Quantum Machine Learning in Cybersecurity: A Case-Study on PCA-based Intrusion Detection Systems
• Quantum Regularized Least Squares
• Quantum Algorithms to Matrix Multiplication
• Quantum Language Processing
• Quantum advantage for differential equation analysis
• Quantum Generative Adversarial Networks For Anomaly Detection In High Energy Physics
• Quantum circuit synthesis using Householder transformations
• Quantum Gradient Algorithm for General Polynomials
• Quantum Expectation-Maximization for Gaussian Mixture Models
• Fast Black-Box Quantum State Preparation Based on Linear Combination of Unitaries
• Quantum Gram-Schmidt Processes and Their Application to Efficient State Read-out for Quantum Algorithms
• A Quantum-inspired Algorithm for General Minimum Conical Hull Problems
• Quantum algorithms for SVD-based data representation and analysis
• Statistical Limits of Supervised Quantum Learning
• Synergies Between Operations Research and Quantum Information Science
• Linear Regression by Quantum Amplitude Estimation and its Extension to Convex Optimization
• Generation of True Quantum Random Numbers with On-Demand Probability Distributions via Single-Photon Quantum Walks
• From linear combination of quantum states to Grover's searching algorithm
• An Early Investigation of the HHL Quantum Linear Solver for Scientific Applications
• Quantum random access memory with transmon-controlled phonon routing
• Accelerating the drive towards energy-efficient generative AI with quantum computing algorithms
• The Inductive Bias of Quantum Kernels
• Quantum Algorithms for the Pathwise Lasso
• The Role of Quantum Computing in Advancing Scientific High-Performance Computing: A perspective from the ADAC Institute
• Dictionary-based Block Encoding of Sparse Matrices with Low Subnormalization and Circuit Depth
• Quantum algorithms for spectral sums
• Quantum Bayesian Neural Networks
• QFCNN: Quantum Fourier Convolutional Neural Network
• Quantum tensor singular value decomposition with applications to recommendation systems
• Faster Coherent Quantum Algorithms for Phase, Energy, and Amplitude Estimation
• A quantum-inspired algorithm for approximating statistical leverage scores
• Quantum Regularized Least Squares Solver with Parameter Estimate
• Quantum Arnoldi and conjugate gradient iteration algorithm
• Quantum Algorithm for Online Convex Optimization
• The quantum version of the shifted power method and its application in quadratic binary optimization
• Improving quantum linear system solvers via a gradient descent perspective
• Quantum Algorithms for Unsupervised Machine Learning and Neural Networks
• Quantum multi-row iteration algorithm for linear systems with non-square coefficient matrices