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

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


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

► References

[1] Alexander S Wein, Ahmed El Alaoui, and Cristopher Moore. The kikuchi hierarchy and tensor pca. 2019. 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.

[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.

[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:/​/​​abs/​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.

[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.

[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.

[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.

[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.

[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.

[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.

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

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

Cited by

[1] 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).

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

The above citations are from Crossref's cited-by service (last updated successfully 2021-06-16 09:44:25) and SAO/NASA ADS (last updated successfully 2021-06-16 09:44:26). The list may be incomplete as not all publishers provide suitable and complete citation data.