#  Parametrized Complexity of Quantum Inspired Algorithms

Ebrahim Ardeshir-Larijani  Institute for Research in Fundamental Sciences
(IPM), Iran
<EMAIL_ADDRESS>
(December 2021)

###### Contents

  1. 1 Introduction
  2. 2 Linear Algebraic Quantum Algorithms
    1. 2.1 Solving Linear systems of equations
    2. 2.2 Quantum Recommender System
    3. 2.3 –ً
    4. 2.4 Quantum singular value transformation
  3. 3 Quantum-Inspired Algorithms for Matrix Computation
    1. 3.1 Sample and Query Techniques
    2. 3.2 Quantum inspired Singular Value Transformation (SVT)
    3. 3.3 Methods from Randomized Numerical Algebra
  4. 4 Complexity Analysis of Quantum - Inspired Algorithms
    1. 4.1 Parametrized Complexity

##  1 Introduction

Motivated by recent progress in quantum technologies and in particular quantum
software, research and industrial communities have been trying to discover new
applications of quantum algorithms such as quantum optimization and machine
learning. Regardless of which hardware platform these novel algorithms operate
on, whether it is _adiabatic_ or _gate based_ , from theoretical point of
view, they are performing drastically better than their classical
counterparts.

One of the remarkable examples is the quantum algorithm for solving linear
systems of equations, introduced by Harow et. al. [15]. At its core, this
algorithm uses the “quantum phase estimation” procedure, which is used in many
important quantum algorithms. For the input matrix $A\in\mathbb{C}^{N\times
N}$, where $N$ is dimension, and $Ax=b$, where $x,b\in\mathbb{C}^{N}$, and
assuming that $A$, is $s$-sparse, that is at least $s$ entry at each row of
the matrix is zero, the HHL algorithm terminates with time complexity
$O(log(N)s^{2}\kappa^{2}/\epsilon)$. Here $\kappa$ and $\epsilon$ are
condition number and approximation constant, respectively. The best classical
algorithm for this problem has the complexity of $O(Ns\kappa
log(1/\epsilon))$. As we will detail briefly in the next section, the HHL
algorithm has the following characteristics:

  * •

It assumes that data, such as vector $b$, is _already_ loaded to a quantum
state, such that quantum operations become possible on it.

  * •

It assumes there is an efficient oracle that simulate Hamiltonians.

  * •

As for solution, it produces approximation of a function of solution.

Many quantum optimization and machine learning algorithms are based on
performing matrix operations using quantum states and operation, in order to
speed up data analysis. The main intuition behind Linear Algebra based quantum
machine learning [4], is that data analytic deals with high dimensional vector
spaces, where quantum computing can efficiently work with them. This is in
contrast with many classical algorithms of matrix computation, where
efficiency can be conditionally met, e.g. assuming _low rank_ and _sparsity_
of input matrices.

In the Section 2, we review quantum recommendation system [16] algorithm as
one example of linear algebraic quantum machine learning and optimization
algorithm. We review new remarkable result [21] that how a classical algorithm
can replace the quantum algorithm of recommendation system, only with poly
logarithmic overhead. The main concept behind this algorithm is to drop the
assumption of loading data into quantum states (as explained above for HHL).
To this end we use a tailored data structure (QRAM), that can deal with both
quantum and classical input, as well as a process called ”dequantization”,
which produces a novel classical algorithms for problems such as
recommendation systems and principal component analysis [17]. This process
replaces quantum state preparation with “ _sampling and query_ ” assumptions.
The claim in [16] is that for the current applications, the latter assumptions
are easier to satisfy than quantum state preparation. Formally, for a quantum
protocol
$P({\left|{\phi_{1}}\right\rangle},\ldots,{\left|{\phi_{n}}\right\rangle})={\left|{\psi}\right\rangle}$,
dequantization means that we replace quantum state preparation with a
classical sampling and query algorithm:
$SQ(\phi_{1},\ldots,\phi_{n})=SQ(\psi)$.

In Section 3.2, another line of research in terms of singular value
transformation (SVT) is described. This is based on a recent algorithm for
quantum SVT [14]. Combining concepts of [21] and quantum SVT, we end up with a
classical algorithm that under suitable sampling assumptions, computes SVT,
independent of the dimension of the input matrices [6]. This work generalizes
the current trends of quantum algorithms of quantum linear algebra in terms of
quantum SVT. Here the intuition is also built upon the fact that practical QML
and optimization algorithms assume constraints on the input (e.g. sparsity)
and generally loading input data into an input quantum state and extracting
amplitude data from an output quantum state are hard.

A fundamental goal of quantum-inspired algorithms is to reduce dimensionality
of input matrices to speed up linear algebra computations. Therefore, using
matrix sketching techniques is natural here. The work [5] uses tools from
randomized numerical linear Algebra to obtain significant improvements in the
sublinear terms for the dynamic (fast updates to the input matrix) and static
settings. Its analysis relies on simulating _leverage score sampling_ and
_ridge leverage score sampling_ , using a _weight-balanced_ data structure
that samples matrices rows proportional to squared Euclidean norm ($l_{2}$
norm). This method will be reviewed in Section 3.3.

From computational complexity point of view, the described quantum inspired
algorithms are exponentially faster than their classical versions, given that
the input satisfy some constraints. However, compared to their quantum
counterparts, they suffer computational (polynomial) overhead. This raises the
question, how these quantum inspired algorithms perform in practice? The work
of Arrazola et. al. [2], tries to answer this question and concludes that the
so called algorithms are in fact very promising in practical setting and
benchmarks, by ensuring some stringent conditions are satisfied.

Studying the research mentioned above, motivates us to understand where the
actual bottlenecks of the recent quantum inspired algorithms are? The
complexity dependence to the input structure points us that perhaps the input
size is not an appropriate measure of complexity, and hence we resort to
_Parametrized Complexity_ [8]. To this end we review some works in the area of
parametrized complexity that we might find possible links to the above quantum
inspired algorithms. In [9], parametrized complexity of classical PCA is
studied. Furthermore, we review the work about rigidity problem [10]. Moreover
the works [3, 10] describe some recent work in the area of parametrized
algorithm, relevant to machine learning and optimization. Finally, we review
the parametrized complexity of _matrix factorization_ [24], a concept that is
used in recommender system extensively.

