Gilyén, András Pál and Song, Z. and Tang, E. (2022) An improved quantum-inspired algorithm for linear regression. QUANTUM, 6. ISSN 2521-327X
|
Text
2009_07268v4.pdf Download (768kB) | Preview |
Abstract
We give a classical algorithm for linear regression analogous to the quantum matrix inversion algorithm [Harrow, Hassidim, and Lloyd, Physical Review Letters'09] for low-rank matrices [Wossnig, Zhao, and Prakash, Physical Review Letters'18], when the input matrix A is stored in a data structure applicable for QRAM-based state preparation. Namely, suppose we are given an A ∈ ℂm×n with minimum non-zero singular value σ which supports certain efficient ℓ2-norm importance sampling queries, along with a b ∈ ℂm. Then, for some x ∈ ℂn satisfying ||x - A+b|| ≤ ε||A+b||, we can output a measurement of |x〉 in the computational basis and output an entry of x with classical algorithms that run in (equation presented) and (equation presented) time, respectively. This improves on previous “quantum-inspired” algorithms in this line of research by at least a factor of (equation presented) [Chia, Gilyén, Li, Lin, Tang, and Wang, STOC'20]. As a consequence, we show that quantum computers can achieve at most a factor-of-12 speedup for linear regression in this QRAM data structure setting and related settings. Our work applies techniques from sketching algorithms and optimization to the quantum-inspired literature. Unlike earlier works, this is a promising avenue that could lead to feasible implementations of classical regression in a quantum-inspired settings, for comparison against future quantum computers. Copyright © 2022 The Korean Association of Oral and Maxillofacial Surgeons
| Item Type: | Article |
|---|---|
| Additional Information: | Alfréd Rényi Institute of Mathematics, Hungary Adobe Research University of Washington, United States The Institute for Quantum Information and Matter, California Institute of Technology, United States Cited By :2 Export Date: 23 January 2023 Funding details: National Science Foundation, NSF, DGE-1762114, PHY-1733907 Funding details: Simons Foundation, SF Funding details: European Research Council, ERC, 680-91-034 Funding text 1: A.G. acknowledges funding provided by Samsung Electronics Co., Ltd., for the project “The Computational Power of Sampling on Quantum Computers”, and additional support by the Institute for Quantum Information and Matter, an NSF Physics Frontiers Center (NSF Grant PHY-1733907), as well as support by ERC Consolidator Grant QPROGRESS, by QuantERA project QuantAlgo 680-91-034 and also by the EU’s Horizon 2020 Marie Skłodowska-Curie program 891889-QuantOrder. Z.S. was partially supported by Schmidt Foundation and Simons Foundation. E.T. is supported by the National Science Foundation Graduate Research Fellowship Program under Grant No. DGE-1762114. Funding text 2: E.T. thanks Kevin Tian immensely for discussions integral to these results. Z.S. thanks Runzhou Tao and Ruizhe Zhang for giving helpful comments on the draft. A.G. acknowledges funding provided by Samsung Electronics Co., Ltd., for the project “The Computational Power of Sampling on Quantum Computers”, and additional support by the Institute for Quantum Information and Matter, an NSF Physics Frontiers Center (NSF Grant PHY-1733907), as well as support by ERC Consolidator Grant QPROGRESS, by QuantERA project QuantAlgo 680-91-034 and also by the EU's Horizon 2020 Marie Skłodowska-Curie program 891889-QuantOrder. Z.S. was partially supported by Schmidt Foundation and Simons Foundation. E.T. is supported by the National Science Foundation Graduate Research Fellowship Program under Grant No. DGE-1762114. |
| Subjects: | Q Science / természettudomány > QA Mathematics / matematika |
| SWORD Depositor: | MTMT SWORD |
| Depositing User: | MTMT SWORD |
| Date Deposited: | 16 Mar 2023 07:42 |
| Last Modified: | 06 Apr 2023 14:32 |
| URI: | http://real.mtak.hu/id/eprint/162172 |
Actions (login required)
 |
Edit Item |
