Noisy Quantum Query Complexity via Fractional Block Sensitivity
Abstract
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 (fbs). For a negligent oracle that applies the correct query with probability 1−p, we prove a lower bound in terms of fbs(f,0n). 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 partial functions with exponential quantum speedups even under negligent queries, and in particular rules out a general lower bound in terms of fbs(f) for partial functions in this model. For two other models, we obtain general lower bounds in terms of fbs(f) for all Boolean functions. For hybrid algorithms using Q coherent and C classical queries, we prove the tradeoff C+Q2=Ω(fbs(f)). For an IID dephasing noisy model where each query dephases the query-index register at rate p independently, we prove Ω (p fbs(f)) queries are necessary. Finally, we introduce a broader family of time-varying dephasing models and identify a variational resource that is always lower bounded by fbs(f). Computing this resource reduces to a convex optimization problem, providing a simple way to derive lower bounds for new noise schedules. As applications, we recover the hybrid and IID dephasing bounds and determine the query complexity of unstructured search when the dephasing rate grows over time.
Related
- Optimal query complexity for fractional quantum evolution
- Near-Optimal Separations of Certificate Complexity from Randomized and Quantum Query Complexity
- Quantum Query Complexity Beyond the Worst Case
- Quantum Query Complexity of Tournament Solutions
- Complexity of tensor network simulation for noisy quantum circuits
BibTeX
@misc{agarwal2026noisy,
title = {{Noisy Quantum Query Complexity via Fractional Block Sensitivity}},
author = {Mehil Agarwal and Shravas Rao and Fang Song},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.00506},
eprint = {2610.00506},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.00506},
}
RIS
TY - UNPB
TI - Noisy Quantum Query Complexity via Fractional Block Sensitivity
AU - Mehil Agarwal
AU - Shravas Rao
AU - Fang Song
PY - 2026
DA - 2026/10/02
PB - arXiv
DO - 10.48550/arxiv.2610.00506
UR - https://arxiv.org/abs/2610.00506
AB - 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 (fbs). For a negligent oracle that applies the correct query with probability 1−p, we prove a lower bound in terms of 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 partial functions with exponential quantum speedups even under negligent queries, and in particular rules out a general lower bound in terms of fbs(f) for partial functions in this model. For two other models, we obtain general lower bounds in terms of fbs(f) for all Boolean functions. For hybrid algorithms using Q coherent and C classical queries, we prove the tradeoff C+Q^2=Ω(fbs(f)). For an IID dephasing noisy model where each query dephases the query-index register at rate p independently, we prove Ω (p fbs(f)) queries are necessary. Finally, we introduce a broader family of time-varying dephasing models and identify a variational resource that is always lower bounded by fbs(f). Computing this resource reduces to a convex optimization problem, providing a simple way to derive lower bounds for new noise schedules. As applications, we recover the hybrid and IID dephasing bounds and determine the query complexity of unstructured search when the dephasing rate grows over time.
ER -