##  2 Linear Algebraic Quantum Algorithms

In this section, first we review the HHL algorithm for solving linear systems
of equation. Then we review the algorithm of Lloyd et. al. [17], for the
problem of principal component analysis (PCA), which is widely used in the
area of machine learning. Finally, we review the Quantum Singular Value
Transformation algorithm [14], which is a unification methods for quantum
algorithms based on quantum phase estimation, in a single algorithm.

###  2.1 Solving Linear systems of equations

A linear system of equation can be described by an equation of the form
$Ax=b$, where $A$ is a matrix and $b$ and $x$ are vectors of finite dimension,
e.g. $N$. In our case, $A\in\mathbb{C}^{N\times N}$ and
$x,b\in\mathbb{C}^{N}$. The goal is to find (estimate) the solution, i.e. $x$.
The algorithm [15], uses a sub algorithm, like many other quantum algorithm,
for phase estimation. For a description of this useful and important algorithm
see [18]. Here we only describe what the phase estimation does.

Suppose $U\in\mathbb{C}^{2^{m}\times 2^{m}}$ be a unitary matrix and
${\left|{\psi}\right\rangle}_{m}\in\mathbb{C}^{2^{m}}$ be its eigenvectors
with associated eigenvalue $e^{2\pi i\theta}$. The _Quantum Phase Estimation
(QPE)_ , approximates $\theta$ for given unitary matrix. More formally:

$QPE(U,{\left|{0}\right\rangle}_{n},{\left|{\psi}\right\rangle}_{m})={\left|{\hat{\theta}}\right\rangle}_{n}{\left|{\psi}\right\rangle}_{m}$

Where binary approximation of $2^{n}\theta$, truncated to $n$ digits is
denoted by $\hat{\theta}$. In the case of HHL algorithm, the unitary $U$ has
the form of $e^{iAt}$, where $A$ is the matrix coming from linear system of
equations. Furthermore, we can rewrite $U$ as following:

$e^{iAt}=\sum_{j=0}^{N-1}e^{i\lambda_{j}t}{\left|{u_{j}}\right\rangle}{\left\langle{u_{j}}\right|}$

Now, with eigenvector ${\left|{u_{j}}\right\rangle}_{n_{b}}$ and eigenvalue
$e^{i\lambda_{j}t}$, the QPE outputs
${\left|{\hat{\lambda_{j}}}\right\rangle}_{n_{l}}{\left|{u_{j}}\right\rangle}_{n_{b}}$.
Here the $\hat{\lambda_{j}}$ is $n_{l}$-bit binary approximation to
$2^{n_{l}}\frac{\lambda_{j}t}{2\pi}$.

Now we can describe HHL algorithm for solving linear system of equation in six
main steps. Schematically, these are shown in Figure 1 , in the language of
quantum circuits [18]. Here we have three quantum registers. One is used for
storage of binary representation (indexed by $n_{l}$) eigenvalue of $A$. We
also a register to load vector $b$, indexed by $n_{b}$, and hence the
dimension of the problem is $N=2^{n_{b}}$. Note that we have ancillary qubits
in a third register, indexed by $n_{a}$.

Figure 1: HHL Algorithm steps

The description of the algorithm is as following 111for a detailed description
and also a numerical example and implementation please have look
at:https://qiskit.org/textbook/ch-applications/hhl_tutorial.html

  1. 1.

Loading vector $b$ into the quantum state
${\left|{b}\right\rangle}\in\mathbb{C}^{N}$, i.e. applying the transformation:
${\left|{0}\right\rangle}_{n_{b}}\mapsto{\left|{b}\right\rangle}_{n_{b}}$.

  2. 2.

Applying QPE to the unitary $U=e^{iAt}$. Now the quantum register has the
state:

$\sum_{j=0}^{N-1}b_{j}{\left|{\lambda_{j}}\right\rangle}_{n_{l}}{\left|{u_{j}}\right\rangle}_{n_{b}}$

here the $n_{l}$-bit binary representation of $\lambda_{j}$ is encoded by
${\left|{\lambda_{j}}\right\rangle}_{n_{l}}$.

  3. 3.

Apply a conditional rotation on ${\left|{\lambda_{j}}\right\rangle}_{n_{l}}$
and add auxiliary qubit (first row in Figure 1).

  4. 4.

Apply $QPR^{\dagger}$.

  5. 5.

Measure auxiliary qubit in computational basis. If the outcome is $1$, then
the register would be in post-measurement state:

$\sqrt{\frac{1}{\sum_{j=0}^{N-1}|b_{j}|^{2}/|\lambda_{j}|^{2}}}\sum_{j=0}^{N-1}\frac{b_{j}}{\lambda_{j}}{\left|{0}\right\rangle}_{n_{l}}{\left|{u_{j}}\right\rangle}_{n_{b}}$

which corresponds to the solution up to the normalization factor.

  6. 6.

Apply an observable $M$ to calculate
$F(x)={\left\langle{x}\right|}M{\left|{x}\right\rangle}$.

###  2.2 Quantum Recommender System

In recommendation system, the goal is to use information on purchase/rating of
$n$ products/services by a group of $m$ clients, to provide personalize
recommendation to individual clients. This information is modeled by a
$m\times n$ preference matrix, where the entries indicates how user $i$
evaluates $j$. The challenge is the preference matrix is not known a priori,
such that by looking into the high evaluation make good recommendation to the
users. The information from clients are received online. So the goal is to
infer a good approximation of preference matrix that reflects high value
rating.

One important characteristics of preference matrix in recommender systems are
that they are _low rank_. This is because users interests fall in certain
types, not all of the products.

The first algorithm by Kerenidis et. al. [16], uses a technique to reconstruct
the a low matrix approximation by using samples (available information) of
preference matrix, up to a measure of matrices, e.g. $l_{2}$ or Frobenius
norms.

The result of sampling technique and matrix reconstruction of quantum
recommender systems is an online computation that requires
$O(poly(k)polylog(mn))$, where $k$ is the rank of the input matrix.

