{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,3]],"date-time":"2026-06-03T12:12:04Z","timestamp":1780488724963,"version":"3.54.1"},"reference-count":46,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-2006359"],"award-info":[{"award-number":["CCF-2006359"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-2422205"],"award-info":[{"award-number":["CCF-2422205"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Schmidt Sciences"},{"DOI":"10.13039\/100006234","name":"Sandia National Laboratories","doi-asserted-by":"publisher","award":["DE-NA0003525"],"award-info":[{"award-number":["DE-NA0003525"]}],"id":[{"id":"10.13039\/100006234","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-2006359"],"award-info":[{"award-number":["CCF-2006359"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-2422205"],"award-info":[{"award-number":["CCF-2422205"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000893","name":"Simons Foundation","doi-asserted-by":"publisher","award":["928589"],"award-info":[{"award-number":["928589"]}],"id":[{"id":"10.13039\/100000893","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2026,6,30]]},"DOI":"10.1137\/24m1710164","type":"journal-article","created":{"date-parts":[[2026,5,20]],"date-time":"2026-05-20T11:25:11Z","timestamp":1779276311000},"page":"469-519","source":"Crossref","is-referenced-by-count":0,"title":["Quantum Time-Space Tradeoffs for Matrix Problems"],"prefix":"10.1137","volume":"55","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2666-3545","authenticated-orcid":false,"given":"Paul","family":"Beame","sequence":"first","affiliation":[{"name":"Department of Computer Science & Engineering, University of Washington, Seattle, WA 98195 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1519-726X","authenticated-orcid":false,"given":"Niels","family":"Kornerup","sequence":"additional","affiliation":[{"name":"University of Texas at Austin, Austin, TX 78712 USA. Current address: Sandia National Laboratories, Albuquerque, NM 87185 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5930-4733","authenticated-orcid":false,"given":"Michael","family":"Whitmeyer","sequence":"additional","affiliation":[{"name":"Department of Computer Science & Engineering, University of Washington, Seattle, WA 98195 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2026,5,20]]},"reference":[{"key":"ref1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2005.v001a001"},{"key":"ref2","doi-asserted-by":"publisher","DOI":"10.1137\/0216067"},{"key":"ref3","doi-asserted-by":"publisher","DOI":"10.1109\/FSCS.1990.89561"},{"key":"ref4","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(91)90014-V"},{"key":"ref5","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2005.v001a008"},{"key":"ref6","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2002.1826"},{"key":"ref7","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-007-9022-9"},{"key":"ref8","doi-asserted-by":"crossref","unstructured":"A. Bakshi and E. Tang, An improved classical singular value transformation for quantum machine learning, in Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA \u201924, SIAM, 2024, pp. 2398\u20132453, https:\/\/doi.org\/10.1137\/1.9781611977912.","DOI":"10.1137\/1.9781611977912.86"},{"key":"ref9","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502097"},{"key":"ref10","doi-asserted-by":"publisher","DOI":"10.1137\/0220017"},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1778"},{"key":"ref12","first-page":"20","volume":"17","author":"Beame P.","year":"2025","journal-title":"ACM Trans. Comput. Theory"},{"key":"ref13","doi-asserted-by":"publisher","DOI":"10.1145\/3618260.3649700"},{"key":"ref14","doi-asserted-by":"publisher","DOI":"10.1145\/636865.636867"},{"key":"ref15","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796300921"},{"key":"ref16","doi-asserted-by":"publisher","DOI":"10.1137\/0211022"},{"key":"ref17","doi-asserted-by":"crossref","unstructured":"A. Borodin, M. J. Fischer, D. G. Kirkpatrick, N. A. Lynch, and M. Tompa, A time-space tradeoff for sorting on non-oblivious machines, in Proceedings of the 20th Annual Symposium on Foundations of Computer Science, IEEE Computer Society, 1979, pp. 319\u2013327, https:\/\/doi.org\/10.1109\/SFCS.1979.4.","DOI":"10.1109\/SFCS.1979.4"},{"key":"ref18","unstructured":"N. Chepurko, K. L. Clarkson, L. Horesh, H. Lin, and D. P. Woodruff, Quantum-inspired algorithms from randomized numerical linear algebra, Proceedings of Machine Learning Research, PMLR, International Conference on Machine Learning, ICML, 2022, 162, pp. 3879\u20133900, https:\/\/proceedings.mlr.press\/v162\/chepurko22a.html."},{"key":"ref19","doi-asserted-by":"crossref","unstructured":"N.H. Chia, A. Gily\u00e9n, T. Li, H.H. Lin, E. Tang, and C. Wang, Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning, in Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, ACM, New York, 2020, pp. 387\u2013400, https:\/\/doi.org\/10.1145\/3357713.3384314.","DOI":"10.1145\/3357713.3384314"},{"key":"ref20","unstructured":"N.H. Chia, A. Gily\u00e9n, H.H. Lin, S. Lloyd, E. Tang, and C. 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), Vol. 181, LIPIcs, Dagstuhl, Germany, 2020, pp. 47:1\u201347:17, https:\/\/doi.org\/10.4230\/LIPIcs.ISAAC.2020.47."},{"key":"ref21","doi-asserted-by":"publisher","DOI":"10.1137\/16M1087072"},{"key":"ref22","doi-asserted-by":"publisher","DOI":"10.1098\/rspa.1992.0167"},{"key":"ref23","doi-asserted-by":"publisher","DOI":"10.22331\/q-2022-06-30-754"},{"key":"ref24","doi-asserted-by":"crossref","unstructured":"A. Gily\u00e9n, Y. Su, G. H. Low, and N. 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, STOC 2019, ACM, New York, 2019, pp. 193\u2013204, https:\/\/doi.org\/10.1145\/3313276.3316366.","DOI":"10.1145\/3313276.3316366"},{"key":"ref25","doi-asserted-by":"crossref","unstructured":"L. K. Grover, A fast quantum mechanical algorithm for database search, in Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, STOC \u201996, ACM, New York, 1996, pp. 212\u2013219, https:\/\/doi.org\/10.1145\/237814.237866.","DOI":"10.1145\/237814.237866"},{"key":"ref26","doi-asserted-by":"crossref","unstructured":"Y. Hamoudi, Q. Liu, and M. Sinha, The NISQ complexity of collision finding, in Advances in Cryptology - EUROCRYPT 2024 - 43rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zurich, Switzerland, May 26-30, 2024, Proceedings, Part IV, Lect. Notes Comp. Sci. 14654, M. Joye and G. Leander, eds. Springer, Zurich, Switzerland, 2024, pp. 3\u201332, https:\/\/doi.org\/10.1007\/978-3-031-58737-5.","DOI":"10.1007\/978-3-031-58737-5_1"},{"key":"ref27","doi-asserted-by":"publisher","DOI":"10.1145\/3589986"},{"key":"ref28","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.103.150502"},{"key":"ref29","first-page":"411","volume":"17","author":"J\u00e1J\u00e1 J. F.","year":"1982","journal-title":"Acta Inform."},{"key":"ref30","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2008.11.001"},{"key":"ref31","doi-asserted-by":"publisher","DOI":"10.1137\/05063235X"},{"key":"ref32","doi-asserted-by":"crossref","unstructured":"Q. Liu and M. Zhandry, On finding quantum multi-collisions, in Advances in Cryptology - EUROCRYPT 2019 - 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings, Part III, Lect. Notes Comp. Sci. 11478, Springer, Darmstadt, Germany, 2019, pp. 189\u2013218, https:\/\/doi.org\/10.1007\/978-3-030-17659-4.","DOI":"10.1007\/978-3-030-17659-4_7"},{"key":"ref33","doi-asserted-by":"publisher","DOI":"10.22331\/q-2019-07-12-163"},{"key":"ref34","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(93)90257-T"},{"key":"ref35","unstructured":"A. Rosmanis, Tight Bounds for Inverting Permutations via Compressed Oracle Arguments, preprint, arXiv:2103.08975, 2021, https:\/\/doi.org\/10.48550\/arXiv.2103.08975."},{"key":"ref36","first-page":"1490","author":"Santhi N.","year":"2006","journal-title":"Proceedings 2006 IEEE International Symposium on Information Theory, ISIT, IEEE 2006"},{"key":"ref37","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780571"},{"key":"ref38","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1978.1055938"},{"key":"ref39","doi-asserted-by":"publisher","DOI":"10.1137\/110842661"},{"key":"ref40","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796298637"},{"key":"ref41","doi-asserted-by":"crossref","unstructured":"R. Spalek, The multiplicative quantum adversary, in Proceedings of the 23rd Annual IEEE Conference on Computational Complexity, CCC 2008, 2008, pp. 237\u2013248, https:\/\/doi.org\/10.1109\/CCC.2008.9.","DOI":"10.1109\/CCC.2008.9"},{"key":"ref42","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2006.v002a001"},{"key":"ref43","doi-asserted-by":"crossref","unstructured":"E. Tang, A quantum-inspired classical algorithm for recommendation systems, in Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, ACM, 2019, pp. 217\u2013228, https:\/\/doi.org\/10.1145\/3313276.","DOI":"10.1145\/3313276.3316310"},{"key":"ref44","doi-asserted-by":"publisher","DOI":"10.1145\/800133.804348"},{"key":"ref45","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(84)90029-1"},{"key":"ref46","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-26951-7_9"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","deposited":{"date-parts":[[2026,6,3]],"date-time":"2026-06-03T11:24:23Z","timestamp":1780485863000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/24M1710164"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,5,20]]},"references-count":46,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2026,6,30]]}},"alternative-id":["10.1137\/24M1710164"],"URL":"https:\/\/doi.org\/10.1137\/24m1710164","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,5,20]]}}}