{"id":"arxiv/2610.42069","url":"https://arxiv.org/abs/2610.42069","tags":["quant-ph","cs.DS","math.OC"],"score":0,"title":"The Quartic Gap Between Quantum and Dequantized Algorithms for Linear Algebra Is Tight","domain":"quant-ph","source":"arxiv","authors":["Shouvanik Chakrabarti","Dylan Herman","Junhyung Lyle Kim","Guneykan Ozgul"],"reviews":0,"subject":"quant-ph","summary":"Quantum algorithms for linear algebra that access a matrix $A$ through quantum random access memory (QRAM) prepare quantum states proportional to the solutions of linear systems and related problems. Dequantized classical algorithms, when given sampling and query access to $A$, return sampling and query access to an approximate solution. Both kinds of algorithms use a number of queries that is polynomial in the normalized Frobenius norm $ρ=\\|A\\|_F/\\|A\\|$ and does not directly depend on the dimension. For linear systems at fixed condition number and accuracy, quantum algorithms use…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-10-30","reactions":{}}