One important assumption of [16] is that there is an efficient algorithm and
data structure to load classical matrix into quantum states. Theorem 2 shows
with the assumption that the transformation $A\mapsto{\left|{A}\right\rangle}$
can be done efficiently, we can store the input of quantum recommendation
system optimally. However, this assumption is dropped in [21]. More details on
the algorithm and in particular sampling technique can be found in [16]. We
will detail some aspects of sampling in the next section.

######  Theorem 1.

[16] Let $A\in\mathbb{R}^{m\times n}$ be a matrix. The input of the
recommendation system with the format $(i,j,A_{ij})$ coming in arbitrary
order. Let $w$ be the number of input that already been taken. Then, there
exists a data structure to store the input of the recommendation system with
the following features:

  1. 1.

The overall size of the data structure is $O(w.log^{2}(mn))$.

  2. 2.

The processing time for storing new input is $O(log^{2}(mn))$.

  3. 3.

Let $\tilde{A}\in\mathbb{R}^{m}$ defined by $\tilde{A_{i}}=||A_{i}||$. A
quantum algorithm with access to this data structure can perform the following
mappings in time $polylog(mn)$:
$\tilde{U}:{\left|{i}\right\rangle}{\left|{0}\right\rangle}\mapsto{\left|{i}\right\rangle}{\left|{A_{i}}\right\rangle}$
for $i\in[m]$, and
$\tilde{V}:{\left|{0}\right\rangle}{\left|{j}\right\rangle}\mapsto{\left|{\tilde{A}}\right\rangle}{\left|{j}\right\rangle}$
for $j\in[m]$ (projecting $A$ rows and columns, respectively).

###  2.3 –ً

Quantum principal component analysis One of the widely used dimension
reduction techniques for large data sets is principal component analysis
(PCA). In PCA we use spectral decomposition of matrices in terms of
eigenvectors and corresponding eigenvalues, and discards eigenvalues below
certain threshold, to obtain a good low rank approximation of the input
matrix. Let data are represented by $d$-dimensional vectors $v_{j}$. Then the
covariance matrix $C$ illustrate the correlation between different components
of the data and is defined as $C=\sum_{j}v_{j}v_{j}^{T}$. Then PCA diagonalize
the covariance matrix:

$C=\sum_{k}e_{k}c_{k}c_{k}^{\dagger}$

Now only a few eigenvalues $e_{k}$ are non-zeor or sufficiently large and the
rest could be discarded. The remaining called principal components and any
given data vector $v$, can be succinctly described by these $k$ components:
$v=\sum_{k}e_{k}c_{k}$. This operation requires $O(d^{2})$ in terms of time
and query complexity. The quantum algorithm for PCA [17], in the first step
needs to map a randomly chosen classical data to a quantum state
$v_{j}\mapsto{\left|{v_{j}}\right\rangle}$. This is usually done with a
dedicated data structure,called QRAM. Because these data are picked in random,
the resulting state has the density matrix
$1/N\sum_{j}{\left|{v_{j}}\right\rangle}{\left\langle{v_{j}}\right|}$, where
$N$ is the size of the data set. This is in fact equals to covariance matrix
up to a constant factor. Now by incorporating a sampling technique [17] and
phase estimation (as in section 2.1) we can find estimation of eigenvalues and
corresponding eigenvectors:

${\left|{v}\right\rangle}\mapsto\sum_{k}v_{k}{\left|{c_{k}}\right\rangle}{\left|{\tilde{e_{k}}}\right\rangle}$

Now the properties of principal components of $C$ can be inferred from
measurements on the quantum representation of its eigenvectors. The time and
query complexity of this algorithm is $O((logN)^{2})$.

###  2.4 Quantum singular value transformation

The area of quantum algorithms involves with two types of algorithms: QPE
based (such as the algorithms described in the previous sections) and Quantum
Fourier Transformation algorithms [18] (such as Shor factorization). The aim
of Quantum singular value transformation (QSVT) [14], is to find a general
framework for QPE based algorithms. Many important applications of quantum
computing use spectral decomposition and transformations, and therefore use
QPE, which we reviewed some of them in the previous sections. Nevertheless,
these algorithms work with quantum states and need to perform encoding and
then reading measurement outcomes to learn certain properties up to a
specified precision $\epsilon$. Therefore the improvements in terms of
computational complexity of these algorithms is merely _polynomially_. Of
course for large scale optimization applications, such as semi-definite
quantum program solvers this polynomial improvement matters significantly
[23]. The central concept of QSVT is _projected unitary encoding_. Let $\Pi$
and $\tilde{\Pi}$ are orthonormal projectors. Let $U$ be any unitary. For an
operator $A$, we say $U$, $\Pi$ and $\tilde{\Pi}$ form a projected unitary
encoding, if we have: $A=\tilde{\Pi}U\Pi$. Let $P\in\mathbb{C}[x]$ be an odd
polynomial and $A=W\Sigma V^{\dagger}$ be a singular value decomposition
(SVD). Now the singular value transformation is defined by:

$P^{SV}(A):=WP(\Sigma)V^{\dagger}$

The main result of [14] is stated as following: For any odd polynomial of
degree $d$, i.e. $P\in\mathbb{C}[x]$, where $|P(x)|\leq 1$, there is a unitary
$U_{qsvt}$ which can be implemented by a quantum circuit consists of only $U$
and $U^{-1}$, $d$ times throughout, such that:

$A=\tilde{\Pi}U\Pi\Rightarrow P^{SV}(A)=\tilde{\Pi}U_{qsvt}\Pi$

See [14] for full details as well as examples.

##  3 Quantum-Inspired Algorithms for Matrix Computation

In this section we review the new trend in designing quantum inspired
algorithms, appeared in a series of publications [21, 13, 20]. We also review
the singular value transformation based technique [6]. In both frameworks, we
deal with dequantization concept, as described in introduction section.
Furthermore, we explore new techniques from [5], where more advanced sampling
methods for matrices such as leverage score, is used to achieve improvement.
Also new classical data structure to support dequantization is introduced in
this work. Our review captures the main ideas and drop most of technical
details for brevity.

###  3.1 Sample and Query Techniques

In this section we explain on of the central notions introduced in [21] and
the subsequent works. The goal is to construct a classical input model which
is close quantum input model (quantum state), while we maintain complexity of
sublinear time. To do so we define sampling and query access as following:

######  Definition 1.

