{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,19]],"date-time":"2026-06-19T02:44:59Z","timestamp":1781837099827,"version":"3.54.5"},"reference-count":48,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2022,7,7]],"date-time":"2022-07-07T00:00:00Z","timestamp":1657152000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"QuantERA ERA-NET Cofund in Quantum Technologies implemented within the European Union\u2019s Horizon 2020 Programme"},{"DOI":"10.13039\/501100000266","name":"EPSRC","doi-asserted-by":"crossref","award":["EP\/L021005\/1 and EP\/R043957\/1"],"award-info":[{"award-number":["EP\/L021005\/1 and EP\/R043957\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"crossref"}]},{"name":"European Research Council"},{"name":"European Union\u2019s Horizon 2020","award":["817581"],"award-info":[{"award-number":["817581"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Transactions on Quantum Computing"],"published-print":{"date-parts":[[2022,12,31]]},"abstract":"\n We establish an improved classical algorithm for solving linear systems in a model analogous to the QRAM that is used by quantum linear solvers. Precisely, for the linear system\n \n \\( A{\\bf x}= {\\bf b} \\)<\/jats:tex-math>\n <\/jats:inline-formula>\n , we show that there is a classical algorithm that outputs a data structure for\n \n \\( {\\bf x} \\)<\/jats:tex-math>\n <\/jats:inline-formula>\n allowing sampling and querying to the entries, where\n \n \\( {\\bf x} \\)<\/jats:tex-math>\n <\/jats:inline-formula>\n is such that\n \n \\( \\Vert {\\bf x}- A^{+}{\\bf b}\\Vert \\le \\epsilon \\Vert A^{+}{\\bf b}\\Vert \\)<\/jats:tex-math>\n <\/jats:inline-formula>\n . This output can be viewed as a classical analogue to the output of quantum linear solvers. The complexity of our algorithm is\n \n \\( \\widetilde{O}(\\kappa _F^6 \\kappa ^2\/\\epsilon ^2) \\)<\/jats:tex-math>\n <\/jats:inline-formula>\n , where\n \n \\( \\kappa _F = \\Vert A\\Vert _F\\Vert A^{+}\\Vert \\)<\/jats:tex-math>\n <\/jats:inline-formula>\n and\n \n \\( \\kappa = \\Vert A\\Vert \\Vert A^{+}\\Vert \\)<\/jats:tex-math>\n <\/jats:inline-formula>\n . This improves the previous best algorithm [Gily\u00e9n, Song and Tang, arXiv:2009.07268] of complexity\n \n \\( \\widetilde{O}(\\kappa _F^6 \\kappa ^6\/\\epsilon ^4) \\)<\/jats:tex-math>\n <\/jats:inline-formula>\n . Our algorithm is based on the randomized Kaczmarz method, which is a particular case of stochastic gradient descent. We also find that when\n A<\/jats:italic>\n is row sparse, this method already returns an approximate solution\n \n \\( {\\bf x} \\)<\/jats:tex-math>\n <\/jats:inline-formula>\n in time\n \n \\( \\widetilde{O}(\\kappa _F^2) \\)<\/jats:tex-math>\n <\/jats:inline-formula>\n , while the best quantum algorithm known returns\n \n \\( | {\\bf x} \\rangle \\)<\/jats:tex-math>\n <\/jats:inline-formula>\n in time\n \n \\( \\widetilde{O}(\\kappa _F) \\)<\/jats:tex-math>\n <\/jats:inline-formula>\n when\n A<\/jats:italic>\n is stored in the QRAM data structure. As a result, assuming access to QRAM and if\n A<\/jats:italic>\n is row sparse, the speedup based on current quantum algorithms is quadratic.\n <\/jats:p>","DOI":"10.1145\/3520141","type":"journal-article","created":{"date-parts":[[2022,3,25]],"date-time":"2022-03-25T13:06:52Z","timestamp":1648213612000},"page":"1-23","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":13,"title":["Faster Quantum-inspired Algorithms for Solving Linear Systems"],"prefix":"10.1145","volume":"3","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3008-7296","authenticated-orcid":false,"given":"Changpeng","family":"Shao","sequence":"first","affiliation":[{"name":"School of Mathematics, University of Bristol, Bristol, UK"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ashley","family":"Montanaro","sequence":"additional","affiliation":[{"name":"School of Mathematics, Bristol, UK, University of Bristol and Phasecraft Ltd., Bristol, UK"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2022,7,7]]},"reference":[{"key":"e_1_3_6_2_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITCS.2019.3"},{"key":"e_1_3_6_3_2","doi-asserted-by":"publisher","DOI":"10.22331\/q-2020-08-13-307"},{"key":"e_1_3_6_4_2","doi-asserted-by":"publisher","DOI":"10.1038\/nature23474"},{"key":"e_1_3_6_5_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10851-014-0539-7"},{"key":"e_1_3_6_6_2","unstructured":"Andrzej Cegielski. 2021. Bibliography on the Kaczmarz method. Retrieved from http:\/\/staff.uz.zgora.pl\/acegiels\/Publications-Kaczmarz-method.pdf."},{"key":"e_1_3_6_7_2","doi-asserted-by":"publisher","DOI":"10.1016\/0024-3795(82)90149-5"},{"key":"e_1_3_6_8_2","volume-title":"Parallel Optimization: Theory, Algorithms, and Applications","author":"Censor Yair","year":"1997","unstructured":"Yair Censor, Stavros Andrea Zenios, et\u00a0al. 1997. Parallel Optimization: Theory, Algorithms, and Applications. Oxford University Press on Demand."},{"key":"e_1_3_6_9_2","first-page":"33:1\u201333:14","volume-title":"46th International Colloquium on Automata, Languages, and Programming (ICALP\u201919)","author":"Chakraborty Shantanav","year":"2019","unstructured":"Shantanav Chakraborty, Andr\u00e1s Gily\u00e9n, and Stacey Jeffery. 2019. The power of block-encoded matrix powers: Improved regression techniques via faster Hamiltonian simulation. In 46th International Colloquium on Automata, Languages, and Programming (ICALP\u201919). 33:1\u201333:14. arXiv:1804.01973."},{"key":"e_1_3_6_10_2","article-title":"Quantum-inspired algorithms from randomized numerical linear algebra","author":"Chepurko Nadiia","year":"2020","unstructured":"Nadiia Chepurko, Kenneth L. Clarkson, Lior Horesh, and David P. Woodruff. 2020. Quantum-inspired algorithms from randomized numerical linear algebra. arXiv preprint arXiv:2011.04125 (2020).","journal-title":"arXiv preprint arXiv:2011.04125"},{"key":"e_1_3_6_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384314"},{"key":"e_1_3_6_12_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ISAAC.2020.47"},{"key":"e_1_3_6_13_2","first-page":"23:1\u201323:15","volume-title":"45th International Symposium on Mathematical Foundations of Computer Science (MFCS\u201920)","author":"Chia Nai-Hui","year":"2020","unstructured":"Nai-Hui Chia, Tongyang Li, Han-Hsuan Lin, and Chunhao Wang. 2020. Quantum-inspired classical algorithms for singular value transformation. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS\u201920). Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik, 23:1\u201323:15. arXiv:1901.03254."},{"key":"e_1_3_6_14_2","doi-asserted-by":"publisher","DOI":"10.1137\/16M1087072"},{"key":"e_1_3_6_15_2","doi-asserted-by":"publisher","DOI":"10.1137\/16M1073807"},{"key":"e_1_3_6_16_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704442696"},{"key":"e_1_3_6_17_2","unstructured":"Andr\u00e1s Gily\u00e9n Zhao Song and Ewin Tang. 2020. An improved quantum-inspired algorithm for linear regression. arXiv:2009.07268."},{"key":"e_1_3_6_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316366"},{"key":"e_1_3_6_19_2","doi-asserted-by":"publisher","DOI":"10.56021\/9781421407944"},{"key":"e_1_3_6_20_2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-5193(70)90109-8"},{"key":"e_1_3_6_21_2","doi-asserted-by":"publisher","DOI":"10.1137\/15M1025487"},{"key":"e_1_3_6_22_2","first-page":"5274","volume-title":"32nd International Conference on Neural Information Processing Systems","author":"Gupta Neha","year":"2018","unstructured":"Neha Gupta and Aaron Sidford. 2018. Exploiting numerical sparsity for efficient learning: Faster eigenvector computation and regression. In 32nd International Conference on Neural Information Processing Systems. 5274\u20135283."},{"key":"e_1_3_6_23_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.103.150502"},{"key":"e_1_3_6_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/359340.359351"},{"key":"e_1_3_6_25_2","first-page":"53:1\u201353:14","volume-title":"45th International Symposium on Mathematical Foundations of Computer Science (MFCS\u201920)","author":"Jethwani Dhawal","year":"2020","unstructured":"Dhawal Jethwani, Franccois Le Gall, and Sanjay K. Singh. 2020. Quantum-inspired classical algorithms for singular value transformation. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS\u201920). Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik, 53:1\u201353:14. arXiv:1910.05699."},{"key":"e_1_3_6_26_2","first-page":"355","article-title":"Angenaherte auflosung von systemen linearer glei-chungen","author":"Karczmarz S.","year":"1937","unstructured":"S. Karczmarz. 1937. Angenaherte auflosung von systemen linearer glei-chungen. Bull. Int. Acad. Pol. Sic. Let., Cl. Sci. Math. Nat. (1937), 355\u2013357.","journal-title":"Bull. Int. Acad. Pol. Sic. Let., Cl. Sci. Math. Nat."},{"key":"e_1_3_6_27_2","first-page":"4134","volume-title":"Conference on Advances in Neural Information Processing Systems","author":"Kerenidis Iordanis","year":"2019","unstructured":"Iordanis Kerenidis, Jonas Landman, Alessandro Luongo, and Anupam Prakash. 2019. Q-means: A quantum algorithm for unsupervised machine learning. In Conference on Advances in Neural Information Processing Systems. 4134\u20134144."},{"key":"e_1_3_6_28_2","first-page":"49:1\u201349:21","volume-title":"8th Innovations in Theoretical Computer Science Conference (ITCS\u201917)","author":"Kerenidis Iordanis","year":"2017","unstructured":"Iordanis Kerenidis and Anupam Prakash. 2017. Quantum recommendation systems. In 8th Innovations in Theoretical Computer Science Conference (ITCS\u201917). 49:1\u201349:21. arXiv:1603.08675."},{"key":"e_1_3_6_29_2","doi-asserted-by":"publisher","DOI":"10.1145\/3406306"},{"key":"e_1_3_6_30_2","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1100.0456"},{"key":"e_1_3_6_31_2","first-page":"3815","volume-title":"International Conference on Machine Learning","author":"Li Tongyang","year":"2019","unstructured":"Tongyang Li, Shouvanik Chakrabarti, and Xiaodi Wu. 2019. Sublinear quantum algorithms for training linear and kernel-based classifiers. In International Conference on Machine Learning. PMLR, 3815\u20133824."},{"key":"e_1_3_6_32_2","doi-asserted-by":"publisher","DOI":"10.22331\/q-2020-11-11-361"},{"key":"e_1_3_6_33_2","doi-asserted-by":"publisher","DOI":"10.1038\/nphys3029"},{"key":"e_1_3_6_34_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10589-020-00220-z"},{"key":"e_1_3_6_35_2","article-title":"Quantum algorithms for spectral sums","author":"Luongo Alessandro","year":"2020","unstructured":"Alessandro Luongo and Changpeng Shao. 2020. Quantum algorithms for spectral sums. arXiv preprint arXiv:2011.06475 (2020).","journal-title":"arXiv preprint arXiv:2011.06475"},{"key":"e_1_3_6_36_2","doi-asserted-by":"crossref","unstructured":"Jacob D. Moorman Thomas K. Tu Denali Molitor and Deanna Needell. 2020. Randomized Kaczmarz with averaging. (2020). arXiv:2002.04126.","DOI":"10.1007\/s10543-020-00824-1"},{"key":"e_1_3_6_37_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719284"},{"key":"e_1_3_6_38_2","doi-asserted-by":"publisher","DOI":"10.1137\/19M1251643"},{"key":"e_1_3_6_39_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10543-010-0265-5"},{"key":"e_1_3_6_40_2","doi-asserted-by":"publisher","DOI":"10.1137\/070704277"},{"key":"e_1_3_6_41_2","doi-asserted-by":"publisher","DOI":"10.1137\/100802001"},{"key":"e_1_3_6_42_2","article-title":"On solving classes of positive-definite quantum linear systems with quadratically improved runtime in the condition number","author":"Orsucci Davide","year":"2021","unstructured":"Davide Orsucci and Vedran Dunjko. 2021. On solving classes of positive-definite quantum linear systems with quadratically improved runtime in the condition number. arXiv preprint arXiv:2101.11868 (2021).","journal-title":"arXiv preprint arXiv:2101.11868"},{"key":"e_1_3_6_43_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.113.130503"},{"key":"e_1_3_6_44_2","doi-asserted-by":"publisher","DOI":"10.1137\/18M1179249"},{"key":"e_1_3_6_45_2","doi-asserted-by":"publisher","DOI":"10.5555\/829576"},{"key":"e_1_3_6_46_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.101.022322"},{"key":"e_1_3_6_47_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00041-008-9030-4"},{"key":"e_1_3_6_48_2","unstructured":"Ewin Tang. 2018. Quantum-inspired classical algorithms for principal component analysis and supervised clustering. (2018). arXiv:1811.00414."},{"key":"e_1_3_6_49_2","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316310"}],"container-title":["ACM Transactions on Quantum Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3520141","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3520141","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T18:10:32Z","timestamp":1750183832000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3520141"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,7,7]]},"references-count":48,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2022,12,31]]}},"alternative-id":["10.1145\/3520141"],"URL":"https:\/\/doi.org\/10.1145\/3520141","relation":{},"ISSN":["2643-6809","2643-6817"],"issn-type":[{"value":"2643-6809","type":"print"},{"value":"2643-6817","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,7,7]]},"assertion":[{"value":"2021-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-02-01","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-07-07","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}