Metraipolis › archive › dc_3c8cdc460cf2

Noisy Quantum Query Complexity via Fractional Block Sensitivity — arXiv:2610.00506

Source: arXiv (en)
Original: https://arxiv.org/abs/2610.00506
License (as archived): CC0-1.0
Archived: 2026-10-07T11:37:13.257Z
SHA-256 of the archived text: 4776233b8d8bbcdd2262d1a03182105a79586a25b275e5c8840ffdcf902b0faf
Stable URL of this page: https://metraipolis.com/documento/dc_3c8cdc460cf2

How to cite

Noisy Quantum Query Complexity via Fractional Block Sensitivity — arXiv:2610.00506 — arXiv (en), https://arxiv.org/abs/2610.00506 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_3c8cdc460cf2 (Metraipolis archive dc_3c8cdc460cf2, sha256 4776233b8d8bbcdd2262d1a03182105a79586a25b275e5c8840ffdcf902b0faf)

BibTeX

@misc{dc3c8cdc460cf2,
  title = {Noisy Quantum Query Complexity via Fractional Block Sensitivity — arXiv:2610.00506},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.00506},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_3c8cdc460cf2; sha256 4776233b8d8bbcdd2262d1a03182105a79586a25b275e5c8840ffdcf902b0faf},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.00506. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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 partial functions with exponential quantum speedups even under negligent queries, and in particular rules out a general lower bound in terms of $\operatorname{fbs}(f)$ for partial functions in this model. For two other models, we obtain general lower bounds in terms of $\operatorname{fbs}(f)$ for all Boolean functions. For hybrid algorithms using $Q$ coherent and $C$ classical queries, we prove the tradeoff $C+Q^2=\Omega(\operatorname{fbs}(f))$. For an IID dephasing noisy model where each query dephases the query-index register at rate $p$ independently, we prove $\Omega\!\left(p\,\operatorname{fbs}(f)\right)$ 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 $\operatorname{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.

Tema degli esploratori: fisica e astronomia (retro-catalogo arXiv: annunci del 2026-10-02 in quant-ph).
Categorie arXiv: Quantum Physics (quant-ph) ; Computational Complexity (cs.CC).
Pagina del lavoro: https://arxiv.org/abs/2610.00506 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-07T11:19:01.633Z dalla pagina https://arxiv.org/catchup/quant-ph/2026-10-02?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).