We define query access model for $v\in\mathbb{C}^{n}$, denoted by $Q(v)$ and
sample and query model, denoted by $SQ(v)$:

  1. 1.

for all $i\in[n]$, we have oracle access and can query for $v(i)$. Similarly,
for a matrix $A\in\mathbb{C}^{m\times n}$, we have $Q(A)$ if for all
$(i,j)\in[m]\times[n]$, we can query for $A(i,j)$.

  2. 2.

We have sampling and query access, $SQ(v)$ if following conditions are met:

    1. (a)

For any $v$, we can query $Q(v)$.

    2. (b)

If we can get independent samples, $i$, over $[n]$ with the distribution
$D_{v}\in\mathbb{R}^{n}$, defined as $D_{v}:=|v(i)^{2}|/\|v\|^{2}$.

    3. (c)

We can query for $\|v\|$.

Note that in order to implement the above input model, we need a dedicated
(dynamic) data structure. In a typical Random Access Memory (RAM) model, query
access has linear computational complexity. However, we are interested in a
(classical) data structure that support sublinear access complexity. In [21]
uses a data structure that [16] uses for preparation of quantum states, which
satisfies all condition we need. One of the dynamic data structures which is
used by mentioned QML algorithms is a binary search tree, that leaf nodes
store $v_{i}$ using the weight $v_{i}^{2}$ and $sgn(v_{i})$. The interior
nodes weight is the sum of their children weights. For updating and entry, all
nodes above the corresponding leaf has to be updated. For sampling, start from
the root of tree and randomly choose a child, where the probability is
proportional to its weight. Note that because we mostly deal with sparse input
(such as recommendation systems), we only include non zero nodes in the tree.
Figure 2, shows and example of such tree for a vector $v\in\mathbb{R}^{4}$.

Figure 2: Dynamic binary search tree for storing inputs of quantum inspired
algorithms

Now we have the following lemma:

######  Lemma 1.

To store a vector $v\in\mathbb{R}^{n}$ with $w$ nonzero entries, there exists
a data structure, supporting the following operations:

  1. 1.

Querying and updating an entry of $v$ in $O(logn)$ time.

  2. 2.

Querying $\|v\|^{2}$ in $O(1)$ time.

  3. 3.

Sampling from $D_{v}$ in $O(logn)$ time.

Note that the actual format of the input in our problems is matrix so for a
matrix $A\in\mathbb{R}^{m\times n}$, we form a vector
$\tilde{A}\in\mathbb{R}^{m}$, where the $i^{th.}$ entry equals to $\|A_{i}\|$
($l_{2}$ norm of the $i^{th.}$ row of $A$). Then we have the following lemma
[21]

######  Lemma 2.

There exists a data structure storing a matrix $A\in\mathbb{R}^{m\times n}$
with $w$ nonzero entries in $O(wlogmn)$ space, supporting the following
operations:

  * •

Reading and updating an entry of $A$ in $O(logmn)$ time;

  * •

Finding $\tilde{A}_{i}$ in $O(logm)$ time;

  * •

Finding $(\|A\|_{F})^{2}$ (Frobenius norm) in $O(1)$ time;

  * •

Sampling from $D_{\tilde{A}}$ and $D_{A_{i}}$ in $O(logmn)$ time.

By having a copy of the data structure specified in Lemma 1 for each row of
$A$ and $\tilde{A}$ we can form the above data structure. This has all of the
desired properties, and in fact, is the data structure Kerenidis and Prakash
[16] use to prepare arbitrary quantum states, which enables our algorithm to
operate on the same input. Figure 3 shows an example of such data structure
for a matrix $A\in\mathbb{R}^{2\times 4}$.

Figure 3: Dynamic data structure for storing $A\in\mathbb{R}^{2\times 4}$

######  Theorem 2.

[[21]] Let $A$ be an input matrix that supports query and sampling as
specified in Lemma 2, suppose $i\in[m]$ be a row and $\sigma,\eta$ be singular
value thresholds for low rank approximation of $A$ (denoted by
$A_{\sigma,\eta}$). For a small $\epsilon$, there is a classical algorithm
that has an output distribution $\epsilon$-close to $D_{M_{i}}$, where
$M\in\mathbb{R}^{m\times n}$, satisfying
$\|M-A_{\sigma,\eta}\|_{F}\leq\epsilon\|A\|_{F}$, in query and time complexity

$O(poly(\frac{\|A\|_{F}}{\sigma},\frac{1}{\epsilon},\frac{1}{\eta},\frac{\|A_{i}\|}{\|D_{i}\|}))$

The Theorem 2 states its algorithm has a runtime indpendent of the input
dimension ($m,n$). To implement the needed sampling operations we need the
dynamic data structure of Lemma 2. Note that using that data structure will
incur additional $O(log(mn))$ overhead. Comparing this algorithm and the
quantum algorithm of [16], shows that in the quantum version of producing low
rank approximation, the dependence on $\epsilon$ is logarithmic, compare to
the classical quantum inspired version. Now by using the above theorem and
impose the constraint that linear algebraic operations should not add the cost
of reading a full row or column of the input, and by using a number of
sampling routines (see [21] for full details) and applying it to the input of
recommendation system, i.e. preference matrix, we have the following theorem:

######  Theorem 3.

[[21]] By applying Theorem 2 to the input model of recommendation system,
which uses the dynamic data structure in [16], we obtain the same complexity
bounds up to constant factors for small $\epsilon$.

For the PCA problem we use similar techniques of sampling and query. The
original algorithm of Lloyd et. al. [17] best performs in low rank setting
therefore we have the following problem:

######  Problem (PCA for low-rank matrices).

For a Given a matrix $A\in\mathbb{C}^{m\times n}$, where we have access to
$SQ(A)$ such that $AA^{\dagger}$ has top $k$ eigenvalues
$\\{\lambda_{i}\\}_{i=1}^{k}$ and eigenvectors $\\{v_{i}\\}_{i=1}^{k}$ , with
probability $\geq 1-\delta$, compute eigenvalue estimates
$\\{\hat{\lambda_{i}}\\}_{i=1}^{k}$ such that
$\sum_{i=1}^{k}|\hat{\lambda_{i}}-\lambda_{i}|\leq\epsilon Tr(AA^{\dagger})$
and eigenvectors $\\{\hat{v_{i}}\\}_{i=1}^{k}$, (with access to
$\\{SQ(\hat{v_{i}})\\}_{i=1}^{k}$) such that $\forall
i,\|v_{i}-\hat{v_{i}}\|\leq\epsilon$.

