{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,18]],"date-time":"2026-05-18T13:50:51Z","timestamp":1779112251388,"version":"3.51.4"},"reference-count":41,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2025,1,18]],"date-time":"2025-01-18T00:00:00Z","timestamp":1737158400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc-nd\/4.0"},{"start":{"date-parts":[[2025,1,18]],"date-time":"2025-01-18T00:00:00Z","timestamp":1737158400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc-nd\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["comput. complex."],"published-print":{"date-parts":[[2025,6]]},"DOI":"10.1007\/s00037-024-00262-3","type":"journal-article","created":{"date-parts":[[2025,1,18]],"date-time":"2025-01-18T07:08:27Z","timestamp":1737184107000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Robust Dequantization of the Quantum Singular Value Transformation and Quantum Machine Learning Algorithms"],"prefix":"10.1007","volume":"34","author":[{"given":"Fran\u00e7ois","family":"Le Gall","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,1,18]]},"reference":[{"key":"262_CR1","doi-asserted-by":"crossref","unstructured":"Scott Aaronson (2015). Read the fine print. Nature Physics 11,\n291-293.","DOI":"10.1038\/nphys3272"},{"key":"262_CR2","doi-asserted-by":"crossref","unstructured":"Ainesh Bakshi & Ewin Tang (2024). An Improved Classical Singular\nValue Transformation for Quantum Machine Learning. In Proceedings\nof the 2024 ACM-SIAM Symposium on Discrete Algorithms (SODA\n2024), 2398\u20132453.","DOI":"10.1137\/1.9781611977912.86"},{"key":"262_CR3","doi-asserted-by":"crossref","unstructured":"Zhihuai Chen, Yinan Li, Xiaoming Sun, Pei Yuan & Jialin\nZhang (2019). A Quantum-inspired Classical Algorithm for Separable\nNon-negative Matrix Factorization. In Proceedings of the 28th International\nJoint Conference on Artificial Intelligence (IJCAI 2019),\n4511\u20134517.","DOI":"10.24963\/ijcai.2019\/627"},{"key":"262_CR4","unstructured":"Nai-Hui Chia, Andr\u00e1s Gily\u00e9n, Han-Hsuan Lin, Seth Lloyd,\nEwin Tang & Chunhao Wang (2020a). Quantum-Inspired Algorithms\nfor Solving Low-Rank Linear Equation Systems with Logarithmic\nDependence on the Dimension. In Proceedings of the 31st International\nSymposium on Algorithms and Computation (ISAAC 2020),\nvolume 181 of LIPIcs, 47:1\u201347:17."},{"key":"262_CR5","unstructured":"Nai-Hui Chia, Tongyang Li, Han-Hsuan Lin & Chunhao Wang\n(2020b). Quantum-Inspired Sublinear Algorithm for Solving Low-Rank\nSemidefinite Programming. In Proceedings of the 45th International\n Symposium on Mathematical Foundations of Computer Science (MFCS\n2020), volume 170 of LIPIcs, 23:1\u201323:15."},{"key":"262_CR6","doi-asserted-by":"crossref","unstructured":"Nai-Hui Chia, Andr\u00e1s Pal Gily\u00e9n, Tongyang Li, Han-Hsuan\nLin, Ewin Tang & Chunhao Wang (2022). Sampling-based Sublinear\nLow-rank Matrix Arithmetic Framework for Dequantizing Quantum\nMachine Learning. Journal of the ACM 69(5), 33:1\u201333:72.","DOI":"10.1145\/3549524"},{"key":"262_CR7","doi-asserted-by":"crossref","unstructured":"Iris Cong & Luming Duan (2016). Quantum discriminant analysis\nfor dimensionality reduction and classification. New Journal of Physics\n18(7), 073 011.","DOI":"10.1088\/1367-2630\/18\/7\/073011"},{"key":"262_CR8","unstructured":"Jordan Cotler, Hsin-Yuan Huang & Jarrod R. McClean\n(2021). Revisiting dequantization and quantum advantage in learning\ntasks. arXiv:2112.00811."},{"key":"262_CR9","doi-asserted-by":"crossref","unstructured":"Luc Devroye (1986). Non-Uniform Random Variate Generation.\nSpringer.","DOI":"10.1007\/978-1-4613-8643-8"},{"key":"262_CR10","doi-asserted-by":"crossref","unstructured":"Chen Ding, Tian-Yi Bao & He-Liang Huang (2022). Quantum-\nInspired Support Vector Machine. IEEE Transactions on Neural Networks\nand Learning Systems 33(12), 7210\u20137222.","DOI":"10.1109\/TNNLS.2021.3084467"},{"key":"262_CR11","doi-asserted-by":"crossref","unstructured":"Petros Drineas, Alan M. Frieze, Ravi Kannan, Santosh S.\nVempala & V. Vinay (2004). Clustering Large Graphs via the Singular\nValue Decomposition. Machine Learning 56(1-3), 9\u201333.","DOI":"10.1023\/B:MACH.0000033113.59016.96"},{"key":"262_CR12","doi-asserted-by":"crossref","unstructured":"Petros Drineas & Ravi Kannan (2001). Fast Monte-Carlo Algorithms\nfor Approximate Matrix Multiplication. In Proceedings of the\n42nd Annual Symposium on Foundations of Computer Science (FOCS\n2001), 452\u2013459.","DOI":"10.1109\/SFCS.2001.959921"},{"key":"262_CR13","doi-asserted-by":"crossref","unstructured":"Petros Drineas, Ravi Kannan & Michael W. Mahoney (2006a).\nFast Monte Carlo Algorithms for Matrices I: Approximating Matrix\nMultiplication. SIAM Journal on Computing 36(1), 132\u2013157.","DOI":"10.1137\/S0097539704442684"},{"key":"262_CR14","doi-asserted-by":"crossref","unstructured":"Petros Drineas, Ravi Kannan & Michael W. Mahoney (2006b).\nFast Monte Carlo Algorithms for Matrices II: Computing a Low-Rank\nApproximation to a Matrix. SIAM Journal on Computing 36(1), 158\u2013\n183.","DOI":"10.1137\/S0097539704442696"},{"key":"262_CR15","doi-asserted-by":"crossref","unstructured":"Petros Drineas, Ravi Kannan & Michael W. Mahoney (2006c).\nFast Monte Carlo Algorithms for Matrices III: Computing a Compressed\n Approximate Matrix Decomposition. SIAM Journal on Computing\n36(1), 184\u2013206.","DOI":"10.1137\/S0097539704442702"},{"key":"262_CR16","doi-asserted-by":"crossref","unstructured":"Yuxuan Du, Min-Hsiu Hsieh, Tongliang Liu & Dacheng Tao\n(2020). Quantum-inspired algorithm for general minimum conical hull\nproblems. Physical Review Research 2, 033 199.","DOI":"10.1103\/PhysRevResearch.2.033199"},{"key":"262_CR17","doi-asserted-by":"crossref","unstructured":"Alan M. Frieze, Ravi Kannan & Santosh S. Vempala (2004).\nFast Monte-Carlo algorithms for finding low-rank approximations. Journal\nof the ACM 51(6), 1025\u20131041.","DOI":"10.1145\/1039488.1039494"},{"key":"262_CR18","doi-asserted-by":"crossref","unstructured":"Sevag Gharibian & Franc\u00b8ois Le Gall (2022). Dequantizing the\nQuantum singular value transformation: hardness and applications to\nQuantum chemistry and the Quantum PCP conjecture. In Proceedings\nof the 54th Annual ACM SIGACT Symposium on Theory of Computing\n(STOC 2022), 19\u201332.","DOI":"10.1145\/3519935.3519991"},{"key":"262_CR19","doi-asserted-by":"crossref","unstructured":"Michael I. Gil (2010). Perturbations of functions of diagonalizable\nmatrices. Electronic Journal of Linear Algebra 20, 303\u2013313.","DOI":"10.13001\/1081-3810.1375"},{"key":"262_CR20","doi-asserted-by":"crossref","unstructured":"Andr\u00e1s Gily\u00e9n, Zhao Song & Ewin Tang (2022). An improved\nquantum-inspired algorithm for linear regression. Quantum 6, 754.","DOI":"10.22331\/q-2022-06-30-754"},{"key":"262_CR21","doi-asserted-by":"crossref","unstructured":"Andr\u00e1s Gily\u00e9n, Yuan Su, Guang Hao Low & Nathan Wiebe\n(2019). Quantum singular value transformation and beyond: exponential\nimprovements for quantum matrix arithmetics. In Proceedings of\nthe 51st Annual ACM SIGACT Symposium on Theory of Computing\n(STOC 2019), 193\u2013204.","DOI":"10.1145\/3313276.3316366"},{"key":"262_CR22","unstructured":"Andr\u00e1s Gily\u00e9n, Seth Lloyd & Ewin Tang (2018). Quantuminspired\nlow-rank stochastic regression with logarithmic dependence on\nthe dimension. arXiv:1811.04909."},{"key":"262_CR23","doi-asserted-by":"crossref","unstructured":"Aram W. Harrow, Avinatan Hassidim & Seth Lloyd (2009).\nQuantum Algorithm for Linear Systems of Equations. Physical Review\nLetters 103, 150 502. Full version available as  arXiv:0811.3171.","DOI":"10.1103\/PhysRevLett.103.150502"},{"key":"262_CR24","doi-asserted-by":"crossref","unstructured":"Alan J. Hoffman & Helmut W. Wielandt (1953). The variation\nof the spectrum of a normal matrix. Duke Mathematical Journal 20(1),\n37\u201339.","DOI":"10.1215\/S0012-7094-53-02004-3"},{"key":"262_CR25","doi-asserted-by":"crossref","unstructured":"Mark Jerrum, Leslie G. Valiant & Vijay V. Vazirani (1986).\nRandom Generation of Combinatorial Structures from a Uniform Distribution.\nTheoretical Computer Science 43, 169\u2013188.","DOI":"10.1016\/0304-3975(86)90174-X"},{"key":"262_CR26","unstructured":"Dhawal Jethwani, Franc\u00b8ois Le Gall & Sanjay K. Singh (2020).\nQuantum-Inspired Classical Algorithms for Singular Value Transformation.\nIn Proceedings of the 45th International Symposium on Mathematical\nFoundations of Computer Science (MFCS 2020), volume 170\nof LIPIcs, 53:1\u201353:14."},{"key":"262_CR27","doi-asserted-by":"crossref","unstructured":"Ravi Kannan & Santosh S. Vempala (2009). Spectral Algorithms.\nFoundations and Trends(r) in Theoretical Computer Science 4(3-4),\n157\u2013288.","DOI":"10.1561\/0400000025"},{"key":"262_CR28","doi-asserted-by":"crossref","unstructured":"Ravindran Kannan & Santosh S. Vempala (2017). Randomized\nalgorithms in numerical linear algebra. Acta Numerica 26, 95\u2013135.","DOI":"10.1017\/S0962492917000058"},{"key":"262_CR29","unstructured":"Iordanis Kerenidis & Anupam Prakash (2017). Quantum Recommendation\nSystems. In Proceedings of the 8th Innovations in Theoretical\nComputer Science Conference (ITCS 2017), volume 67 of LIPIcs,\n49:1\u201349:21."},{"key":"262_CR30","doi-asserted-by":"crossref","unstructured":"Yang Liu & Shengyu Zhang (2017). Fast quantum algorithms for\nleast squares regression and statistic leverage scores. Theoretical Computer\nScience 657(A), 38\u201347.","DOI":"10.1016\/j.tcs.2016.05.044"},{"key":"262_CR31","unstructured":"Seth Lloyd, Masoud Mohseni & Patrick Rebentrost (2013).\nQuantum algorithms for supervised and unsupervised machine learning. arXiv:1307.0411."},{"key":"262_CR32","doi-asserted-by":"crossref","unstructured":"Seth Lloyd, Masoud Mohseni & Patrick Rebentrost (2014).\nQuantum principal component analysis. Nature Physics 10, 631-633.","DOI":"10.1038\/nphys3029"},{"key":"262_CR33","doi-asserted-by":"crossref","unstructured":"John M. Martyn, Zane M. Rossi, Andrew K. Tan & Isaac L.\nChuang (2021). Grand Unification of Quantum Algorithms. PRX\nQuantum 2, 040 203.","DOI":"10.1103\/PRXQuantum.2.040203"},{"key":"262_CR34","doi-asserted-by":"crossref","unstructured":"Colin McDiarmid (1989). On the method of bounded differences. In\nSurveys in combinatorics, 1989 (Norwich, 1989), volume 141 of London\nMathematical Society Lecture Note series, 148\u2013188. Cambridge University\nPress. ISBN 0-521-37823-0.","DOI":"10.1017\/CBO9781107359949.008"},{"key":"262_CR35","doi-asserted-by":"crossref","unstructured":"Patrick Rebentrost, Masoud Mohseni & Seth Lloyd (2014).\nQuantum Support Vector Machine for Big Data Classification. Physical\nReview Letters 113, 130 503.","DOI":"10.1103\/PhysRevLett.113.130503"},{"key":"262_CR36","doi-asserted-by":"crossref","unstructured":"Patrick Rebentrost, Thomas R. Bromley, Christian Weedbrook\n& Seth Lloyd (2018a). Quantum Hopfield neural network.\nPhysical Review A 98(4).","DOI":"10.1103\/PhysRevA.98.042308"},{"key":"262_CR37","doi-asserted-by":"crossref","unstructured":"Patrick Rebentrost, Adrian Steffens, Iman Marvian & Seth\nLloyd (2018b). Quantum singular-value decomposition of nonsparse\nlow-rank matrices. Physical Review A 97, 012 327.","DOI":"10.1103\/PhysRevA.97.012327"},{"key":"262_CR38","doi-asserted-by":"crossref","unstructured":"Changpeng Shao & Ashley Montanaro (2022). Faster Quantum-\nInspired Algorithms for Solving Linear Systems. ACM Transactions on\nQuantum Computing 3(4). ISSN 2643-6809.","DOI":"10.1145\/3520141"},{"key":"262_CR39","doi-asserted-by":"crossref","unstructured":"Ewin Tang (2019). A quantum-inspired classical algorithm for recommendation\nsystems. In Proceedings of the 51st Annual ACM SIGACT\nSymposium on Theory of Computing (STOC 2019), 217\u2013228.","DOI":"10.1145\/3313276.3316310"},{"key":"262_CR40","doi-asserted-by":"crossref","unstructured":"Ewin Tang (2021). Quantum Principal Component Analysis Only\nAchieves an Exponential Speedup Because of Its State Preparation Assumptions.\nPhysical Review Letters 127, 060 503.","DOI":"10.1103\/PhysRevLett.127.060503"},{"key":"262_CR41","doi-asserted-by":"crossref","unstructured":"Nathan Wiebe, Daniel Braun & Seth Lloyd (2012). Quantum\nAlgorithm for Data Fitting. Physical Review Letters 109, 050 505.","DOI":"10.1103\/PhysRevLett.109.050505"}],"updated-by":[{"DOI":"10.1007\/s00037-025-00265-8","type":"correction","label":"Correction","source":"publisher","updated":{"date-parts":[[2025,3,1]],"date-time":"2025-03-01T00:00:00Z","timestamp":1740787200000}}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-024-00262-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00037-024-00262-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-024-00262-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,21]],"date-time":"2025-07-21T23:11:13Z","timestamp":1753139473000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00037-024-00262-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,1,18]]},"references-count":41,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,6]]}},"alternative-id":["262"],"URL":"https:\/\/doi.org\/10.1007\/s00037-024-00262-3","relation":{"correction":[{"id-type":"doi","id":"10.1007\/s00037-025-00265-8","asserted-by":"object"}]},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,1,18]]},"assertion":[{"value":"28 December 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 January 2025","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 March 2025","order":3,"name":"change_date","label":"Change Date","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Correction","order":4,"name":"change_type","label":"Change Type","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"A Correction to this paper has been published:","order":5,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"https:\/\/doi.org\/10.1007\/s00037-025-00265-8","URL":"https:\/\/doi.org\/10.1007\/s00037-025-00265-8","order":6,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"2"}}