Document Open Access Logo

Quantum-Inspired Algorithms for Solving Low-Rank Linear Equation Systems with Logarithmic Dependence on the Dimension

Authors Nai-Hui Chia, András Gilyén, Han-Hsuan Lin, Seth Lloyd, Ewin Tang, Chunhao Wang

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2020.47.pdf
  • Filesize: 0.54 MB
  • 17 pages

Document Identifiers

Author Details

Nai-Hui Chia
  • Department of Computer Science, University of Texas at Austin, TX, USA
  • Joint Center for Quantum Information and Computer Science, University of Maryland, College Park, MD, USA
András Gilyén
  • QuSoft, CWI and University of Amsterdam, The Netherlands
Han-Hsuan Lin
  • Department of Computer Science, University of Texas at Austin, TX, USA
  • Department of Computer Science, National Tsing Hua University, Hsinchu, Taiwan
Seth Lloyd
  • MIT, Departments of Mechanical Engineering and Physics, Cambridge, MA, USA
  • Xanadu, Toronto, Canada
Ewin Tang
  • University of Washington, Seattle, WA, USA
Chunhao Wang
  • Department of Computer Science, University of Texas at Austin, TX, USA
  • Department of Computer Science and Engineering, Pennsylvania State University, Philadelphia, PA, USA

Funding

NHC, HHL, and CW were supported by Scott Aaronson’s Vannevar Bush Faculty Fellowship. AG was supported by ERC Consolidator Grant QPROGRESS and partially supported by QuantERA project QuantAlgo 680-91-034. SL was supported by ARO and OSD under a Blue Sky Program.

Acknowledgements

NHC, HHL, and CW thank Scott Aaronson for the valuable feedback on a draft of this paper. AG thanks Márió Szegedy for introduction to the problem and sharing insights, Ravi Kannan for helpful discussions and Ronald de Wolf for useful comments on the manuscript. We thank the anonymous reviewers for their valuable feedback on both submissions.

Cite AsGet BibTex

Nai-Hui Chia, András Gilyén, Han-Hsuan Lin, Seth Lloyd, Ewin Tang, and Chunhao Wang. Quantum-Inspired Algorithms for Solving Low-Rank Linear Equation Systems with Logarithmic Dependence on the Dimension. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 47:1-47:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.ISAAC.2020.47

Abstract

We present two efficient classical analogues of the quantum matrix inversion algorithm [Harrow et al., 2009] for low-rank matrices. Inspired by recent work of Tang [Tang, 2019], assuming length-square sampling access to input data, we implement the pseudoinverse of a low-rank matrix allowing us to sample from the solution to the problem Ax = b using fast sampling techniques. We construct implicit descriptions of the pseudo-inverse by finding approximate singular value decomposition of A via subsampling, then inverting the singular values. In principle, our approaches can also be used to apply any desired "smooth" function to the singular values. Since many quantum algorithms can be expressed as a singular value transformation problem [András Gilyén et al., 2019], our results indicate that more low-rank quantum algorithms can be effectively "dequantised" into classical length-square sampling algorithms.

Subject Classification

ACM Subject Classification
  • Theory of computation → Sketching and sampling