The quantum inspired algorithm in [20] exactly solve this problem by using
sampling techniques and low rank approximation. For details of its algorithm
see [20], page 3.

###  3.2 Quantum inspired Singular Value Transformation (SVT)

As we described in Section 2.4, the quantum algorithms based on phase
estimation can be generalized by transformation on singular values. In fact
transforming singular values is the crux of many machine learning methods. For
instance, QML algorithms such as quantum support vector machines [19],
principal component analysis [17], training Boltzmann machines for state
tomography [22], all are based on singular value transformation. Note that the
speed up in quantum algorithms stems from the ability of unitary operations in
describing evolution of quantum systems with exponential size. This leads to
the idea of block encoding of large matrices which is a special case of
projected encoding described in Section 2.4. However, the aim of this section
is to extract a sampling based methods [6] for the seminal work of quantum
singular transformation of [14]. The main result of [6] states that the for a
matrix $A\in\mathbb{C}^{m\times n}$, with access to
$ًُSQ(A)$,wecanobtainasuccinctcharacterizationofsingulartransformationof$A$,efficiently.\par\begin{mydef}[Even
singular value]Foragiven$A\in\mathbb{C}^{m\times
n}$andafunction$f:[0,\infty)\mapsto\mathbb{C}$,andSVDof$A=\sum\sigma_{i}u_{i}v_{i}^{\dagger}$,theevensingularvaluetransformationof$A$,definedas$f(\sqrt{AA^{\dagger}})=\sum
f(\sigma_{i})v_{i}v_{i}^{\dagger}$\end{mydef}\par\begin{myth}Assumeforatheinput$A\in\mathbb{C}^{m\times
n}$wehaveaccessto$ًُSQ(A)$Let$f:[0,\infty)\mapsto\mathbb{C}$suchthat$f$is$L$-\textit{Lipschitz}and$\bar{f}(x)=(f(x)-f(0))/x$.Thenforsmallenough$\epsilon,\delta\geq
0$,wecanfindasubsetof$A$^{\prime}rows,denotedby$R\in\mathbb{C}^{r\times
n}$andasubsetof$R$^{\prime}scolumn,denotedby$C\in\mathbb{C}^{r\times
c}$suchthat:$$Pr\,[\|R^{\dagger}\bar{f}(CC^{\dagger})R+f(0)I-f(A^{\dagger}A)\|\,>\epsilon]<\delta$$Ifsamplingandquerytakes$T$time,thenfinding$R$,$C$andcomputing$\bar{f}(CC^{\dagger})$hasthecomplexity$O(r^{2}c+rcT)$.\end{myth}\par
The$R^†
¯f(CC^†)R$in\cite[cite]{[\@@bibref{}{smpldeq}{}{}]}iscalled\emph{RUR}decomposition.InthatcasetheabovetheoremsaysthatRURdecompositionexpressesagoodapproximationofinputmatrixasalinearcombinationof$r^2$outerproductsofitsrows.See\cite[cite]{[\@@bibref{}{smpldeq}{}{}]}forthoroughdetails.$

###  3.3 Methods from Randomized Numerical Algebra

In the previous sections we drew parallels to quantum algorithms by
implementing the so called dequantization technique. One can observe the heavy
reliance of this technique on randomized numerical linear algebra, where low
matrix rank computation and matrix sketching has been used at large. In a
recent work [5] raises the following questions: Is the running time of quantum
inspired algorithms, that are based on sample and query techniques, and have
sublinear terms is improvable? Here the goal is to maintain the efficient
creation of the dynamic data structure in $O(nnz(A))$ of a given input matrix
$A$, and updating it in $O(log\leavevmode\nobreak\ n)$. Another question is
can we use a vast number of techniques in randomized numerical linear algebra
in this context? The main contribution of [5] is answering to the above
questions. Given the technicality of the methods in the context of numerical
linear algebra we refer the reader to the main text and we only give statement
of the improvement result for the quantum inspired algorithm for recommender
systems here. Sketching is a widely used solution for reducing dimensionality
of matrix computation. The goal is to find a new matrix with its rows (or
columns) are subset of the target matrix but still hold its main structures.
Lemma 9 of [5], summarizes the main sketching techniques, relevant to this
work. For a given $n\times d$ matrix $A$ of rank $k$, the lower bound for the
singular value $\sigma_{k}(A)$, is denoted by $\hat{\sigma_{k}}$. Let
$\psi_{\lambda}=\frac{\|A\|^{2}_{F}}{\lambda+\hat{\sigma_{k}}^{2}}$. Let
$\psi_{k}$ be the estimate of $\frac{||A||_{F}^{2}}{\sigma_{k}(A)^{2}}$. Now
Theorem 5, presents a sampling technique that compared to [21], has a lower
overhead and smaller relative error. For further details on how a dynamic data
structure can be constructed from sketching matrix, see [5].

######  Theorem 5.

[5] Let $A\in\mathbb{R}^{n\times d}$ is represented by a sampling data
structure. Let $k$ and $\epsilon$, be target rank and error parameter,
respectively. Suppose $A_{k}$ be the best $k$ rank approximation of $A$. Then
we can find sampling matrices $S$, $R$ and $W$ (a rank $k$ matrix) such that:

$||ARWSA-A||_{F}\leq(1+O(\epsilon))||A-A_{k}||_{F}$

with the running time:

$\tilde{O}(\epsilon^{-6}k^{3}+\epsilon^{-4}\psi_{\lambda}(\psi_{\lambda})+k^{2}+k\psi_{k})$

##  4 Complexity Analysis of Quantum - Inspired Algorithms

