# Classical and Quantum Algorithms for Tensor Principal Component Analysis

arXiv: https://arxiv.org/abs/1907.12724 · HTML: https://mlsanity.com/paper/1907.12724/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Jul 2019.

## Built on by (most cited first, 5 of 5)

- [Towards Quantum Tensor Decomposition in Biomedical Applications](https://mlsanity.com/paper/2502.13140/) (2025)
- [Selective Multiple Power Iteration: from Tensor PCA to gradient-based exploration of landscapes](https://mlsanity.com/paper/2112.12306/) (2021)
- [Overcomplete Tensor Decomposition via Koszul-Young Flattenings](https://mlsanity.com/paper/2411.14344/) (2024)
- [Dimension reduction with structure-aware quantum circuits for hybrid machine learning](https://mlsanity.com/paper/2508.00048/) (2025)
- [Practical advantage beyond the quadratic speedup limit with fully-quantum walks](https://mlsanity.com/paper/2607.22818/) (2026)

## Abstract (arXiv)

We present classical and quantum algorithms based on spectral methods for a problem in tensor principal component analysis. The quantum algorithm achieves a quartic 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. 1. 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.