Quantum singular value estimation techniques for data representation

Most quantum algorithms offering speedups over classical algorithms are based on the three techniques of phase estimation, amplitude estimation and Hamiltonian simulation. In spite of the linear algebraic nature of the postulates of quantum mechanics, until recent work by Lloyd and coauthors cite{LMR13, LMR13a, LMR13b} no quantum algorithms achieving speedups for linear algebra or machine learning had been proposed. A quantum machine learning algorithm must address three issues: encoding of classical data into a succinct quantum representation, processing the quantum representation and extraction of classically useful information from the processed quantum state. In this dissertation, we make progress on all three aspects of the quantum machine learning problem and obtain quantum algorithms for low rank approximation and regularized least squares. The oracle $QRAM$ , the standard model studied in quantum query complexity, requires time $O(sqrt{n})$ to encode vectors $v in R^{n}$ into quantum states. We propose simple hardware augmentations to the oracle $QRAM$ , that enable vectors $v in R^{n}$ to be encoded in time $O(log n)$ , with pre-processing. The augmented $QRAM$ incurs minimal hardware overheads, the pre-processing can be parallelized and is a flexible model that allows storage of multiple vectors and matrices. It provides a framework for designing quantum algorithms for linear algebra and machine learning. Using the augmented $QRAM$ for vector state preparation, we present two different algorithms for singular value estimation where given singular vector $ket{v}$ for $A in R^{mtimes n}$ , the singular value $sigma_{i}$ is estimated within additive error $epsilon norm{A}_{F}$ . The first algorithm requires time $wt{1/epsilon^{3}}$ and uses the approach for simulating $e^{-i rho}$ in cite{LMR13}. However, the analysis cite{LMR13} does not establish the coherence of outputs, we provide a qualitatively different analysis that uses the quantum Zeno effect to establish coherence and reveals the probabilistic nature of the simulation technique. The second algorithm has a running time $wt{1/epsilon}$ and uses Jordan's lemma from linear algebra and the augmented $QRAM$ to implement reflections. We use quantum singular value estimation to obtain algorithms for low rank approximation by column selection, the algorithms are based on importance sampling from the leverage score distribution. We obtain quadratic speedups for a large class of linear algebra algorithms that rely on importance sampling from the leverage score distribution including approximate least squares and $CX$ and $CUR$ decompositions. Classical algorithms for these problems require time $O(mn log n + poly(1/epsilon))$ , the quantum algorithms have running time $O(sqrt{m}poly(1/epsilon, k, Delta))$ where $k, Delta$ are the rank and spectral gap. The running time of the quantum $CX$ decomposition algorithm does not depend on $m$ , it is polynomial in problem parameters. We also provide quantum algorithms for $ell_{2}$ regularized regression problems, the quantum ridge regression algorithm requires time $wt{1/mu^{2} delta}$ to output a quantum state that is $delta$ close to the solution, where $mu$ is the regularization parameter.Most quantum algorithms offering speedups over classical algorithms are based on the three techniques of phase estimation, amplitude estimation and Hamiltonian simulation. In spite of the linear algebraic nature of the postulates of quantum mechanics, until recent work by Lloyd and coauthors cite{LMR13, LMR13a, LMR13b} no quantum algorithms achieving speedups for linear algebra or machine learning had been proposed. A quantum machine learning algorithm must address three issues: encoding of classical data into a succinct quantum representation, processing the quantum representation and extraction of classically useful information from the processed quantum state. In this dissertation, we make progress on all three aspects of the quantum machine learning problem and obtain quantum algorithms for low rank approximation and regularized least squares. The oracle $QRAM$, the standard model studied in quantum query complexity, requires time $O(sqrt{n})$ to encode vectors $v in R^{n}$ into quantum states. We propose simple hardware augmentations to the oracle $QRAM$, that enable vectors $v in R^{n}$ to be encoded in time $O(log n)$, with pre-processing. The augmented $QRAM$ incurs minimal hardware overheads, the pre-processing can be parallelized and is a flexible model that allows storage of multiple vectors and matrices. It provides a framework for designing quantum algorithms for linear algebra and machine learning. Using the augmented $QRAM$ for vector state preparation, we present two different algorithms for singular value estimation where given singular vector $ket{v}$ for $A in R^{mtimes n}$, the singular value $sigma_{i}$ is estimated within additive error $epsilon norm{A}_{F}$. The first algorithm requires time $wt{1/epsilon^{3}}$ and uses the approach for simulating $e^{-i rho}$ in cite{LMR13}. However, the analysis cite{LMR13} does not establish the coherence of outputs, we provide a qualitatively different analysis that uses the quantum Zeno effect to establish coherence and reveals the probabilistic nature of the simulation technique. The second algorithm has a running time $wt{1/epsilon}$ and uses Jordan's lemma from linear algebra and the augmented $QRAM$ to implement reflections. We use quantum singular value estimation to obtain algorithms for low rank approximation by column selection, the algorithms are based on importance sampling from the leverage score distribution. We obtain quadratic speedups for a large class of linear algebra algorithms that rely on importance sampling from the leverage score distribution including approximate least squares and $CX$ and $CUR$ decompositions. Classical algorithms for these problems require time $O(mn log n + poly(1/epsilon))$, the quantum algorithms have running time $O(sqrt{m}poly(1/epsilon, k, Delta))$ where $k, Delta$ are the rank and spectral gap. The running time of the quantum $CX$ decomposition algorithm does not depend on $m$, it is polynomial in problem parameters. We also provide quantum algorithms for $ell_{2}$ regularized regression problems, the quantum ridge regression algorithm requires time $wt{1/mu^{2} delta}$ to output a quantum state that is $delta$ close to the solution, where $mu$ is the regularization parameter.