In this section we complement theoretical analysis of quantum inspired
algorithms that are based on sampling and query and matrix sketching
techniques, by reviewing implementation and numerical benchmarking, first
reported in [2]. The aim of such experiment is to acquire an understanding of
the _practical complexity_ of quantum inspired algorithms in terms of
_erroneous_ and _runtime_. The main finding is that although we have seen in
the previous sections a hefty polynomial overhead compare to quantum
algorithms, however in practice and in the case we only have indirect access
to massive data sets via query, quantum inspired algorithms performs very
well. This is a reminding to the fact that computational complexity of these
problems does not depend on the dimension of input, but other quality of the
input and the manner input is accessible. In the following we briefly report
on the findings of [2]. The first example concerns with sampling according to
the $l_{2}$ norm. For the dimension of less than $10^{6}$, using direct
sampling is faster than using dynamic data structure of [16] and [21]. The
Figure 4 illustrate the runtime of producing $1000$ sample of $l_{2}$ norm
distribution according to the dynamic data structure as explained previously
and direct sampling method.

Figure 4: Runtimes for generating one thousand samples from a length-square
distribution

The second example which we mention here (see more case studies and details in
[2]) is movie recommendation systems based on MovieLens 100K data set. It
consists of a preference matrix with 100,000 ratings from 611 users across
9,724 movies. where ratings are scaled within the range $[0.5,5]$. Here
majority of users watch only a small fraction of available movies, and
therefore the matrix is sparse. The preference matrix has full rank of
$k=611$, its largest and smallest singular values are respectively
$\sigma_{max}=534.4$, $\sigma_{min}=2.95$, and its condition number (for
$l_{2}$ norm $\frac{\sigma_{max}}{\sigma_{min}}$) is $\kappa=181.2$. The
algorithm tries to predict missing ratings and subsequently recommend movies
that have a high predicted rating, which we explained in Section 3. Figure 5
[2] compares the running times between the quantum-inspired algorithm and the
direct calculation method.

Figure 5: Running times (in seconds) for the quantum-inspired algorithm for
recommendation systems. The parameter $t_{LS}$ is the time required to
construct length-squared (LS) probability distributions over rows and columns

For small size matrices direct computation of SVD can be done in a shorter
time. The runtime of the quantum-inspired algorithm is dominated by the
coefficient estimation step, even when the resulting errors in estimating
these coefficient is relatively high. As a conclusion, the numerical examples
we mentioned here suggest that when applied to moderately-sized data sets,
because they rely on a more intricate procedure, the quantum-inspired
algorithms take more time than exact diagonalization, and because they rely on
sampling for coefficient estimation, lead to higher inaccuracies. These
results show that in order to provide a speedup over preexisting classical
algorithms, the quantum-inspired algorithms must be applied to _extremely
large_ data sets where exact diagonalization is impossible and where even the
linear scaling of SVD approximation algorithms (for example those based on
monte carlo methods such as FKV [11]) prevents its direct application. It is
also relevant to examine the complexity of quantum inspired algorithm where we
have perturbation in the input. This has be done in the context of smooth
analysis in a recent work of Dunjko et. al. [25]. They proved, using smooth
complexity that if the quantum (inspired) algorithm is robust against small
entry-wise input perturbation, state preparation can always be achieved with
constant queries. The entry-wise access is done by an oracle $O_{x}$, with an
arbitrary function $f(x)$:

$\sum_{i,j}]\alpha_{i,j}{\left|{i}\right\rangle}{\left|{j}\right\rangle}\xrightarrow{O_{f(x)}}\sum_{i,j}]\alpha_{i,j}{\left|{i}\right\rangle}{\left|{j+f(x_{i})}\right\rangle}$

For simplicity we assume $f(x_{i})=x_{i}$. Note that in the classical setting,
random access memory, provides the mapping $i\mapsto f(x_{i})$. Now generating
$l_{2}$ samples from entry-wise oracle and unstructured search has lower bound
$\Omega(D)$ queries for $x\in\mathbb{R}^{D}$. This can be achieved by QRAM
model 222The paper [25] techniques can be applied to both quantum and quantum
inspired algorithms. Here we mention results for quantum inspired setting. To
model noisy data input, it is assumed that Gaussian element wise perturbation
occurs. Subsequently, smooth complexity is defined.

######  Definition 3 (Smooth Complexity [25]).

Given an algorithm $A$ with an input domain $\Omega_{D}=\mathbb{R}^{D}$, the
smoothed complexity of $A$with $\sigma$-Gaussian perturbation is defined as:

$max_{x\in[-1,1]^{D}}\mathbb{E}_{g}[T_{A}(x+g)]$

Here $g$ is a Gaussian random vector with variance $\sigma^{2}$, and $T_{A}$
denotes the runtime of $A$. Having defined smooth complexity, the main result
of [25] is the following theorem:

######  Theorem 6.

Given oracle access, $O_{x}$ to the entries of $x\in\mathbb{R}^{D}$, the
amplitude encoding of $x$ into ${\left|{x}\right\rangle}$ (state preparation)
has smoothed complexity $O(1/\sigma)$.

###  4.1 Parametrized Complexity

In this section we review some works in the context of classical algorithms
that may have relevance to parametrized complexity analysis. The goal of our
project is to extend parametrized complexity concepts to the quantum inspired
algorithms which we explained in the previous sections. A central concept in
parametrized complexity [8] is _Fixed Parameter Tractability (FPT)_. For FPT
algorithm, the performance is heavily depends on some _fixed parameters_
rather than the _input size_. So we can view these problems in sliced way
where each slice corresponds to a tractable problem. Another important concept
is ”kernelization” [8], where we reduce the parametrized input to a new
parametrization where the algorithm performs better. The formal definition of
FPT is as following:

######  Definition 4.

[Fixed parameter tractable] We say an algorithm $A$ is FPT if for all
parametrized input $\langle x,k\rangle$, constant $c$, and a commutable
function $f$, $A$ has a running time $f(k)|x|^{c}$. Here $c$ is independent
from $|x|$ and $k$.

Parametrized algorithms with higher complexity belong to $XP$, where the
complexity bound is in terms of commutable function $f$ and $g$ :
$f(k)|x|^{g(k)}$. The first example concerns with recommendation system (which
we explained its quantum version in Section 2.2). Here ([24]) the problem
formulated as “ _weighted low rank approximation_ ” and “matrix completion
problems”. The formal definition of these problems are as following:

######  Definition 5.

[Weighted low rank approximation]

