5
$\begingroup$

I have been reading Seth Lloyd's paper on Quantum Principal Component Analysis and while there is a short discussion that points to possible applications, I am having a hard time seeing the advantage of this subroutine in a specific context. In particular, I'd like to see a short illustrative example of how the algorithm works and why it is better than a classical algorithm. I'd be appreciative of any references or explanations in this regard.

$\endgroup$

1 Answer 1

3
$\begingroup$

A quantum PCA speedup for quantum data

Theorem 2 in (Huang, 2022) provides such an example of how this algorithm can be better than a classical algorithm:

Theorem 2 (Performing quantum PCA). In the conventional scenario, at least order $2^{𝑛/2}$ experiments are needed to learn a fixed property of the principal component of an unknown $n$-qubit quantum state, while a constant number of experiments suffice in the quantum-enhanced scenario.

More specifically, the "fixed property" to predict is $\langle \lambda_1| O |\lambda_1\rangle$ for some observable $O$, where $|\lambda_1 \rangle $ is the largest-eigenvalue eigenvector of a fixed, $n$-qubit state $\rho$. A key detail is that $\rho$ here does not represent classical data, but is treated as purely "quantum data" that one could imagine was sampled directly from a physical system.

No quantum PCA speedup for classical data so far

Claims of advantage for using quantum PCA to process classical data have been less solid. You won't find a compelling example of why quantum PCA is better than classical algorithms in this setting because there isn't any so far.

An example of this setting is if $\rho$ represents the covariance matrix for a dataset of high-dimensional classical vectors, then efficiently projecting elements of this dataset onto the eigenvectors of $\rho$ is useful for all sorts of machine learning tasks (as Lloyd discusses). Of course, processing classical data in this way requires a technique to efficiently prepare classical data as quantum states, e.g. QRAM.

The main thrust of (Tang, 2019) was that if you assume such a technique exists, then its only fair to provide a technique with similar power$^1$ to whatever classical machine learning algorithm is competing with quantum PCA. She carried this analysis out to show how a proposed exponential speedup from (Kerenidis, 2016)$^2$ vanishes in this setting with fairer data access assumptions. I'm not aware of any other proposals for super-polynomial speedup in processing classical data using quantum PCA, perhaps related to the widespread publicity in the community of Tang "dequantizing" the algorithm.


$^1$ The classical algorithm is given the ability to sample elements from vectors in the dataset according to the elements' magnitude.

$^2$ To be precise, Kerenidis and Prakash did not actually use quantum PCA in this work, but using the same data access model Prakash had shown in another work that a result using quantum PCA with similar scaling holds.

$\endgroup$
2
  • $\begingroup$ As an aside, could you inform me of any applications of qPCA to such purely quantum data? It seems to me that something like quantum state discrimination which is mentioned in the original paper fits the bill, but Iḿ not quite sure. $\endgroup$ Jul 6, 2023 at 15:38
  • $\begingroup$ That is the topic of the first link I provided and explained above, or maybe I am misunderstanding what you're asking? $\endgroup$
    – forky40
    Jul 7, 2023 at 1:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.