Classical and Quantum Algorithms for Tensor Principal Component Analysis

Matthew B. Hastings

doi:10.22331/q-2020-02-27-237

Classical and Quantum Algorithms for Tensor Principal Component Analysis

Matthew B. Hastings

Station Q, Microsoft Research, Santa Barbara, CA 93106-6105, USA
Microsoft Quantum and Microsoft Research, Redmond, WA 98052, USA

Published:	2020-02-27, volume 4, page 237
Eprint:	arXiv:1907.12724v2
Doi:	https://doi.org/10.22331/q-2020-02-27-237
Citation:	Quantum 4, 237 (2020).

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.

Abstract

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.

► BibTeX data

@article{Hastings2020classicalquantum,
  doi = {10.22331/q-2020-02-27-237},
  url = {https://doi.org/10.22331/q-2020-02-27-237},
  title = {Classical and {Q}uantum {A}lgorithms for {T}ensor {P}rincipal {C}omponent {A}nalysis},
  author = {Hastings, Matthew B.},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {4},
  pages = {237},
  month = feb,
  year = {2020}
}

► References

[1] Alexander S Wein, Ahmed El Alaoui, and Cristopher Moore. The kikuchi hierarchy and tensor pca. 2019. arXiv:1904.03858.
arXiv:1904.03858

[2] Andrea Montanari and Emile Richard. A statistical model for tensor pca. In Advances in Neural Information Processing Systems, pages 2897–2905, 2014.

[3] Thibault Lesieur, Leo Miolane, Marc Lelarge, Florent Krzakala, and Lenka Zdeborova. Statistical and computational phase transitions in spiked tensor estimation. In 2017 IEEE International Symposium on Information Theory (ISIT). IEEE, jun 2017. doi:10.1109/isit.2017.8006580.
https://doi.org/10.1109/isit.2017.8006580

[4] Samuel B Hopkins, Jonathan Shi, and David Steurer. Tensor principal component analysis via sum-of-square proofs. In Conference on Learning Theory, pages 956–1006, 2015.

[5] Samuel B. Hopkins, Tselil Schramm, Jonathan Shi, and David Steurer. Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing - STOC 2016. ACM Press, 2016. doi:10.1145/2897518.2897529.
https://doi.org/10.1145/2897518.2897529

[6] Vijay V. S. P. Bhattiprolu, Mrinalkanti Ghosh, Euiwoong Lee, Venkatesan Guruswami, and Madhur Tulsiani. Multiplicative approximations for polynomial optimization over the unit sphere. CoRR, abs/1611.05998, 2016. URL: http://arxiv.org/abs/1611.05998, arXiv:1611.05998.
arXiv:1611.05998

[7] Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami, Euiwoong Lee, and Madhur Tulsiani. Weak decoupling, polynomial folds and approximate optimization over the sphere. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS). IEEE, oct 2017. doi:10.1109/focs.2017.97.
https://doi.org/10.1109/focs.2017.97

[8] R.F. Werner. Large deviations and mean-field quantum systems. In Quantum Probability and Related Topics, pages 349–381. WORLD SCIENTIFIC, jul 1992. doi:10.1142/9789814354783_0024.
https://doi.org/10.1142/9789814354783_0024

[9] Christina V. Kraus, Maciej Lewenstein, and J. Ignacio Cirac. Ground states of fermionic lattice hamiltonians with permutation symmetry. Physical Review A, 88(2), aug 2013. doi:10.1103/physreva.88.022335.
https://doi.org/10.1103/physreva.88.022335

[10] Fernando G. S. L. Brandão and Aram W. Harrow. Product-state approximations to quantum states. Communications in Mathematical Physics, 342(1):47–80, jan 2016. doi:10.1007/s00220-016-2575-1.
https://doi.org/10.1007/s00220-016-2575-1

[11] Scott Aaronson and Lijie Chen. Complexity-theoretic foundations of quantum supremacy experiments. In 32nd Computational Complexity Conference (CCC 2017). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2017. arXiv:1612.05903.
arXiv:1612.05903

[12] Madan Lal Mehta. Random matrices, volume 142. Elsevier, 2004.

[13] James Demmel, Ioana Dumitriu, and Olga Holtz. Fast linear algebra is stable. Numerische Mathematik, 108(1):59–91, oct 2007. doi:10.1007/s00211-007-0114-x.
https://doi.org/10.1007/s00211-007-0114-x

[14] Guang Hao Low and Isaac L. Chuang. Optimal Hamiltonian simulation by quantum signal processing. Phys. Rev. Lett., 118:010501, 2017. arXiv:1606.02685v2, doi:10.1103/PhysRevLett.118.010501.
https://doi.org/10.1103/PhysRevLett.118.010501
arXiv:1606.02685v2

[15] Guang Hao Low and Isaac L Chuang. Hamiltonian simulation by qubitization. 2016. arXiv:1610.06546 https://doi.org/10.22331/q-2019-07-12-163.
https://doi.org/10.22331/q-2019-07-12-163
arXiv:1610.06546