$\textit{Input:}\leavevmode\nobreak\ A\in\mathbb{R}^{n\times
n},W\in\mathbb{R}^{n\times n},k\in\mathbb{N},\epsilon>0$
$\textit{Output:}\leavevmode\nobreak\ U,V^{T}\in\mathbb{R}^{n\times
k}s.t.\|W\circ(UV-A)\|_{F}\leq(1+\epsilon)OPT$

Where $OPT:=Min_{A}^{\prime}\|W\circ(A^{\prime}-A)\|_{F},rank(A^{\prime})\leq
k$

In the matrix completion problem, we are given a matrix with missing entries
and the task is to complete the matrix in a way that (1) minimizes the number
of distinct rows and columns, (2) minimizes the number of distinct column, or
(1) minimizes the rank. It is shown in [12] that this problem is FPT for
bounded domain.

######  Definition 6 (matrix completion problem).

$\textit{Input:}\leavevmode\nobreak\
A\in\\{\mathbb{R},?\\},\leavevmode\nobreak\ \textit{known
entries}\leavevmode\nobreak\ \Omega\in[n]\times[n],k\in\mathbb{N}$
$\textit{Output:}\leavevmode\nobreak\ A_{\bar{\Omega}}\leavevmode\nobreak\
s.t.\leavevmode\nobreak\ rank(A)=k$

Now the [24], considers the weighted low rank approximation with these three
parametrizations.

######  Theorem 7.

For a given matrix $A\in\mathbb{R}^{n\times n}$, $W\in\mathbb{R}^{n\times n}$,
$r,k\in\mathbb{N}$ and $\epsilon>0$:

  1. 1.

with $r$ distinct rows and columns, computing $\hat{A}=UV$ as in Definition 5,
with probability $9/10$ can be done in
$O(nnz(A)+nnz(W)+n^{\gamma}))+n2^{O(k^{2}r/\epsilon)}$, for arbitrary small
$\gamma$, and hence is in FPT.

  2. 2.

with $r$ distinct columns, computing $\hat{A}=UV$ as in Definition 5, with
probability $9/10$ can be done in
$O(nnz(A)+nnz(W)+n^{\gamma}))+n2^{O(k^{2}r^{2}/\epsilon)}$, for arbitrary
small $\gamma$, and hence is in FPT.

  3. 3.