Keywords
  • sublinear algorithms
  • quantum-inspired
  • regression
  • importance sampling
  • quantum machine learning

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 Symposium on Theoretical Aspects of Computer Science (STACS), pages 636-647, 2012. https://arxiv.org/abs/1010.4458. 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. Quantum, 4:307, 2020. https://arxiv.org/abs/1905.10415. URL: https://doi.org/10.22331/q-2020-08-13-307.
  3. Dominic W. Berry, Andrew M. Childs, Richard Cleve, Robin Kothari, and Rolando D. Somma. Exponential improvement in precision for simulating sparse Hamiltonians. In Proceedings of the 46th ACM Symposium on the Theory of Computing (STOC), pages 283-292, 2014. https://arxiv.org/abs/1312.1414. URL: https://doi.org/10.1145/2591796.2591854.
  4. Jacob Biamonte, Peter Wittek, Nicola Pancotti, Patrick Rebentrost, Nathan Wiebe, and Seth Lloyd. Quantum machine learning. Nature, 549:195-202, 2017. https://arxiv.org/abs/1611.09347. URL: https://doi.org/10.1038/nature23474.
  5. Shantanav Chakraborty, András Gilyén, and Stacey Jeffery. The power of block-encoded matrix powers: improved regression techniques via faster Hamiltonian simulation. In Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP), pages 33:1-33:14, 2019. https://arxiv.org/abs/1804.01973. URL: https://doi.org/10.4230/LIPIcs.ICALP.2019.33.
  6. Zhihuai Chen, Yinan Li, Xiaoming Sun, Pei Yuan, and Jialin Zhang. A quantum-inspired classical algorithm for separable non-negative matrix factorization. In Proceedings of the 28th International Joint Conference on Artificial Intelligence, pages 4511-4517. AAAI Press, 2019. URL: https://arxiv.org/abs/1907.05568.
  7. 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 ACM Symposium on the Theory of Computing (STOC), page 387–400, 2020. https://arxiv.org/abs/1910.06151. URL: https://doi.org/10.1145/3357713.3384314.
  8. Nai-Hui Chia, Tongyang Li, Han-Hsuan Lin, and Chunhao Wang. Quantum-inspired sublinear algorithm for solving low-rank semidefinite programming. In Proceedings of the 45th International Symposium on Mathematical Foundations of Computer Science (MFCS), pages 23:1-23:15, 2020. https://arxiv.org/abs/1901.03254. URL: https://doi.org/10.4230/LIPIcs.MFCS.2020.23.
  9. Nai-Hui Chia, Han-Hsuan Lin, and Chunhao Wang. Quantum-inspired sublinear classical algorithms for solving low-rank linear systems. https://arxiv.org/abs/1811.04852, 2018.
  10. Chen Ding, Tian-Yi Bao, and He-Liang Huang. Quantum-inspired support vector machine. https://arxiv.org/abs/1906.08902, 2019.
  11. Yuxuan Du, Min-Hsiu Hsieh, Tongliang Liu, and Dacheng Tao. Quantum-inspired algorithm for general minimum conical hull problems. Physical Review Research, 2(3):033199, 2020. https://arxiv.org/abs/1907.06814. URL: https://doi.org/10.1103/PhysRevResearch.2.033199.
  12. Yuliya B. Farforovskaya and Ludmila N. Nikolskaya. Modulus of continuity of operator functions. St. Petersburg Math. J. - Algebra i Analiz, 20(3):493-506, 2009. URL: https://doi.org/10.1090/S1061-0022-09-01058-9.
  13. 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. URL: https://doi.org/10.1145/1039488.1039494.
  14. András Gilyén, Seth Lloyd, and Ewin Tang. Quantum-inspired low-rank stochastic regression with logarithmic dependence on the dimension. https://arxiv.org/abs/1811.04909, 2018.
  15. 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 ACM Symposium on the Theory of Computing (STOC),, pages 193-204, 2019. https://arxiv.org/abs/1806.01838. URL: https://doi.org/10.1145/3313276.3316366.
  16. Aram W. Harrow, Avinatan Hassidim, and Seth Lloyd. Quantum algorithm for linear systems of equations. Physical Review Letters, 103(15):150502, 2009. https://arxiv.org/abs/0811.3171. URL: https://doi.org/10.1103/PhysRevLett.103.150502.
  17. Roger A. Horn and Charles R. Johnson. Matrix Analysis. Cambridge University Press, 1990. Google Scholar
  18. Dhawal Jethwani, François Le Gall, and Sanjay K. Singh. Quantum-inspired classical algorithms for singular value transformation. In Proceedings of the 45th International Symposium on Mathematical Foundations of Computer Science (MFCS), pages 53:1-53:14, 2020. https://arxiv.org/abs/1910.05699. URL: https://doi.org/10.4230/LIPIcs.MFCS.2020.53.
  19. Ravindran Kannan and Santosh Vempala. Randomized algorithms in numerical linear algebra. Acta Numerica, 26:95-135, 2017. URL: https://doi.org/10.1017/S0962492917000058.
  20. Iordanis Kerenidis and Anupam Prakash. Quantum recommendation systems. In Proceedings of the 8th Innovations in Theoretical Computer Science Conference (ITCS), pages 49:1-49:21, 2017. https://arxiv.org/abs/1603.08675. URL: https://doi.org/10.4230/LIPIcs.ITCS.2017.49.
  21. Iordanis Kerenidis and Anupam Prakash. Quantum gradient descent for linear systems and least squares. Physical Review A, 101(2):022316, 2020. https://arxiv.org/abs/1704.04992. URL: https://doi.org/10.1103/PhysRevA.101.022316.
  22. Seth Lloyd, Masoud Mohseni, and Patrick Rebentrost. Quantum principal component analysis. Nature Physics, 10:631-633, 2014. https://arxiv.org/abs/1307.0401. URL: https://doi.org/10.1038/nphys3029.
  23. Patrick Rebentrost and Seth Lloyd. Quantum computational finance: quantum algorithm for portfolio optimization. https://arxiv.org/abs/1811.03975, 2018.
  24. Patrick Rebentrost, Masoud Mohseni, and Seth Lloyd. Quantum support vector machine for big data classification. Physical Review Letters, 113(13):130503, 2014. https://arxiv.org/abs/1307.0471. URL: https://doi.org/10.1103/PhysRevLett.113.130503.
  25. Patrick Rebentrost, Adrian Steffens, Iman Marvian, and Seth Lloyd. Quantum singular-value decomposition of nonsparse low-rank matrices. Physical Review A, 97:012327, 2018. https://arxiv.org/abs/1607.05404. URL: https://doi.org/10.1103/PhysRevA.97.012327.
  26. Ewin Tang. Quantum-inspired classical algorithms for principal component analysis and supervised clustering. https://arxiv.org/abs/1811.00414, 2018.
  27. Ewin Tang. A quantum-inspired classical algorithm for recommendation systems. In Proceedings of the 51st ACM Symposium on the Theory of Computing (STOC), pages 217-228, 2019. https://arxiv.org/abs/1807.04271. URL: https://doi.org/10.1145/3313276.3316310.
  28. Nathan Wiebe, Daniel Braun, and Seth Lloyd. Quantum algorithm for data fitting. Physical Review Letters, 109(5):050505, 2012. https://arxiv.org/abs/1204.5242. URL: https://doi.org/10.1103/PhysRevLett.109.050505.
  29. Leonard Wossnig, Zhikuan Zhao, and Anupam Prakash. Quantum linear system algorithm for dense matrices. Physical Review Letters, 120(5):050502, 2018. https://arxiv.org/abs/1704.06174. URL: https://doi.org/10.1103/PhysRevLett.120.050502.
  30. Zhikuan Zhao, Jack K. Fitzsimons, and Joseph F. Fitzsimons. Quantum-assisted Gaussian process regression. Physical Review A, 99(5):052331, 2019. https://arxiv.org/abs/1512.03929. URL: https://doi.org/10.1103/PhysRevA.99.052331.
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