Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Quantum-inspired classical algorithms for principal component analysis and supervised clustering.

Ewin Tang

Published Oct 31, 2018• 59 citations
OpenAlex

Abstract

We describe classical analogues to Lloyd et al.'s quantum algorithms for principal component analysis and nearest-centroid clustering. We introduce a classical algorithm model that assumes we can efficiently perform $\ell^2$-norm samples of input data, a natural analogue to quantum algorithms assuming efficient state preparation. In this model, our classical algorithms run in time polylogarithmic in input size, matching the runtime of the quantum algorithms with only polynomial slowdown. These algorithms indicate that their corresponding problems do not yield exponential quantum speedups.

Related papers

Quantum Principal Component Analysis Only Achieves an Exponential Speedup Because of Its State Preparation Assumptions

Ewin Tang

A central roadblock to analyzing quantum algorithms on quantum states is the lack of a comparable input model for classical algorithms. Inspired by recent work of the author [E. Tang, STOC 2019.], we introduce such a model, where we assume we can efficiently perform ℓ^{2}-norm samples of input data, a natural analog to quantum algorithms that assume efficient state preparation of classical data. Though this model produces less practical algorithms than the (stronger) standard model of classical computation, it captures versions of many of the features and nuances of quantum linear algebra algorithms. With this model, we describe classical analogs to Lloyd, Mohseni, and Rebentrost's quantum algorithms for principal component analysis [S. Lloyd, M. Mohseni, and P. Rebentrost, Nat. Phys. 10, 631 (2014).NPAHAX1745-247310.1038/nphys3029] and nearest-centroid clustering [S. Lloyd, M. Mohseni, and P. Rebentrost, Quantum algorithms for supervised and unsupervised machine learning]. Since they are only polynomially slower, these algorithms suggest that the exponential speedups of their quantum counterparts are simply an artifact of state preparation assumptions.

arXiv:1811.00414•Physical Review Letters•Aug 4, 2021•141 citations

Quantum-Inspired Classical Algorithm for Principal Component Regression

Daniel Chen, Yekun Xu, Betis Baheri +4 more

This paper presents a sublinear classical algorithm for principal component regression. The algorithm uses quantum-inspired linear algebra, an idea developed by Tang. Using this technique, her algorithm for recommendation systems achieved runtime only polynomially slower than its quantum counterpart. Her work was quickly adapted to solve many other problems in sublinear time complexity. In this work, we developed an algorithm for principal component regression that runs in time polylogarithmic to the number of data points, an exponential speed up over the state-of-the-art algorithm, under the mild assumption that the input is given in some data structure that supports a norm-based sampling procedure. This exponential speed up allows for potential applications in much larger data sets.

arXiv:2010.08626•Oct 16, 2020•3 citations

Quantum-inspired principal component analysis for exponentially large dimensional data

慶 間島, 小出（間島）真子, 憲明 八幡 +2 more

Principal component analysis (PCA) is a widely used statistical tool for extracting low-dimensional structures underlying multivariate data. However, its application to high-dimensional data is limited due to its large computational time. While the conventional PCA algorithm requires polynomial time, using a quantum-inspired algorithm as a subroutine, we have implemented an algorithm that approximates it with computational time proportional to the logarithm of the input dimensionality. The computational efficiency and performance of the implemented algorithm, quantum-inspired PCA, are experimentally evaluated on synthetic and real datasets.

•Sep 21, 2021•0 citations

Classical Equivalent Quantum Based Efficient Data Preprocessing Algorithm

Barkha Soni, Nilay Khare, Kapil Kumar Soni +1 more

The machine learning model can infer desired information on processing data sets without being explicitly programmed. It needs refined data to train the perfect model, hence preprocessing is mandatory. The principal component analysis is desired classical existing methods for preprocessing and it requires polynomial time. Now, the research field of computer science is getting influenced by existence of quantum computations, as it supports exponential operations to be performed in parallel over single step of execution. An intrinsic realization of quantum machine provides simultaneous access to either classical or quantum memory. The objective of paper is to understand the importance of data preprocessing and to suggest quantum based solution that takes the advantage of quantum parallelism and thus can obtain computational speedups. So, we contribute to the emergence of quantum computations, processing aspects using quantum accessible memory models and then classical equivalent quantum principal component analysis algorithm. At last we conclude with the mathematical justification over complexity analysis, computational speedups, and prove that quantum algorithms are efficient along with the suggestions of further directions.

International Conference on Computing, Communication and Networking Technologies (ICCCNT)•Jul 1, 2020•8 citations

A quantum-inspired classical algorithm for recommendation systems

Ewin Tang

We give a classical analogue to Kerenidis and Prakash’s quantum recommendation system, previously believed to be one of the strongest candidates for provably exponential speedups in quantum machine learning. Our main result is an algorithm that, given an m × n matrix in a data structure supporting certain ℓ2-norm sampling operations, outputs an ℓ2-norm sample from a rank-k approximation of that matrix in time O(poly(k)log(mn)), only polynomially slower than the quantum algorithm. As a consequence, Kerenidis and Prakash’s algorithm does not in fact give an exponential speedup over classical algorithms. Further, under strong input assumptions, the classical recommendation system resulting from our algorithm produces recommendations exponentially faster than previous classical systems, which run in time linear in m and n.

arXiv:1807.04271•ACM Symposium on Theory of Computing (STOC)•Jun 20, 2019•367 citations

