results for au:Prakash_A in:quant-ph

- Apr 21 2017 quant-ph arXiv:1704.06174v1Solving linear systems of equations is a frequently encountered problem in machine learning and optimisation. Given a matrix $A$ and a vector $\mathbf b$ the task is to find the vector $\mathbf x$ such that $A \mathbf x = \mathbf b$. We describe a quantum algorithm that achieves a sparsity-independent runtime scaling of $\mathcal{O}(\kappa^2 \|A\|_F \text{polylog}(n)/\epsilon)$, where $n\times n$ is the dimensionality of $A$ with Frobenius norm $\|A\|_F$, $\kappa$ denotes the condition number of $A$, and $\epsilon$ is the desired precision parameter. When applied to a dense matrix with spectral norm bounded by a constant, the runtime of the proposed algorithm is bounded by $\mathcal{O}(\kappa^2\sqrt{n} \text{polylog}(n)/\epsilon)$, which is a quadratic improvement over known quantum linear system algorithms. Our algorithm is built upon a singular value estimation subroutine, which makes use of a memory architecture that allows for efficient preparation of quantum states that correspond to the rows and row Frobenius norms of $A$.
- Apr 18 2017 quant-ph arXiv:1704.04992v2Quantum Machine Learning is an exciting new area that was initiated by the breakthrough quantum algorithm of Harrow, Hassidim, Lloyd \citeHHL09 for solving linear systems of equations and has since seen many interesting developments \citeLMR14, LMR13a, LMR14a, KP16. In this work, we start by providing a quantum linear system solver that outperforms the current ones for large families of matrices and provides exponential savings for any low-rank (even dense) matrix. Our algorithm uses an improved procedure for Singular Value Estimation which can be used to perform efficiently linear algebra operations, including matrix inversion and multiplication. Then, we provide the first quantum method for performing gradient descent for cases where the gradient is an affine function. Performing $\tau$ steps of the quantum gradient descent requires time $O(\tau C_S)$, where $C_S$ is the cost of performing quantumly one step of the gradient descent, which can be exponentially smaller than the cost of performing the step classically. We provide two applications of our quantum gradient descent algorithm: first, for solving positive semidefinite linear systems, and, second, for performing stochastic gradient descent for the weighted least squares problem.
- Nov 28 2016 quant-ph arXiv:1611.08053v1We identify certain classes of 1D symmetry-protected topological (SPT) phases in which almost every state is universal for measurement based quantum computation (MBQC) in 1D. By developing a general scheme to extract the useful entanglement from SPT ordered states, we can associate to each of these phases a Lie group of executable gates. We then show how to determine this Lie group from the cohomological description of SPT phases, thereby affirming the compelling link between SPT order and the computational power of 1D resource states.
- Sep 27 2016 quant-ph arXiv:1609.07549v1We investigate the usefulness of ground states of quantum spin chains with symmetry-protected topological order (SPTO) for measurement-based quantum computation. We show that, in spatial dimension one, if an SPTO phase supports quantum wire, then, subject to an additional symmetry condition that is satisfied in all cases so far investigated, it can also be used for quantum computation.
- An $n\times n$ matrix $X$ is called completely positive semidefinite (cpsd) if there exist $d\times d$ Hermitian positive semidefinite matrices $\{P_i\}_{i=1}^n$ (for some $d\ge 1$) such that $X_{ij}= {\rm Tr}(P_iP_j),$ for all $i,j \in \{ 1, \ldots, n \}$. The cpsd-rank of a cpsd matrix is the smallest $d\ge 1$ for which such a representation is possible. In this work we initiate the study of the cpsd-rank which we motivate twofold. First, the cpsd-rank is a natural non-commutative analogue of the completely positive rank of a completely positive matrix. Second, we show that the cpsd-rank is physically motivated as it can be used to upper and lower bound the size of a quantum system needed to generate a quantum behavior. In this work we present several properties of the cpsd-rank. Unlike the completely positive rank which is at most quadratic in the size of the matrix, no general upper bound is known on the cpsd-rank of a cpsd matrix. In fact, we show that the cpsd-rank can be exponential in terms of the size. Specifically, for any $n\ge1,$ we construct a cpsd matrix of size $2n$ whose cpsd-rank is $2^{\Omega(\sqrt{n})}$. Our construction is based on Gram matrices of Lorentz cone vectors, which we show are cpsd. The proof relies crucially on the connection between the cpsd-rank and quantum behaviors. In particular, we use a known lower bound on the size of matrix representations of extremal quantum correlations which we apply to high-rank extreme points of the $n$-dimensional elliptope. Lastly, we study cpsd-graphs, i.e., graphs $G$ with the property that every doubly nonnegative matrix whose support is given by $G$ is cpsd. We show that a graph is cpsd if and only if it has no odd cycle of length at least $5$ as a subgraph. This coincides with the characterization of cp-graphs.
- Apr 04 2016 cond-mat.str-el quant-ph arXiv:1604.00037v1We investigate the phase diagram of a quantum spin-1 chain whose Hamiltonian is invariant under a global onsite $A_4$, translation and lattice inversion symmetries. We detect different gapped phases characterized by SPT order and symmetry breaking using matrix product state order parameters. We observe a rich variety of phases of matter characterized by a combination of symmetry breaking and symmetry fractionalization and also the interplay between the onsite and spatial symmetries. Examples of continuous phase transitions directly between topologically nontrivial SPT phases are also observed.
- 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.
- 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.
- Oct 07 2014 quant-ph cond-mat.str-el arXiv:1410.0974v4The program of classifying symmetry protected topological (SPT) phases in 1D has been recently completed and has opened the doors to study closely the properties of systems belonging to these phases. It was recently found that being able to constrain the form of ground states of SPT order based on symmetry properties also allows to explore novel resource states for processing of quantum information. In this paper, we generalize the consideration of Else et al. [Phys. Rev. Lett. \bf 108, 240505 (2012)] where it was shown that the ground-state form of spin-1 chains protected by $\mathbb{Z}_2 \times \mathbb{Z}_2$ symmetry supports perfect operation of the identity gate, important also for long-distance transmission of quantum information. We develop a formalism to constrain the ground-state form of SPT phases protected by any arbitrary finite symmetry group and use it to examine examples of ground states of SPT phases protected by various finite groups for similar gate protections. We construct a particular Hamiltonian invariant under $A_4$ symmetry transformation which is one of the groups that allows protected identity operation and examine its ground states. We find that there is an extended region where the ground state is the AKLT state, which not only supports the identity gate but also arbitrary single-qubit gates.
- Sep 04 2007 quant-ph arXiv:0709.0063v2Using graphs and hypergraphs to systematically model collections of arbitrary subsets of parties representing \it ensembles (or collections) of shared multipartite CAT states, we study transformations between such \it ensembles under \it local operations and classical communication (LOCC). We show using partial entropic criteria, that any two such distinct ensembles represented by \it $r$-uniform hypergraphs with the same number of hyperedges (CAT states), are LOCC incomparable for even integers $r\geq 2$, generalizing results in \citemscthesis,sin:pal:kum:sri. We show that the cardinality of the largest set of mutually LOCC incomparable ensembles represented by $r$-uniform hypergraphs for even $r\geq 2$, is exponential in the number of parties. We also demonstrate LOCC incomparability between two ensembles represented by 3-uniform hypergraphs where partial entropic criteria do not help in establishing incomparability. Further we characterize LOCC comparability of EPR graphs in a model where LOCC is restricted to teleportation and edge destruction. We show that this model is equivalent to one in which LOCC transformations are carried out through a sequence of operations where each operation adds at most one new EPR pair.