{"id":"arxiv/2610.00506","url":"https://arxiv.org/abs/2610.00506","tags":["quant-ph","cs.CC"],"score":0,"title":"Noisy Quantum Query Complexity via Fractional Block Sensitivity","domain":"quant-ph","source":"arxiv","authors":["Mehil Agarwal","Shravas Rao","Fang Song"],"reviews":0,"subject":"quant-ph","summary":"We study quantum query complexity under several models of imperfect oracle access, and develop lower bounds through a common framework based on fractional block sensitivity ($\\operatorname{fbs}$). For a negligent oracle that applies the correct query with probability $1-p$, we prove a lower bound in terms of $\\operatorname{fbs}(f,0^n)$. We also show, perhaps surprisingly, that negligence need not destroy quantum speedups: any function $f$ can be transformed into a partial function $f'$ whose negligent query complexity essentially preserves the quantum query complexity of $f$. This gives…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-09-30","reactions":{}}