Jan 1, 201447 citations

Quantum Estimation

François Chapeau‐Blondeau

Springer eBooksJan 1, 20260 citations

Quantum generalized least squares method in system identification

Sadegh Kalantari, Ali Madady, Mehdi Ramezani

Quantum Information ProcessingJun 12, 20242 citations

Quantum algorithms for linear algebra and machine learning. - eScholarship

Anupam Prakash

Jan 1, 20140 citations

Quantum machine learning with subspace states

Iordanis Kerenidis, Anupam Prakash

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.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.

arXiv:2202.00054Jan 31, 202210 citations

An improved quantum algorithm for data fitting

Jiancheng Lei, Tingting Song, Ling Liu +1 more

Physica A Statistical Mechanics and its ApplicationsJan 30, 20234 citations

QRAM

, the standard model studied in quantum query complexity, requires time

O(sqrt{n})

to encode vectors

v in R^{n}

into quantum states. We propose simple hardware augmentations to the oracle

QRAM

, that enable vectors

v in R^{n}

to be encoded in time

O(log n)

, with pre-processing. The augmented

QRAM

incurs minimal hardware overheads, the pre-processing can be parallelized and is a flexible model that allows storage of multiple vectors and matrices. It provides a framework for designing quantum algorithms for linear algebra and machine learning. Using the augmented

QRAM

for vector state preparation, we present two different algorithms for singular value estimation where given singular vector

ket{v}

for

A in R^{mtimes n}

, the singular value

sigma_{i}

is estimated within additive error

epsilon norm{A}_{F}

. The first algorithm requires time

wt{1/epsilon^{3}}

and uses the approach for simulating

e^{-i rho}

in cite{LMR13}. However, the analysis cite{LMR13} does not establish the coherence of outputs, we provide a qualitatively different analysis that uses the quantum Zeno effect to establish coherence and reveals the probabilistic nature of the simulation technique. The second algorithm has a running time

wt{1/epsilon}

and uses Jordan's lemma from linear algebra and the augmented

QRAM

to implement reflections. We use quantum singular value estimation to obtain algorithms for low rank approximation by column selection, the algorithms are based on importance sampling from the leverage score distribution. We obtain quadratic speedups for a large class of linear algebra algorithms that rely on importance sampling from the leverage score distribution including approximate least squares and

CX

and

CUR

decompositions. Classical algorithms for these problems require time

O(mn log n + poly(1/epsilon))

, the quantum algorithms have running time

O(sqrt{m}poly(1/epsilon, k, Delta))

where

k, Delta

are the rank and spectral gap. The running time of the quantum

CX

decomposition algorithm does not depend on

m

, it is polynomial in problem parameters. We also provide quantum algorithms for

ell_{2}

regularized regression problems, the quantum ridge regression algorithm requires time

wt{1/mu^{2} delta}

to output a quantum state that is

delta

close to the solution, where

mu

is the regularization parameter.

QRAM

, the standard model studied in quantum query complexity, requires time

O(sqrt{n})

to encode vectors

v in R^{n}

into quantum states. We propose simple hardware augmentations to the oracle

QRAM

, that enable vectors

v in R^{n}

to be encoded in time

O(log n)

, with pre-processing. The augmented

QRAM

QRAM

for vector state preparation, we present two different algorithms for singular value estimation where given singular vector

ket{v}

for

A in R^{mtimes n}

, the singular value

sigma_{i}

is estimated within additive error

epsilon norm{A}_{F}

. The first algorithm requires time

wt{1/epsilon^{3}}

and uses the approach for simulating

e^{-i rho}

wt{1/epsilon}

and uses Jordan's lemma from linear algebra and the augmented

QRAM

CX

and

CUR

decompositions. Classical algorithms for these problems require time

O(mn log n + poly(1/epsilon))

, the quantum algorithms have running time

O(sqrt{m}poly(1/epsilon, k, Delta))

where

k, Delta

are the rank and spectral gap. The running time of the quantum

CX

decomposition algorithm does not depend on

m

, it is polynomial in problem parameters. We also provide quantum algorithms for

ell_{2}

regularized regression problems, the quantum ridge regression algorithm requires time

wt{1/mu^{2} delta}

to output a quantum state that is

delta

close to the solution, where

mu

is the regularization parameter.

\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)

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.