Document Open Access Logo

Quantum-Inspired Classical Algorithms for Singular Value Transformation

Authors Dhawal Jethwani, François Le Gall, Sanjay K. Singh

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2020.53.pdf
  • Filesize: 0.52 MB
  • 14 pages

Document Identifiers

Author Details

Dhawal Jethwani
  • Indian Institute of Technology (BHU), Varanasi, India
François Le Gall
  • Nagoya University, Japan
Sanjay K. Singh
  • Indian Institute of Technology (BHU), Varanasi, India

Funding

  • Le Gall, François: FLG was partially supported by JSPS KAKENHI grants Nos. JP15H01677, JP16H01705, JP16H05853, JP19H04066 and by the MEXT Quantum Leap Flagship Program (MEXT Q-LEAP) grant No. JPMXS0118067394.

Acknowledgements

The authors are grateful to András Gilyén for discussions and comments about the manuscript. Part of this work has been done when DJ was visiting Kyoto University.

Cite AsGet BibTex

Dhawal Jethwani, François Le Gall, and Sanjay K. Singh. Quantum-Inspired Classical Algorithms for Singular Value Transformation. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 53:1-53:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.MFCS.2020.53

Abstract

A recent breakthrough by Tang (STOC 2019) showed how to "dequantize" the quantum algorithm for recommendation systems by Kerenidis and Prakash (ITCS 2017). The resulting algorithm, classical but "quantum-inspired", efficiently computes a low-rank approximation of the users' preference matrix. Subsequent works have shown how to construct efficient quantum-inspired algorithms for approximating the pseudo-inverse of a low-rank matrix as well, which can be used to (approximately) solve low-rank linear systems of equations. In the present paper, we pursue this line of research and develop quantum-inspired algorithms for a large class of matrix transformations that are defined via the singular value decomposition of the matrix. In particular, we obtain classical algorithms with complexity polynomially related (in most parameters) to the complexity of the best quantum algorithms for singular value transformation recently developed by Chakraborty, Gilyén and Jeffery (ICALP 2019) and Gilyén, Su, Low and Wiebe (STOC 2019).

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
Keywords
  • Sampling algorithms
  • quantum-inspired algorithms
  • linear algebra

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Andris Ambainis. Variable time amplitude amplification and quantum algorithms for linear algebra problems. In Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science, pages 636-647, 2012. URL: https://doi.org/10.4230/LIPIcs.STACS.2012.636.
  2. Juan Miguel Arrazola, Alain Delgado, Bhaskar Roy Bardhan, and Seth Lloyd. Quantum-inspired algorithms in practice. arXiv:1905.10415, 2019. Google Scholar
  3. Jacob Biamonte, Peter Wittek, Nicola Pancotti, Patrick Rebentrost, Nathan Wiebe, and Seth Lloyd. Quantum machine learning. Nature, 549:195–202, 2017. Google Scholar
  4. Shantanav Chakraborty, András Gilyén, and Stacey Jeffery. The power of block-encoded matrix powers: Improved regression techniques via faster Hamiltonian simulation. In Proceeding of the 46th International Colloquium on Automata, Languages, and Programming, pages 33:1-33:14, 2019. Google Scholar
  5. Nai-Hui Chia, András Gilyén, Tongyang Li, Han-Hsuan Lin, Ewin Tang, and Chunhao Wang. Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning. In Proceedings of the 52nd Annual ACM Symposium on Theory of Computing, to appear, 2020. arXiv:1910.06151. Google Scholar
  6. Nai-Hui Chia, Han-Hsuan Lin, and Chunhao Wang. Quantum-inspired sublinear classical algorithms for solving low-rank linear systems. arXiv:1811.04852, 2018. Google Scholar
  7. Andrew M. Childs, Robin Kothari, and Rolando D. Somma. Quantum algorithm for systems of linear equations with exponentially improved dependence on precision. SIAM Journal on Computing, 46(6):1920-1950, 2017. Google Scholar
  8. B. David Clader, Bryan C. Jacobs, and Chad R. Sprouse. Preconditioned quantum linear system algorithm. Physical Review Letters, 110:250504, 2013. Google Scholar
  9. Alan Frieze, Ravi Kannan, and Santosh Vempala. Fast Monte-Carlo algorithms for finding low-rank approximations. Journal of the ACM, 51(6):1025-1041, 2004. Google Scholar
  10. Michael I. Gil. Perturbations of functions of diagonalizable matrices. Electronic Journal of Linear Algebra, 27(1):645, 2014. Google Scholar
  11. András Gilyén, Seth Lloyd, and Ewin Tang. Quantum-inspired low-rank stochastic regression with logarithmic dependence on the dimension. arXiv:1811.04909, 2018. Google Scholar
  12. András Gilyén, Yuan Su, Guang Hao Low, and Nathan Wiebe. Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 193-204, 2019. Google Scholar
  13. Aram W. Harrow, Avinatan Hassidim, and Seth Lloyd. Quantum algorithm for solving linear systems of equations. Physical Review Letters, 15(103):150502, 2009. Google Scholar
  14. Iordanis Kerenidis and Anupam Prakash. Quantum recommendation systems. In Proceedings of the 8th Innovations in Theoretical Computer Science Conference, pages 49:1-49:21, 2017. Google Scholar
  15. Seth Lloyd, Masoud Mohseni, and Patrick Rebentrost. Quantum principal component analysis. Nature Physics, 10:631–633, 2014. Google Scholar
  16. Patrick Rebentrost, Masoud Mohseni, and Seth Lloyd. Quantum support vector machine for big data classification. Physical review letters, 113(13):130503, 2014. Google Scholar
  17. Ewin Tang. Quantum-inspired classical algorithms for principal component analysis and supervised clustering. arXiv:1811.00414, 2018. Google Scholar
  18. Ewin Tang. A quantum-inspired classical algorithm for recommendation systems. In Proceedings of the 51st Annual Symposium on Theory of Computing, pages 217-228, 2019. Google Scholar
  19. Hermann Weyl. Das asymptotische verteilungsgesetz der eigenwerte linearer partieller differentialgleichungen (mit einer anwendung auf die theorie der hohlraumstrahlung). Mathematische Annalen, 71(4):441-479, 1912. Google Scholar
  20. Leonard Wossnig, Zhikuan Zhao, and Anupam Prakash. Quantum linear system algorithm for dense matrices. Physical Review Letters, 120:050502, 2018. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact