1.1 High-Dimensional Quantum Data Reduction Algorithm

Here, we will analyze matrix dimensionality reduction using qPCA. Let $\xi$ be the precision parameter and $p$ denote variance retained after dimensionality reduction. Given efficient quantum access to the matrix $A=U\mathrm{\Sigma }{V}^T$ $=$ $\sum _i^r{\sigma }_i{u}_i{v}_i^T\in {\mathbb{R}}^{n\times m}$, let the top $k$ right singular vectors ${\overline{V}}^{(k)}\in {\mathbb{R}}^{m\times k}$, where $\Vert V^{(k)}-{\overline{V}}^{(k)}\Vert$ $\le$ $\frac{\xi \sqrt{p}}{\sqrt{2}}$. There exists a quantum algorithm that creates $|\overline{Y}⟩$ $=$ $\frac{1}{\parallel Y{\parallel }_F}\sum _i^n\Vert y_{i,\cdot }\Vert |i⟩|y_{i,\cdot }⟩$ proportional to the projection of $A$ in the PCA subspace. Where the algorithmic lower-bound probability $1-1/\mathrm{poly}(m)$ and with error $\parallel |Y⟩-|\overline{Y}⟩\parallel$ $\le$ $\xi$ with the time complexity $\tilde{O}(1/\sqrt{p})$. If, instead, we estimate the value of $\parallel \overline{Y}{\parallel }_F$ to a realtive error of $\eta$ then the time complexity becomes $\tilde{O}\left(\frac{1}{\sqrt{p}\eta }\right)$

It is important to note what data is PCA-representable and qPCA-representable. First, we begin by defining PCA-representable data. Let a set of $n$ data points be defined $m$ coordinates and represented by the matrix $A$, which was given earlier as $\sum _i^r{\sigma }_i{u}_i{v}_i^T\in {\mathbb{R}}^{n\times m}$. Matrix or data $A$ is PCA-representable if there exists $p\in [\frac{1}{2},1]$, $\epsilon \in [0,1/2]$, $\beta \in [p-\epsilon ,p+\epsilon ]$, and $\alpha \in [0,1]$ such that:

• $\mathrm{\exists }k\in O(1)$ where the variance retained after dimensionality reduction $p=\frac{\sum _i^k{\sigma }_i^2}{\sum _i^m{\sigma }_i^2}$.
• For at least $\alpha n$ points $a_i$, it is maintained that $\frac{\Vert y_i\Vert }{\Vert a_i\Vert }\ge \beta$, where $\Vert y_i\Vert$ $=$ $\sqrt{\sum _i^k{\left|⟨a_i\mid v_j⟩\right|}^2}\Vert a_i\Vert$.

Note, this allows for algorithmic lower-bound probability of $1-1/\mathrm{poly}(m)$ we saw before.

Let's consider qPCA-representable case. Given $a_i$ is a row of $A\in {\mathbb{R}}^{n\times d}$, the time complexity is $\frac{\Vert a_i\Vert }{\Vert {\overline{y}}_i\Vert }$ $=$ $\frac{1}{\beta }$ $=$ $O(1)$ with the a probability greater than $\alpha$.

Now that we have defined the parameters, data assumptions, and goal for our qPCA algorithm, let's walk through the algorithm itself. The abstract concept is that the algorithm transforms the quantum state $|{\psi }_s⟩$ that holds the original data in quantum parallel to another quantum state $|{\psi }_e⟩$, that will store the new low-dimensional data points:

${\displaystyle |{\psi }_s⟩:=\frac{\sum _{i=1}^N|i⟩\otimes {\mathbf{x}}_i}{||X|{|}_F}}$ $\mapsto$ ${\displaystyle |{\psi }_e⟩:=\frac{\sum _{i=1}^N|i⟩\otimes {\mathbf{y}}_i}{\parallel Y{\parallel }_F}}$

such that, $\parallel X{\parallel }_F$ and $\parallel Y{\parallel }_F$ are the Frobenius norms of $X$ and $Y$. Let:

${\mathbf{x}}_i=\sum _{j=1}^D{x}_{ij}|j⟩=||{\mathbf{x}}_i|||{\mathbf{x}}_i⟩$

${\mathbf{y}}_i=\sum _{j=1}^d{y}_{ij}|j⟩=||{\mathbf{y}}_i|||{\mathbf{y}}_i⟩$

For the implementation of the quantum algorithm, first consider the data set $\{{\mathbf{x}}_i{\}}_{i=1}^N$, or matrix $X$, is stored in a quantum random access memory qRAM, such that qRAM takes $|i⟩|0⟩|0⟩\to |i⟩|a_i⟩||{\overrightarrow{a}}_i|⟩$. Next, using quantum access to the vectors and norms, we constuct the state $\sum _i\left|{\overrightarrow{a}}_i\right||e_i⟩|a_i⟩$, where the density matrix for the first register is exactly $X$. Now, we must create $n=O\left(t^2{ϵ}^{-1}\right)$ copies of $X$, in order to have an accuracy $ϵ$ in time $O(n\log d)$ by completing $e^{-iXt}$ implementations of this process.

An important aspect to keep in mind about this algorithm is that the density matrix exponentiation is most effective when some of the eigenvalues are large. This is because we are utilizing quantum parallelism to amplify deviations in the probability amplitudes in order to reveal eigenvectors corresponding to the large eigenvalues of the unknown state. If all eigenvalues are of size $O(1/d)$, then the time complexity increases to $t=(d)$ to generate a transformation such that it rotates the input state $\sigma$ to an orthogonal state.