[16] Dominic W. Berry, Andrew M. Childs, Richard Cleve, Robin Kothari, and Rolando D. Somma. Exponential improvement in precision for simulating sparse Hamiltonians. pages 283–292, 2014. arXiv:1312.1414, doi:10.1145/2591796.2591854.
https://doi.org/10.1145/2591796.2591854
arXiv:1312.1414

[17] Dominic W. Berry, Andrew M. Childs, Richard Cleve, Robin Kothari, and Rolando D. Somma. Simulating Hamiltonian dynamics with a truncated Taylor series. Phys. Rev. Lett., 114:090502, 2015. arXiv:1412.4687, doi:10.1103/PhysRevLett.114.090502.
https://doi.org/10.1103/PhysRevLett.114.090502
arXiv:1412.4687

[18] D. W. Berry, A. M. Childs, and R. Kothari. Hamiltonian simulation with nearly optimal dependence on all parameters. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pages 792–809, Oct 2015. arXiv:1501.01715, doi:10.1109/FOCS.2015.54.
https://doi.org/10.1109/FOCS.2015.54
arXiv:1501.01715

[19] Alexei Yu Kitaev, Alexander Shen, and Mikhail N Vyalyi. Classical and quantum computation, volume 47. American Mathematical Society Providence, 2002. doi:10.1090/gsm/047.
https://doi.org/10.1090/gsm/047

[20] Gilles Brassard, Peter Hoyer, Michele Mosca, and Alain Tapp. Quantum amplitude amplification and estimation. Contemporary Mathematics, 305:53–74, 2002. doi:10.1090/conm/305.
https://doi.org/10.1090/conm/305

[21] Anthony Carbery and James Wright. Distributional and ${L^q}$ norm inequalities for polynomials over convex bodies in ${R^n}$. Mathematical Research Letters, 8(3):233–248, 2001. doi:10.4310/mrl.2001.v8.n3.a1.
https://doi.org/10.4310/mrl.2001.v8.n3.a1

[22] Dave Wecker, Matthew B. Hastings, Nathan Wiebe, Bryan K. Clark, Chetan Nayak, and Matthias Troyer. Solving strongly correlated electron models on a quantum computer. Physical Review A, 92(6), dec 2015. doi:10.1103/physreva.92.062318.
https://doi.org/10.1103/physreva.92.062318

[23] Matthew B. Hastings. The asymptotics of quantum max-flow min-cut. Communications in Mathematical Physics, 351(1):387–418, nov 2016. doi:10.1007/s00220-016-2791-8.
https://doi.org/10.1007/s00220-016-2791-8

Cited by

[1] David Gamarnik, Aukosh Jagannath, and Alexander S. Wein, 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS) 131 (2020) ISBN:978-1-7281-9621-3.

[2] Mohamed Ouerfelli, Mohamed Tamaazousti, and Vincent Rivasseau, "Selective multiple power iteration: from tensor PCA to gradient-based exploration of landscapes", The European Physical Journal Special Topics (2023).

[3] Ryan Babbush, Jarrod R. McClean, Michael Newman, Craig Gidney, Sergio Boixo, and Hartmut Neven, "Focus beyond Quadratic Speedups for Error-Corrected Quantum Advantage", PRX Quantum 2 1, 010103 (2021).

[4] Vincent Lahoche, Mohamed Ouerfelli, Dine Ousmane Samary, and Mohamed Tamaazousti, "Field Theoretical Approach for Signal Detection in Nearly Continuous Positive Spectra II: Tensorial Data", Entropy 23 7, 795 (2021).

[5] Alexander M. Dalzell, Sam McArdle, Mario Berta, Przemyslaw Bienias, Chi-Fang Chen, András Gilyén, Connor T. Hann, Michael J. Kastoryano, Emil T. Khabiboulline, Aleksander Kubica, Grant Salton, Samson Wang, and Fernando G. S. L. Brandão, "Quantum algorithms: A survey of applications and end-to-end complexities", arXiv:2310.03011, (2023).

[6] Alexander S. Wein, Ahmed El Alaoui, and Cristopher Moore, "The Kikuchi Hierarchy and Tensor PCA", arXiv:1904.03858, (2019).

[7] Blake A. Wilson, Zhaxylyk A. Kudyshev, Alexander V. Kildishev, Sabre Kais, Vladimir M. Shalaev, and Alexandra Boltasseva, "Machine learning framework for quantum sampling of highly constrained, continuous optimization problems", Applied Physics Reviews 8 4, 041418 (2021).

The above citations are from Crossref's cited-by service (last updated successfully 2023-12-07 05:50:48) and SAO/NASA ADS (last updated successfully 2023-12-07 05:50:49). The list may be incomplete as not all publishers provide suitable and complete citation data.

This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.