Covariance Matrix Preparation for Quantum Principal Component Analysis

Principal component analysis (PCA) is a dimensionality reduction method in data analysis that involves diagonalizing the covariance matrix of the dataset. Recently, quantum algorithms have been formulated for PCA based on diagonalizing a density matrix. These algorithms assume that the covariance matrix can be encoded in a density matrix, but a concrete protocol for this encoding has been lacking. Our work aims to address this gap. Assuming amplitude encoding of the data, with the data given by the ensemble $\{p_i,|{\psi }_i⟩\}$, then one can easily prepare the ensemble average density matrix $\overline{\rho }=\sum _i{p}_i|{\psi }_i⟩⟨{\psi }_i|$. We first show that $\overline{\rho }$ is precisely the covariance matrix whenever the dataset is centered. For quantum datasets, we exploit global phase symmetry to argue that there always exists a centered dataset consistent with $\overline{\rho }$, and hence $\overline{\rho }$ can always be interpreted as a covariance matrix. This provides a simple means for preparing the covariance matrix for arbitrary quantum datasets or centered classical datasets. For uncentered classical datasets, our method is so-called “PCA without centering,” which we interpret as PCA on a symmetrized dataset. We argue that this closely corresponds to standard PCA, and we derive equations and inequalities that bound the deviation of the spectrum obtained with our method from that of standard PCA. We numerically illustrate our method for the Modified National Institute of Standards and Technology (MNIST) handwritten digit dataset. We also argue that PCA on quantum datasets is natural and meaningful, and we numerically implement our method for molecular ground-state datasets.

Popular Summary

Principal component analysis (PCA) is an essential part of machine learning and data analysis. It is used to reduce the dimensionality in a dataset while minimizing information loss. Implementing PCA on a quantum device is of great interest to the quantum computing community. However, an essential step in quantum PCA was missing: how to prepare the covariance matrix on a quantum computer.

Our main result proves that the ensemble average density matrix, which is extremely easy to prepare on a quantum computer, happens to correspond to the covariance matrix for quantum datasets. This is a timely result, since it was recently shown that quantum computers could provide an exponential speedup for PCA on quantum datasets. Therefore, our work provides the missing link in the quest for demonstrating exponential quantum speedup with PCA, opening the door for near-term implementations on quantum hardware.

In addition, we provide several conceptual insights. (1) We show that PCA on molecular ground states can lead to dramatic data compression. (2) We show that our method is PCA without centering for classical datasets, and we illustrate this for the famous MNIST handwritten digit dataset. (3) We offer a new interpretation of PCA without centering as being PCA on a symmetrized dataset. (4) We rigorously prove that PCA without centering yields a spectrum very similar to standard PCA.

Figure 1

Preparation of the ensemble average density matrix $\overline{\rho }$. For illustration, we show the well-known bars-and-stripes dataset. To prepare $\overline{\rho }$, images from this dataset are randomly selected according to a probability distribution $\{p_i\}$ and then amplitude encoded on a quantum device. The latter involves encoding each pixel’s color into the amplitudes of a quantum state $|{\psi }_i⟩$, expanded in the standard basis. Once the data are physically represented on a quantum device, the global phase information is lost and they can be represented as density matrices, of the form $|{\psi }_i⟩⟨{\psi }_i|$. The average state, averaged over many samplings from $\{p_i\}$, is what we call the ensemble average density matrix $\overline{\rho }=\sum _{i=1}^N{p}_i|{\psi }_i⟩⟨{\psi }_i|$. Preparing $\overline{\rho }$ simply adds a linear overhead (linear in the number of datapoints $N$) to the complexity of state preparation for each datapoint. See Sec. 5 for a detailed analysis of the complexity of our method when used as a subroutine of quantum PCA algorithms.

Figure 2

Covariance for complex random variables. For two complex random variables $X$ and $Y$, one can sample from their joint probability distribution $P(X,Y)$, and here we show three different samplings (with the purple, pink, and green colors). Each sampling leads to a pair of vectors in the complex plane (solid vector represents $X$, dashed vector represents $Y$). In the case of negative covariance, the vectors $X$ and $Y$ are ${180}^{\circ }$ out of phase. For positive covariance, the vectors are in phase. Imaginary covariance corresponds to vectors that are ${90}^{\circ }$ out of phase. In general, complex covariance arises from variables that are partially out of phase. In all cases, the direction of the covariance vector is indicated with a black arrow.

Figure 3

Comparison of standard PCA and “PCA without centering.” (a) Standard PCA involves diagonalizing $Q$, with the interpretation of fitting an ellipsoid to the data. (b) So-called “PCA without centering” can be interpreted as PCA on a symmetrized version of the dataset, e.g., where the dataset is duplicated with the duplicate copy having a minus sign applied. “PCA without centering” then corresponds to fitting an ellipsoid to the symmetrized dataset. [See Eq. (51) in the text below for an example of a symmetrized dataset.]

Figure 4

Impact of global phase on classical data. Unlike quantum states, classical datapoints are impacted by applying a global phase. Here we give a visual demonstration of this, where multiplying by a minus sign inverts the color of a handwritten digit from white to black.

Figure 5

Eigenvectors for the MNIST dataset of handwritten digits. We perform standard PCA (diagonalizing $Q$) and quantum PCA (diagonalizing $\overline{\rho }$). (a) The images of the first five principal components for PCA and the first six for quantum PCA are shown. The first principal component for quantum PCA is close to (has a large overlap with) the mean vector $|v_{\mathit{\mu }}⟩$, which is also shown. Also, one can visually see that $|Q_{d-j}⟩$ is quite similar to $|R_{d-j-1}⟩$ for these eigenvectors. (b) We plot the magnitude of the overlap of the principal components calculated from PCA and quantum PCA, namely, $|Q_{d-j}⟩$ and $|R_{d-j-1}⟩$. This overlap remains large when $j$ is less than 25. (c) Finally, we show the eigenvector error, which quantifies how far the eigenvectors of $\overline{\rho }$ are from being eigenvectors of $Q$.

Figure 6

Eigenvalues for the MNIST dataset of handwritten digits. We perform standard PCA (diagonalizing $Q$) and quantum PCA (diagonalizing $\overline{\rho }$). The eigenvalues calculated using PCA and quantum PCA are plotted. Note that $q_{d-j}$ is quite similar to $r_{d-j-1}$ for these principal components. In the inset we plot the difference between the shifted eigenvalues $q_{d-j}$ and $r_{d-j-1}$ calculated using PCA and quantum PCA, respectively.

Figure 7

Projection onto $n$ principal components for PCA and quantum PCA of the MNIST dataset. (a) The plot shows the median (solid) and upper 90% interval (dotted) infidelity ($I$) values between the projected state constructed using $n$ principal components calculated from PCA and quantum PCA. The median and upper interval are calculated over all $50000$ digits. (b) We show how the images are reproduced when using $n=1$ to $n=80$ principal components from PCA and quantum PCA in the upper and lower rows, respectively.

Figure 8

Quantum PCA performed on ground states of molecules at different interatomic distances. (a) The plot shows the infidelity ($I$) between the original state and the projected state constructed using $n$ principal components calculated by simulating quantum PCA. The median (solid line) and upper 90% interval (dotted line) are calculated over all $401$ interatomic distances $r$. (b) The infidelity is plotted as a function of interatomic distance $r$ for projected states calculated with $n=1,2,3,4$ principal components.