with rank $r$, computing $\hat{A}=UV$ as in Definition 5, with probability
$9/10$ can be done in $O(n^{O(k^{2}r/\epsilon)}$, and hence is in FPT.

Our second example concerns with PCA as mentioned in Section 2.3. In [9] and
[7], Fomin et. al. showed that for the _robust PCA_ and _PCA with outliers_
problems there are exact and randomized FPT algorithms. Their results are
based on the relation of these problems with the _matrix rigidity_ problem
[10]. A normal PCA formulation (as in Section 2.3) is not robust against
corrupted observations. For a data $M\in\mathbb{R}^{d\times n}$, robust PCA
models outliers as additive sparse matrix $S$. Thus we have a superposition of
a low-rank component $L$ and a sparse component $S$ : $M=L+S$. Now the robust
PCA is as following:

$\textit{minimize}\leavevmode\nobreak\ rank(L)+nnz(S)\leavevmode\nobreak\
s.t.M=L+S$

On the other hand robust PCA is equivalent to matrix rigidity problem: for a
matrix $M\in\mathbb{R}^{d\times n}$, suppose updating at most $k$ entries
operation is denoted by $\textit{update}^{k}(M)$, then the following problem:

$M^{\prime}=\textit{update}^{k}(M)\leavevmode\nobreak\
s.t.\leavevmode\nobreak\ rank(M^{\prime})\leq r$

is called matrix rigidity problem.

######  Theorem 8 ([10]).

The problem of max rigidity (robust PCA) is solvable in
$poly(M)2^{O((r+k)log(kr))}$, thus FPT, parametrized by $r+k$.

Note that this problem is NP-complete for $r\geq 0$. Another formulation is
called _PCA with outliers_. The parametrized complexity of this problem in
both classical and approximation setting is studied in [7, 9]. Here the
problem is as following: “Given a set of $n$ points in $\mathbb{R}^{d}$ with
(unknown) $k$ outliers, the problem is to identify the outliers so that the
remaining set of points fits best into an unknown $r$-dimensional subspace”
One can interpret this problem in the following geometrical setting: “Given
$n$ points in $\mathbb{R}^{d}$, represented by the rows of $A$, we seek for a
set of $k$ outliers, represented by the non-zero rows of $N$, whose removal
from $A$ leaves the remaining $n-k$ inliers as close as possible to an
$r$-dimensional subspace. The matrix $L$ contains then the orthogonal
projections of the inliers onto this subspace” Now the formal definition of
the PCA with outliers is shown in Figure 6.

Figure 6: PCA with outliers

The algorithms of [9] reduces the problem to iteration of normal PCA as in the
following theorem:

######  Theorem 9.

Solving PCA with outliers is reducible to solving $|A|^{O(n^{2})}$ instances
of PCA. since only iterative algorithms for PCA and SVD exist, this algorithm
does not solves PCA with outliers in a fixed number of operations. However, up
to some constant precision, PCA is solvable in polynomial number of operations

Moreover by using computational complexity assertion that is called
Exponential Time Hypothesis (ETH) [1], they improved Theorem 9 to achieve
fixed parameter tractability. Roughly ETH says that for $k\geq 3$, and
$\delta_{k}>0$, $k$-SATISFIABILITY problem with $n$ variables and $m$ clauses
cannot be solved in time $O(2^{\delta_{k}n}(n+m)^{O(1)})$. This means that
$k$-SATISFIABILITY cannot be solved in subexponential in $n$ time. Now the
following theorem is shown in [9]:

######  Theorem 10.

For any $\epsilon\geq 1$, there is no $\epsilon$-approximation algorithm for
PCA with outliers with running time $f(d)\,N^{o(d)}$ for any commutable
function $f$ unless ETH fails, where $N$ is the bitsize of the input matrix.

One way to circumvent ETH assumption is to consider fixed rank setting. This
is investigated in [7], resulting in several approximation algorithm for PCA
with outlier. Here we conclude this section with the following theorem, and
refer the reader to [7] for further details.

######  Theorem 11.

For every $\epsilon>0$, an $1+\epsilon$-approximate solution to PCA with
outliers can be found in time $n^{O(\frac{r\ log\ r}{\epsilon^{2}})}\
d^{O(1)}$

######  Conjecture 1.

Quantum inspired algorithm for recommendation system and PCA, that are based
on low rank approximation and also dependent to sample and query technique,
are FPT, using appropriate parametrization.

## References

  * [1] Which problems have strongly exponential complexity?  Journal of Computer and System Sciences, 63(4):512–530, 2001.
  * [2] Juan Miguel Arrazola, Alain Delgado, Bhaskar Roy Bardhan, and Seth Lloyd.  Quantum-inspired algorithms in practice.  Quantum, 4:307, August 2020.
  * [3] Sayan Bandyapadhyay, Fedor V. Fomin, Petr A. Golovach, and Kirill Simonov.  Parameterized complexity of feature selection for categorical data clustering.  CoRR, abs/2105.03753, 2021.
  * [4] Jacob D. Biamonte, Peter Wittek, Nicola Pancotti, Patrick Rebentrost, Nathan Wiebe, and Seth Lloyd.  Quantum machine learning.  Nature, 549(7671):195–202, 2017.
  * [5] Nadiia Chepurko, Kenneth L. Clarkson, Lior Horesh, and David P. Woodruff.  Quantum-inspired algorithms from randomized numerical linear algebra.  CoRR, abs/2011.04125, 2020.
  * [6] Nai-Hui Chia, András Gilyén, Tongyang Li, Han-Hsuan Lin, Ewin Tang, and Chunhao Wang.  Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning.  In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, page 387–400, New York, NY, USA, 2020. Association for Computing Machinery.
  * [7] Yogesh Dahiya, Fedor V. Fomin, Fahad Panolan, and Kirill Simonov.  Fixed-parameter and approximation algorithms for PCA with outliers.  In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pages 2341–2351. PMLR, 2021.
  * [8] Rodney G. Downey and Michael R. Fellows.  Fundamentals of Parameterized Complexity.  Springer Publishing Company, Incorporated, 1st edition, 2016.
  * [9] Fedor V. Fomin, Petr A. Golovach, and Kirill Simonov.  Parameterized Complexity of PCA (Invited Talk).  In Susanne Albers, editor, 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020), volume 162 of Leibniz International Proceedings in Informatics (LIPIcs), pages 1:1–1:5, Dagstuhl, Germany, 2020. Schloss Dagstuhl–Leibniz-Zentrum für Informatik.
  * [10] Fedor V. Fomin, Daniel Lokshtanov, S. M. Meesum, Saket Saurabh, and Meirav Zehavi.  Matrix Rigidity from the Viewpoint of Parameterized Complexity.  In Heribert Vollmer and Brigitte Vallée, editors, 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017), volume 66 of Leibniz International Proceedings in Informatics (LIPIcs), pages 32:1–32:14, Dagstuhl, Germany, 2017. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
  * [11] Alan Frieze, Ravi Kannan, and Santosh Vempala.  Fast monte-carlo algorithms for finding low-rank approximations.  J. ACM, 51(6):1025–1041, November 2004.
  * [12] Robert Ganian, Iyad A. Kanj, Sebastian Ordyniak, and Stefan Szeider.  Parameterized algorithms for the matrix completion problem.  In Jennifer G. Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässan, Stockholm, Sweden, July 10-15, 2018, volume 80 of Proceedings of Machine Learning Research, pages 1642–1651. PMLR, 2018\.
  * [13] András Gilyén, Zhao Song, and Ewin Tang.  An improved quantum-inspired algorithm for linear regression.  CoRR, abs/2009.07268, 2020.
  * [14] András Gilyén, Yuan Su, Guang Hao Low, and Nathan Wiebe.  Quantum singular value transformation and beyond: Exponential improvements for quantum matrix arithmetics.  In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, page 193–204, New York, NY, USA, 2019. Association for Computing Machinery.
  * [15] Aram W. Harrow, Avinatan Hassidim, and Seth Lloyd.  Quantum algorithm for linear systems of equations.  Phys. Rev. Lett., 103:150502, Oct 2009.
  * [16] Iordanis Kerenidis and Anupam Prakash.  Quantum Recommendation Systems.  In Christos H. Papadimitriou, editor, 8th Innovations in Theoretical Computer Science Conference (ITCS 2017), volume 67 of Leibniz International Proceedings in Informatics (LIPIcs), pages 49:1–49:21, Dagstuhl, Germany, 2017. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
  * [17] Seth Lloyd, Masoud Mohseni, and Patrick Rebentrost.  Quantum principal component analysis.  Nature Physics, 10(9):631–633, Jul 2014.
  * [18] Michael A. Nielsen and Isaac L. Chuang.  Quantum Computation and Quantum Information: 10th Anniversary Edition.  Cambridge University Press, 2010.
  * [19] Patrick Rebentrost, Masoud Mohseni, and Seth Lloyd.  Quantum support vector machine for big data classification.  Phys. Rev. Lett., 113:130503, Sep 2014.
  * [20] Ewin Tang.  Quantum-inspired classical algorithms for principal component analysis and supervised clustering.  CoRR, abs/1811.00414, 2018.
  * [21] Ewin Tang.  A quantum-inspired classical algorithm for recommendation systems.  In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, page 217–228, New York, NY, USA, 2019. Association for Computing Machinery.
  * [22] Giacomo Torlai, Guglielmo Mazzola, Juan Carrasquilla, Matthias Troyer, Roger Melko, and Giuseppe Carleo.  Neural-network quantum state tomography.  Nature Physics, 14(5):447–450, February 2018.
  * [23] Joran van Apeldoorn and András Gilyén.  Improvements in Quantum SDP-Solving with Applications.  In Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi, editors, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), volume 132 of Leibniz International Proceedings in Informatics (LIPIcs), pages 99:1–99:15, Dagstuhl, Germany, 2019. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
  * [24] David P Woodruff.  Parameterized complexity of matrix factorization.  2017\.
  * [25] Zhikuan Zhao, Jack K. Fitzsimons, Patrick Rebentrost, Vedran Dunjko, and Joseph F. Fitzsimons.  Smooth input preparation for quantum and quantum-inspired machine learning.  Quantum Mach. Intell., 3(1):1–6, 2021.