Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userQuantum-inspired sublinear classical algorithms for solving low-rank linear systems
97
0
0.0
(
0
)
Added by
Chunhao Wang
Publication date
2018
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We present classical sublinear-time algorithms for solving low-rank linear systems of equations. Our algorithms are inspired by the HHL quantum algorithm for solving linear systems and the recent breakthrough by Tang of dequantizing the quantum algorithm for recommendation systems. Let $A in mathbb{C}^{m times n}$ be a rank-$k$ matrix, and $b in mathbb{C}^m$ be a vector. We present two algorithms: a sampling algorithm that provides a sample from $A^{-1}b$ and a query algorithm that outputs an estimate of an entry of $A^{-1}b$, where $A^{-1}$ denotes the Moore-Penrose pseudo-inverse. Both of our algorithms have query and time complexity $O(mathrm{poly}(k, kappa, |A|_F, 1/epsilon),mathrm{polylog}(m, n))$, where $kappa$ is the condition number of $A$ and $epsilon$ is the precision parameter. Note that the algorithms we consider are sublinear time, so they cannot write and read the whole matrix or vectors. In this paper, we assume that $A$ and $b$ come with well-known low-overhead data structures such that entries of $A$ and $b$ can be sampled according to some natural probability distributions. Alternatively, when $A$ is positive semidefinite, our algorithms can be adapted so that the sampling assumption on $b$ is not required.
rate research
Read More
Semidefinite programming (SDP) is a central topic in mathematical optimization with extensive studies on its efficient solvers. In this paper, we present a proof-of-principle sublinear-time algorithm for solving SDPs with low-rank constraints; specifically, given an SDP with $m$ constraint matrices, each of dimension $n$ and rank $r$, our algorithm can compute any entry and efficient descriptions of the spectral decomposition of the solution matrix. The algorithm runs in time $O(mcdotmathrm{poly}(log n,r,1/varepsilon))$ given access to a sampling-based low-overhead data structure for the constraint matrices, where $varepsilon$ is the precision of the solution. In addition, we apply our algorithm to a quantum state learning task as an application. Technically, our approach aligns with 1) SDP solvers based on the matrix multiplicative weight (MMW) framework by Arora and Kale [TOC 12]; 2) sampling-based dequantizing framework pioneered by Tang [STOC 19]. In order to compute the matrix exponential required in the MMW framework, we introduce two new techniques that may be of independent interest: $bullet$ Weighted sampling: assuming sampling access to each individual constraint matrix $A_{1},ldots,A_{tau}$, we propose a procedure that gives a good approximation of $A=A_{1}+cdots+A_{tau}$. $bullet$ Symmetric approximation: we propose a sampling procedure that gives the emph{spectral decomposition} of a low-rank Hermitian matrix $A$. To the best of our knowledge, this is the first sampling-based algorithm for spectral decomposition, as previous works only give singular values and vectors.
We establish an improved classical algorithm for solving linear systems in a model analogous to the QRAM that is used by quantum linear solvers. Precisely, for the linear system $Ax = b$, we show that there is a classical algorithm that outputs a data structure for $x$ allowing sampling and querying to the entries, where $x$ is such that $|x - A^{-1}b|leq epsilon |A^{-1}b|$. This output can be viewed as a classical analogue to the output of quantum linear solvers. The complexity of our algorithm is $widetilde{O}(kappa_F^6 kappa^2/epsilon^2 )$, where $kappa_F = |A|_F|A^{-1}|$ and $kappa = |A||A^{-1}|$. This improves the previous best algorithm [Gily{e}n, Song and Tang, arXiv:2009.07268] of complexity $widetilde{O}(kappa_F^6 kappa^6/epsilon^4)$. Our algorithm is based on the randomized Kaczmarz method, which is a particular case of stochastic gradient descent. We also find that when $A$ is row sparse, this method already returns an approximate solution $x$ in time $widetilde{O}(kappa_F^2)$, while the best quantum algorithm known returns $ket{x}$ in time $widetilde{O}(kappa_F)$ when $A$ is stored in the QRAM data structure. As a result, assuming access to QRAM and if $A$ is row sparse, the speedup based on current quantum algorithms is quadratic.
We investigate sublinear classical and quantum algorithms for matrix games, a fundamental problem in optimization and machine learning, with provable guarantees. Given a matrix $Ainmathbb{R}^{ntimes d}$, sublinear algorithms for the matrix game $min_{xinmathcal{X}}max_{yinmathcal{Y}} y^{top} Ax$ were previously known only for two special cases: (1) $mathcal{Y}$ being the $ell_{1}$-norm unit ball, and (2) $mathcal{X}$ being either the $ell_{1}$- or the $ell_{2}$-norm unit ball. We give a sublinear classical algorithm that can interpolate smoothly between these two cases: for any fixed $qin (1,2]$, we solve the matrix game where $mathcal{X}$ is a $ell_{q}$-norm unit ball within additive error $epsilon$ in time $tilde{O}((n+d)/{epsilon^{2}})$. We also provide a corresponding sublinear quantum algorithm that solves the same task in time $tilde{O}((sqrt{n}+sqrt{d})textrm{poly}(1/epsilon))$ with a quadratic improvement in both $n$ and $d$. Both our classical and quantum algorithms are optimal in the dimension parameters $n$ and $d$ up to poly-logarithmic factors. Finally, we propose sublinear classical and quantum algorithms for the approximate Caratheodory problem and the $ell_{q}$-margin support vector machines as applications.
We present an algorithmic framework for quantum-inspired classical algorithms on close-to-low-rank matrices, generalizing the series of results started by Tangs breakthrough quantum-inspired algorithm for recommendation systems [STOC19]. Motivated by quantum linear algebra algorithms and the quantum singular value transformation (SVT) framework of Gilyen et al. [STOC19], we develop classical algorithms for SVT that run in time independent of input dimension, under suitable quantum-inspired sampling assumptions. Our results give compelling evidence that in the corresponding QRAM data structure input model, quantum SVT does not yield exponential quantum speedups. Since the quantum SVT framework generalizes essentially all known techniques for quantum linear algebra, our results, combined with sampling lemmas from previous work, suffice to generalize all recent results about dequantizing quantum machine learning algorithms. In particular, our classical SVT framework recovers and often improves the dequantization results on recommendation systems, principal component analysis, supervised clustering, support vector machines, low-rank regression, and semidefinite program solving. We also give additional dequantization results on low-rank Hamiltonian simulation and discriminant analysis. Our improvements come from identifying the key feature of the quantum-inspired input model that is at the core of all prior quantum-inspired results: $ell^2$-norm sampling can approximate matrix products in time independent of their dimension. We reduce all our main results to this fact, making our exposition concise, self-contained, and intuitive.
We investigate quantum algorithms for classification, a fundamental problem in machine learning, with provable guarantees. Given $n$ $d$-dimensional data points, the state-of-the-art (and optimal) classical algorithm for training classifiers with constant margin runs in $tilde{O}(n+d)$ time. We design sublinear quantum algorithms for the same task running in $tilde{O}(sqrt{n} +sqrt{d})$ time, a quadratic improvement in both $n$ and $d$. Moreover, our algorithms use the standard quantization of the classical input and generate the same classical output, suggesting minimal overheads when used as subroutines for end-to-end applications. We also demonstrate a tight lower bound (up to poly-log factors) and discuss the possibility of implementation on near-term quantum machines. As a side result, we also give sublinear quantum algorithms for approximating the equilibria of $n$-dimensional matrix zero-sum games with optimal complexity $tilde{Theta}(sqrt{n})$.
suggested questions
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
