Source author record

Anupam Prakash

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

quant-ph Data Structures and Algorithms Computational Complexity Information Retrieval Machine Learning

Catalog footprint

Research overview

7works

5topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Low depth algorithms for quantum amplitude estimation

We design and analyze two new low depth algorithms for amplitude estimation (AE) achieving an optimal tradeoff between the quantum speedup and circuit depth. For $β\in (0,1]$ , our algorithms require $N= \tilde{O}( \frac{1}{ ε^{1+β}})$ oracle calls and require the oracle to be called sequentially $D= O( \frac{1}{ ε^{1-β}})$ times to perform amplitude estimation within additive error $ε$ . These algorithms interpolate between the classical algorithm $(β=1)$ and the standard quantum algorithm ( $β=0$ ) and achieve a tradeoff $ND= O(1/ε^{2})$ . These algorithms bring quantum speedups for Monte Carlo methods closer to realization, as they can provide speedups with shallower circuits. The first algorithm (Power law AE) uses power law schedules in the framework introduced by Suzuki et al \cite{S20}. The algorithm works for $β\in (0,1]$ and has provable correctness guarantees when the log-likelihood function satisfies regularity conditions required for the Bernstein Von-Mises theorem. The second algorithm (QoPrime AE) uses the Chinese remainder theorem for combining lower depth estimates to achieve higher accuracy. The algorithm works for discrete $β=q/k$ where $k \geq 2$ is the number of distinct coprime moduli used by the algorithm and $1 \leq q \leq k-1$ , and has a fully rigorous correctness proof. We analyze both algorithms in the presence of depolarizing noise and provide numerical comparisons with the state of the art amplitude estimation algorithms.

preprint2022arXiv

Quantum machine learning with subspace states

We introduce a new approach for quantum linear algebra based on quantum subspace states and present three new quantum machine learning algorithms. The first is a quantum determinant sampling algorithm that samples from the distribution $\Pr[S]= det(X_{S}X_{S}^{T})$ for $|S|=d$ using $O(nd)$ gates and with circuit depth $O(d\log n)$ . The state of art classical algorithm for the task requires $O(d^{3})$ operations \cite{derezinski2019minimax}. The second is a quantum singular value estimation algorithm for compound matrices $\mathcal{A}^{k}$ , the speedup for this algorithm is potentially exponential. It decomposes a $\binom{n}{k}$ dimensional vector of order- $k$ correlations into a linear combination of subspace states corresponding to $k$ -tuples of singular vectors of $A$ . The third algorithm reduces exponentially the depth of circuits used in quantum topological data analysis from $O(n)$ to $O(\log n)$ . Our basic tool are quantum subspace states, defined as $|Col(X)\rangle = \sum_{S\subset [n], |S|=d} det(X_{S}) |S\rangle$ for matrices $X \in \mathbb{R}^{n \times d}$ such that $X^{T} X = I_{d}$ , that encode $d$ -dimensional subspaces of $\mathbb{R}^{n}$ . We develop two efficient state preparation techniques, the first using Givens circuits uses the representation of a subspace as a sequence of Givens rotations, while the second uses efficient implementations of unitaries $Γ(x) = \sum_{i} x_{i} Z^{\otimes (i-1)} \otimes X \otimes I^{n-i}$ with $O(\log n)$ depth circuits that we term Clifford loaders.

preprint2021arXiv

Quantum gradient descent for linear systems and least squares

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 $τ$ steps of the gradient descent requires time $O(τ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.

preprint2020arXiv

Quantum Expectation-Maximization for Gaussian Mixture Models

The Expectation-Maximization (EM) algorithm is a fundamental tool in unsupervised machine learning. It is often used as an efficient way to solve Maximum Likelihood (ML) estimation problems, especially for models with latent variables. It is also the algorithm of choice to fit mixture models: generative models that represent unlabelled points originating from $k$ different processes, as samples from $k$ multivariate distributions. In this work we define and use a quantum version of EM to fit a Gaussian Mixture Model. Given quantum access to a dataset of $n$ vectors of dimension $d$ , our algorithm has convergence and precision guarantees similar to the classical algorithm, but the runtime is only polylogarithmic in the number of elements in the training set, and is polynomial in other parameters - as the dimension of the feature space, and the number of components in the mixture. We generalize further the algorithm in two directions. First, we show how to fit any mixture model of probability distributions in the exponential family. Then, we show how to use this algorithm to compute the Maximum a Posteriori (MAP) estimate of a mixture model: the Bayesian approach to likelihood estimation problems. We discuss the performance of the algorithm on a dataset that is expected to be classified successfully by this algorithm, arguing that on those cases we can give strong guarantees on the runtime.

preprint2016arXiv

On the sum-of-squares degree of symmetric quadratic functions

We study how well functions over the boolean hypercube of the form $f_k(x)=(|x|-k)(|x|-k-1)$ can be approximated by sums of squares of low-degree polynomials, obtaining good bounds for the case of approximation in $\ell_{\infty}$ -norm as well as in $\ell_1$ -norm. We describe three complexity-theoretic applications: (1) a proof that the recent breakthrough lower bound of Lee, Raghavendra, and Steurer on the positive semidefinite extension complexity of the correlation and TSP polytopes cannot be improved further by showing better sum-of-squares degree lower bounds on $\ell_1$ -approximation of $f_k$ ; (2) a proof that Grigoriev's lower bound on the degree of Positivstellensatz refutations for the knapsack problem is optimal, answering an open question from his work; (3) bounds on the query complexity of quantum algorithms whose expected output approximates such functions.

preprint2016arXiv

Quantum Recommendation Systems

A recommendation system uses the past purchases or ratings of $n$ products by a group of $m$ users, in order to provide personalized recommendations to individual users. The information is modeled as an $m \times n$ preference matrix which is assumed to have a good rank- $k$ approximation, for a small constant $k$ . In this work, we present a quantum algorithm for recommendation systems that has running time $O(\text{poly}(k)\text{polylog}(mn))$ . All known classical algorithms for recommendation systems that work through reconstructing an approximation of the preference matrix run in time polynomial in the matrix dimension. Our algorithm provides good recommendations by sampling efficiently from an approximation of the preference matrix, without reconstructing the entire matrix. For this, we design an efficient quantum procedure to project a given vector onto the row space of a given matrix. This is the first algorithm for recommendation systems that runs in time polylogarithmic in the dimensions of the matrix and provides an example of a quantum machine learning algorithm for a real world application.

preprint2013arXiv

Computation in anonymous networks

We identify and investigate a computational model arising in molecular computing, social computing and sensor network. The model is made of of multiple agents who are computationally limited and posses no global information. The agents may represent nodes in a social network, sensors, or molecules in a molecular computer. Assuming that each agent is in one of $k$ states, we say that {\em the system computes} $f:[k]^{n} \to [k]$ if all agents eventually converge to the correct value of $f$ . We present number of general results characterizing the computational power of the mode. We further present protocols for computing the plurality function with $O(\log k)$ memory and for approximately counting the number of nodes of a given color with $O(\log \log n)$ memory, where $n$ is the number of agents in the networks. These results are tight.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.