Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userClassical and Quantum Algorithms for Tensor Principal Component Analysis
316
0
0.0
(
0
)
Authors
M. B. Hastings
Ask ChatGPT about the research
No Arabic abstract
We present classical and quantum algorithms based on spectral methods for a problem in tensor principal component analysis. The quantum algorithm achieves a quartic speedup while using exponentially smaller space than the fastest classical spectral algorithm, and a super-polynomial speedup over classical algorithms that use only polynomial space. The classical algorithms that we present are related to, but slightly different from those presented recently in Ref. 1. In particular, we have an improved threshold for recovery and the algorithms we present work for both even and odd order tensors. These results suggest that large-scale inference problems are a promising future application for quantum computers.
rate research
Read More
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.
Principal component analysis has been widely adopted to reduce the dimension of data while preserving the information. The quantum version of PCA (qPCA) can be used to analyze an unknown low-rank density matrix by rapidly revealing the principal components of it, i.e. the eigenvectors of the density matrix with largest eigenvalues. However, due to the substantial resource requirement, its experimental implementation remains challenging. Here, we develop a resonant analysis algorithm with the minimal resource for ancillary qubits, in which only one frequency scanning probe qubit is required to extract the principal components. In the experiment, we demonstrate the distillation of the first principal component of a 4$times$4 density matrix, with the efficiency of 86.0% and fidelity of 0.90. This work shows the speed-up ability of quantum algorithm in dimension reduction of data and thus could be used as part of quantum artificial intelligence algorithms in the future.
Principal component analysis is an important dimension reduction technique in machine learning. In [S. Lloyd, M. Mohseni and P. Rebentrost, Nature Physics 10, 631-633, (2014)], a quantum algorithm to implement principal component analysis on quantum computer was obtained by computing the Hamiltonian simulation of unknown density operators. The complexity is $O((log d)t^2/epsilon)$, where $d$ is the dimension, $t$ is the evolution time and $epsilon$ is the precision. We improve this result into $O((log d)t^{1+frac{1}{k}}/epsilon^{frac{1}{k}})$ for arbitrary constant integer $kgeq 1$. As a result, we show that the Hamiltonian simulation of low-rank dense Hermitian matrices can be implemented in the same time.
We study the performance of local quantum algorithms such as the Quantum Approximate Optimization Algorithm (QAOA) for the maximum cut problem, and their relationship to that of classical algorithms. (1) We prove that every (quantum or classical) one-local algorithm achieves on $D$-regular graphs of girth $> 5$ a maximum cut of at most $1/2 + C/sqrt{D}$ for $C=1/sqrt{2} approx 0.7071$. This is the first such result showing that one-local algorithms achieve a value bounded away from the true optimum for random graphs, which is $1/2 + P_*/sqrt{D} + o(1/sqrt{D})$ for $P_* approx 0.7632$. (2) We show that there is a classical $k$-local algorithm that achieves a value of $1/2 + C/sqrt{D} - O(1/sqrt{k})$ for $D$-regular graphs of girth $> 2k+1$, where $C = 2/pi approx 0.6366$. This is an algorithmic version of the existential bound of Lyons and is related to the algorithm of Aizenman, Lebowitz, and Ruelle (ALR) for the Sherrington-Kirkpatrick model. This bound is better than that achieved by the one-local and two-loc
Identifying the best arm of a multi-armed bandit is a central problem in bandit optimization. We study a quantum computational version of this problem with coherent oracle access to states encoding the reward probabilities of each arm as quantum amplitudes. Specifically, we show that we can find the best arm with fixed confidence using $tilde{O}bigl(sqrt{sum_{i=2}^nDelta^{smash{-2}}_i}bigr)$ quantum queries, where $Delta_{i}$ represents the difference between the mean reward of the best arm and the $i^text{th}$-best arm. This algorithm, based on variable-time amplitude amplification and estimation, gives a quadratic speedup compared to the best possible classical result. We also prove a matching quantum lower bound (up to poly-logarithmic factors).
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
