Quantum query complexity lower bounds under query noise models
Noisy Quantum Query Complexity via Fractional Block Sensitivity
Computational Complexity
Summary
Quantum computers often get information by asking questions (queries) to an oracle. This paper looks at how noisy or imperfect these questions can affect the power of quantum algorithms. The authors find ways to measure and bound how hard it is to solve problems when queries can be wrong or partially corrupted. Surprisingly, some quantum speed advantages survive even with noisy queries. They also provide formulas and methods to understand how various noise types affect quantum query complexity.
What this means in practice
- •For quantum algorithm designers: Use lower bounds to understand limits of quantum algorithms when queries are noisy or imperfect, helping refine algorithms under realistic conditions.
- •For quantum hardware architects: Inform hardware tolerances by linking noise levels in quantum query implementations to fundamental complexity limits.
A theory result. No direct application yet.
Authors
Mehil Agarwal, Shravas Rao, Fang Song
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,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 \(Ω\!\left(p\,\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 \(\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.