{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,16]],"date-time":"2026-06-16T04:08:44Z","timestamp":1781582924745,"version":"3.54.5"},"reference-count":23,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2020,2,27]],"date-time":"2020-02-27T00:00:00Z","timestamp":1582761600000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Quantum"],"abstract":"<jats:p>We present classical and quantum algorithms based on spectral methods for a problem in tensor principal component analysis. The quantum algorithm achieves a <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>q<\/mml:mi><mml:mi>u<\/mml:mi><mml:mi>a<\/mml:mi><mml:mi>r<\/mml:mi><mml:mi>t<\/mml:mi><mml:mi>i<\/mml:mi><mml:mi>c<\/mml:mi><\/mml:math> 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.<\/jats:p>","DOI":"10.22331\/q-2020-02-27-237","type":"journal-article","created":{"date-parts":[[2020,2,27]],"date-time":"2020-02-27T14:00:11Z","timestamp":1582812011000},"page":"237","source":"Crossref","is-referenced-by-count":11,"title":["Classical and Quantum Algorithms for Tensor Principal Component Analysis"],"prefix":"10.22331","volume":"4","author":[{"given":"Matthew B.","family":"Hastings","sequence":"first","affiliation":[{"name":"Station Q, Microsoft Research, Santa Barbara, CA 93106-6105, USA"},{"name":"Microsoft Quantum and Microsoft Research, Redmond, WA 98052, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"9598","published-online":{"date-parts":[[2020,2,27]]},"reference":[{"key":"0","unstructured":"Alexander S Wein, Ahmed El Alaoui, and Cristopher Moore. The kikuchi hierarchy and tensor pca. 2019. arXiv:1904.03858."},{"key":"1","unstructured":"Andrea Montanari and Emile Richard. A statistical model for tensor pca. In Advances in Neural Information Processing Systems, pages 2897\u20132905, 2014."},{"key":"2","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1109\/isit.2017.8006580"},{"key":"3","unstructured":"Samuel B Hopkins, Jonathan Shi, and David Steurer. Tensor principal component analysis via sum-of-square proofs. In Conference on Learning Theory, pages 956\u20131006, 2015."},{"key":"4","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1145\/2897518.2897529"},{"key":"5","unstructured":"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."},{"key":"6","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1109\/focs.2017.97"},{"key":"7","doi-asserted-by":"publisher","unstructured":"R.F. Werner. Large deviations and mean-field quantum systems. In Quantum Probability and Related Topics, pages 349\u2013381. WORLD SCIENTIFIC, jul 1992. doi:10.1142\/9789814354783_0024.","DOI":"10.1142\/9789814354783_0024"},{"key":"8","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1103\/physreva.88.022335"},{"key":"9","doi-asserted-by":"publisher","unstructured":"Fernando G. S. L. Brand\u00e3o and Aram W. Harrow. Product-state approximations to quantum states. Communications in Mathematical Physics, 342(1):47\u201380, jan 2016. doi:10.1007\/s00220-016-2575-1.","DOI":"10.1007\/s00220-016-2575-1"},{"key":"10","unstructured":"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."},{"key":"11","unstructured":"Madan Lal Mehta. Random matrices, volume 142. Elsevier, 2004."},{"key":"12","doi-asserted-by":"publisher","unstructured":"James Demmel, Ioana Dumitriu, and Olga Holtz. Fast linear algebra is stable. Numerische Mathematik, 108(1):59\u201391, oct 2007. doi:10.1007\/s00211-007-0114-x.","DOI":"10.1007\/s00211-007-0114-x"},{"key":"13","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1103\/PhysRevLett.118.010501"},{"key":"14","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.22331\/q-2019-07-12-163"},{"key":"15","doi-asserted-by":"publisher","unstructured":"Dominic W. Berry, Andrew M. Childs, Richard Cleve, Robin Kothari, and Rolando D. Somma. Exponential improvement in precision for simulating sparse Hamiltonians. pages 283\u2013292, 2014. arXiv:1312.1414, doi:10.1145\/2591796.2591854.","DOI":"10.1145\/2591796.2591854"},{"key":"16","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1103\/PhysRevLett.114.090502"},{"key":"17","doi-asserted-by":"publisher","unstructured":"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\u2013809, Oct 2015. arXiv:1501.01715, doi:10.1109\/FOCS.2015.54.","DOI":"10.1109\/FOCS.2015.54"},{"key":"18","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1090\/gsm\/047"},{"key":"19","doi-asserted-by":"publisher","unstructured":"Gilles Brassard, Peter Hoyer, Michele Mosca, and Alain Tapp. Quantum amplitude amplification and estimation. Contemporary Mathematics, 305:53\u201374, 2002. doi:10.1090\/conm\/305.","DOI":"10.1090\/conm\/305"},{"key":"20","doi-asserted-by":"publisher","unstructured":"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\u2013248, 2001. doi:10.4310\/mrl.2001.v8.n3.a1.","DOI":"10.4310\/mrl.2001.v8.n3.a1"},{"key":"21","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1103\/physreva.92.062318"},{"key":"22","doi-asserted-by":"publisher","unstructured":"Matthew B. Hastings. The asymptotics of quantum max-flow min-cut. Communications in Mathematical Physics, 351(1):387\u2013418, nov 2016. doi:10.1007\/s00220-016-2791-8.","DOI":"10.1007\/s00220-016-2791-8"}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2020-02-27-237\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2020,2,27]],"date-time":"2020-02-27T14:00:15Z","timestamp":1582812015000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2020-02-27-237\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,2,27]]},"references-count":23,"URL":"https:\/\/doi.org\/10.22331\/q-2020-02-27-237","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"value":"2521-327X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,2,27]]},"article-number":"237"}}