Classical and Quantum Algorithms for Tensor Principal Component Analysis

Matthew B. Hastings

We present classical and quantum algorithms based on spectral methods for a problem in tensor principal component analysis. The quantum algorithm achieves a q u a r t i c speedup while using exponentially smaller space than the fastest classical spectral algorithm, and a super-polynomial speedup over classical algorithms that use only polynomial space. The classical algorithms that we present are related to, but slightly different from those presented recently in Ref. \cite{wein2019kikuchi}. In particular, we have an improved threshold for recovery and the algorithms we present work for both even and odd order tensors. These results suggest that large-scale inference problems are a promising future application for quantum computers.

arXiv:1907.12724•Quantum•Feb 27, 2020•16 citations
We describe classical analogues to Lloyd et al.'s quantum algorithms for principal component analysis and nearest-centroid clustering. We introduce a classical algorithm model that assumes we can efficiently perform ℓ2\ell^2ℓ2-norm samples of input data, a natural analogue to quantum algorithms assuming efficient state preparation. In this model, our classical algorithms run in time polylogarithmic in input size, matching the runtime of the quantum algorithms with only polynomial slowdown. These algorithms indicate that their corresponding problems do not yield exponential quantum speedups.
A central roadblock to analyzing quantum algorithms on quantum states is the lack of a comparable input model for classical algorithms. Inspired by recent work of the author [E. Tang, STOC 2019.], we introduce such a model, where we assume we can efficiently perform ℓ^{2}-norm samples of input data, a natural analog to quantum algorithms that assume efficient state preparation of classical data. Though this model produces less practical algorithms than the (stronger) standard model of classical computation, it captures versions of many of the features and nuances of quantum linear algebra algorithms. With this model, we describe classical analogs to Lloyd, Mohseni, and Rebentrost's quantum algorithms for principal component analysis [S. Lloyd, M. Mohseni, and P. Rebentrost, Nat. Phys. 10, 631 (2014).NPAHAX1745-247310.1038/nphys3029] and nearest-centroid clustering [S. Lloyd, M. Mohseni, and P. Rebentrost, Quantum algorithms for supervised and unsupervised machine learning]. Since they are only polynomially slower, these algorithms suggest that the exponential speedups of their quantum counterparts are simply an artifact of state preparation assumptions.
This paper presents a sublinear classical algorithm for principal component regression. The algorithm uses quantum-inspired linear algebra, an idea developed by Tang. Using this technique, her algorithm for recommendation systems achieved runtime only polynomially slower than its quantum counterpart. Her work was quickly adapted to solve many other problems in sublinear time complexity. In this work, we developed an algorithm for principal component regression that runs in time polylogarithmic to the number of data points, an exponential speed up over the state-of-the-art algorithm, under the mild assumption that the input is given in some data structure that supports a norm-based sampling procedure. This exponential speed up allows for potential applications in much larger data sets.
Principal component analysis (PCA) is a widely used statistical tool for extracting low-dimensional structures underlying multivariate data. However, its application to high-dimensional data is limited due to its large computational time. While the conventional PCA algorithm requires polynomial time, using a quantum-inspired algorithm as a subroutine, we have implemented an algorithm that approximates it with computational time proportional to the logarithm of the input dimensionality. The computational efficiency and performance of the implemented algorithm, quantum-inspired PCA, are experimentally evaluated on synthetic and real datasets.
The machine learning model can infer desired information on processing data sets without being explicitly programmed. It needs refined data to train the perfect model, hence preprocessing is mandatory. The principal component analysis is desired classical existing methods for preprocessing and it requires polynomial time. Now, the research field of computer science is getting influenced by existence of quantum computations, as it supports exponential operations to be performed in parallel over single step of execution. An intrinsic realization of quantum machine provides simultaneous access to either classical or quantum memory. The objective of paper is to understand the importance of data preprocessing and to suggest quantum based solution that takes the advantage of quantum parallelism and thus can obtain computational speedups. So, we contribute to the emergence of quantum computations, processing aspects using quantum accessible memory models and then classical equivalent quantum principal component analysis algorithm. At last we conclude with the mathematical justification over complexity analysis, computational speedups, and prove that quantum algorithms are efficient along with the suggestions of further directions.
We give a classical analogue to Kerenidis and Prakash’s quantum recommendation system, previously believed to be one of the strongest candidates for provably exponential speedups in quantum machine learning. Our main result is an algorithm that, given an m × n matrix in a data structure supporting certain ℓ2-norm sampling operations, outputs an ℓ2-norm sample from a rank-k approximation of that matrix in time O(poly(k)log(mn)), only polynomially slower than the quantum algorithm. As a consequence, Kerenidis and Prakash’s algorithm does not in fact give an exponential speedup over classical algorithms. Further, under strong input assumptions, the classical recommendation system resulting from our algorithm produces recommendations exponentially faster than previous classical systems, which run in time linear in m and n.
We present classical and quantum algorithms based on spectral methods for a problem in tensor principal component analysis. The quantum algorithm achieves a q u a r t i c speedup while using exponentially smaller space than the fastest classical spectral algorithm, and a super-polynomial speedup over classical algorithms that use only polynomial space. The classical algorithms that we present are related to, but slightly different from those presented recently in Ref. \cite{wein2019kikuchi}. In particular, we have an improved threshold for recovery and the algorithms we present work for both even and odd order tensors. These results suggest that large-scale inference problems are a promising future application for quantum computers.