PaperlayerView exact revision on arXiv

Source-linked AI summary

Noisy Quantum Query Complexity via Fractional Block Sensitivity

Mehil Agarwal, Shravas Rao, Fang Song

arXiv:2610.00506v1quant-phcs.CC

TL;DR

The paper asks how quantum query speedups fare when oracle access is imperfect. It develops fractional-block-sensitivity lower bounds across noisy models and shows that partial functions can retain quantum query advantages under negligence.

  • Problem

    The paper asks whether quantum speedups persist when quantum computers have limited or imperfect oracle access.

    Source: §1 · p. 2

  • Method

    The authors use fractional block sensitivity to derive lower bounds across four imperfect-oracle models and introduce a flag-based construction for negligent queries.

    Source: §1 · p. 2, §1.2 · p. 9

  • Results

    Fractional block sensitivity at 0^n lower-bounds negligent query complexity, while its global maximum lower-bounds complexity in the other three models; a partial function can preserve its source function’s quantum query complexity under negligence.

    Source: §1 · p. 2

  • Takeaways & Limitations

    Partial functions can retain a source function’s quantum advantage under negligent queries, so negligence does not universally eliminate quantum speedups.

    Source: §1 · p. 2

    A global fractional-block-sensitivity lower bound is false for partial functions in the negligent model; whether total Boolean functions admit such a bound remains open.

    Source: §1.3 · p. 10

Abstract

from arXiv · show

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=\Omega(\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\,\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.

1 Introduction

This introduction examines noisy quantum query models and whether quantum speedups and lower bounds persist under imperfect oracle access, using fractional block sensitivity as a common framework. It also covers hybrid and dephasing models, time-varying noise, a partial-function counterexample, and open questions about tighter bounds and realistic noise models.

1.1 Main Results

  • Fractional block sensitivity at 0^n lower-bounds negligent-oracle query complexity, while its maximum over inputs lower-bounds complexity in the hybrid, IID dephasing, and extended dephasing models.For unstructured search, fbs(f,0^n)=n, recovering the earlier lower bounds [Ros22].Source: §1 · p. 2, §1.1 · p. 4
  • Hybrid algorithms satisfy C+Q^2=Ω(fbs(f)), and IID query-index dephasing requires Ω(p fbs(f)) queries.The hybrid bound also holds when classical queries replace the stronger pseudo-classical queries.Source: §1.1 · p. 4
  • For every function f, a partial function f′ can preserve R(f) while its negligent-oracle query complexity equals the quantum query complexity of f.Thus a general negligent-oracle lower bound in terms of global fbs(f) cannot hold for partial functions.Source: §1 · p. 2, §1.1 · pp. 4–5
  • The computational-opportunity theorem separates the quantum argument from the noise schedule, so analyzing a new dephasing model requires estimating the scalar optimization problem R(µ), not a new quantum lower-bound proof.It recovers lower bounds in hybrid and IID dephasing models and gives tight bounds for computing OR in an increasing-dephasing scenario.Source: §1.1 · p. 5

1.2 Technical Overview

  • The technical overview derives bounds from a weighted star of inputs packed by fbs, where no query index affects more than a 1/W fraction of the weighted leaves.For negligent and pseudo-classical queries it tracks a common branch of center and leaf computations; dephasing analysis instead tracks hidden index records.Source: §1.2 · pp. 5–6
  • For query-index dephasing, the analysis purifies the channel and tracks hidden records, separating unresolved directions, coherent distinctions, and leaves already hit by a record.The record partitions leaves into those not yet hit and those certified as hit.Source: §1.2 · p. 8
  • The cited argument implies a lower bound on pfbs(f,0n); the passage gives no numerical bound or claim that it holds for other reference inputs.Source: §1.2 · p. 8
  • A partial-function construction both refutes a universal global fbs lower bound for negligent queries and preserves quantum speedups by flagging successful queries.The construction encodes bits in complementary pairs so a flag reveals query success without revealing the logical computation; ideal queries can then be simulated by repeating negligent queries.Source: §1.2 · pp. 8–9
  • For predictable time-varying dephasing schedules, the Computational-Opportunity Theorem lower-bounds a resource by fbs(f), using past-dependent parameters to balance coherent accumulation against dephasing.The overview notes that a phase-length resource evaluated with hindsight fails for random schedules because rare long coherent runs receive quadratic credit unavailable when queries are made.Source: §1.2 · pp. 9–10

1.3 Discussion and Open Questions

  • Whether total Boolean functions admit a global fbs lower bound for negligent queries remains open, as does finding a sharper measure for functions such as AND∘OR.The negligent bound is at fbs(f,0^n); for failed queries replaced by a fixed reference oracle Oa, the argument instead gives fbs(f,a).Source: §1.3 · p. 10
  • Open dephasing directions include determining AND∘OR complexity, proving robust simulation with overhead near the lower bounds, and applying the theorem to correlated noise schedules.Examples of correlated schedules include burst noise, recovery processes, and environments with temporal memory; prior work [LMP24] gives polynomial-overhead simulation in the negligent model.Source: §1.3 · p. 10

2 Preliminaries

Translation covariance lets the hybrid and dephasing analyses move a fractional-block-sensitivity maximizer to 0^n. The preliminaries also define a progress measure whose terminal value is bounded below when an algorithm computes the function successfully.

2.1 Translation covariance in hybrid and dephasing models

  • XOR translation preserves quantum and classical query complexity, so a fractional-block-sensitivity maximizer can be moved to 0^n.The same covariance holds for query-index dephasing.Source: §2.1 · p. 10

2.2 Definitions and preliminary lemmas

  • The progress measure is built from fractional-block-sensitivity variables to support query lower bounds.It is defined from a solution to the linear program at 0^n.Source: §2.2 · p. 12
  • Successful computation requires terminal progress at least 1−4pε under the stated worst-case correctness condition.The lemma assumes the algorithm is correct on every input with probability at least 1−ε.Source: §2.2 · p. 12

3 Negligent Oracles

The negligent-oracle analysis bounds progress on a weighted star centered at 0^n, while a partial-function construction shows that negligence can preserve quantum query complexity. The construction also yields partial functions with large separations from randomized query complexity.

3.1 A Regev–Schiff-style weighted-star proof

  • The weighted-star proof bounds one-step progress using constraints on the fractional-block-sensitivity weights, then combines this with terminal progress.The proof follows Regev–Schiff with adjustments for sensitive blocks that may contain multiple indices.Source: §3.1 · pp. 13–14
  • The negligent-oracle lower-bound argument is centered at 0^n because this oracle model lacks the standard XOR translation covariance.After translation correction, the fault branch is generally a nontrivial known oracle rather than the identity channel.Source: §3.1 · p. 14

3.2 Partial-function counterexample

  • The construction encodes each input bit as a complementary pair and leaves f′ undefined on inputs outside that encoding.Randomized query complexity is preserved between f and f′.Source: §3.2 · p. 15
  • Theorem 1.4 shows that negligent oracles need not increase query complexity: some partial functions are computable with O(1) queries even in this model, yet require Ω(N^(1−ε)) randomized queries.Source: §3.2 · p. 15

4 Hybrid Quantum-Classical Queries

The hybrid model divides queries between pseudo-classical and coherent quantum calls. Its lower-bound proof controls progress separately for the two query types and combines those bounds.

4 Hybrid Quantum-Classical Queries

  • A hybrid algorithm uses C pseudo-classical queries and Q coherent quantum queries, with total query count C+Q.The proof distinguishes the times at which each query type is made.Source: §4 · p. 15
  • The proof bounds one-step progress separately for pseudo-classical and quantum queries.The pseudo-classical and quantum growth bounds are given in Lemmas 4.1 and 4.2, respectively.Source: §4 · pp. 16–17
  • Theorem 4.3 states a lower-bound condition for bounded-error algorithms in terms of C pseudo-classical and Q coherent queries.The proof combines the one-step bounds with earlier progress lemmas.Source: §4 · p. 17

5 IID Query-Index Dephasing

For IID query-index dephasing, the analysis purifies the noise into hidden records and tracks progress through a weighted-star potential. Combining one-query growth with terminal progress yields a lower bound proportional to the dephasing rate and fractional block sensitivity.

5.1 Coherent weighted-star potential analysis

  • The analysis purifies dephasing by recording queried indices in an inaccessible register, then decomposes the truth space by the accumulated record.This tracks unresolved directions, coherent distinguishing directions, and leaves already hit by the record.Source: §5.1 · p. 19
  • A dephased query removes the old active Q-direction: its unhit part joins the common unresolved direction, while its hit part moves to C.This change contributes a negative quadratic term to the dephased-query potential bound.Source: §5.1 · pp. 21–22
  • The one-query growth bound conditions on accessible history and averages over the fresh independent dephasing choice.The terminal-progress lemma supplies the complementary progress requirement for bounded-error algorithms.Source: §5.1 · pp. 21–22

5.2 Putting It Together

  • IID query-index dephasing at rate p requires Ω_ε(p·fbs(f,0^n)) queries.The theorem assumes each query is independently fully dephased in the query-index register with probability p.Source: §5 · p. 18, §5.2 · p. 25

6 An Extended Family of Stochastic Dephasing

Section 6 extends query-index dephasing to algorithm-independent schedules and introduces a predictable opportunity resource for lower-bounding computation. The resource yields specializations for hybrid and IID queries and supports matching bounds for search under increasing dephasing.

6.1 Algorithm-independent stochastic dephasing

  • A dephasing schedule may have arbitrary temporal correlations, but must be sampled independently of the input, algorithm, private randomness, and computational registers.The model includes deterministic, IID, Markov, and long-range-correlated schedules, but excludes feedback from the algorithm to future noise.Source: §6.1 · pp. 25–26

6.2 Computational-opportunity resource and fbs lower bound

  • A T-query algorithm computing f with worst-case error ε < 1/2 under schedule µ requires opportunity resource R(µ) ≥ cε fbs(f).The constant cε depends only on ε and universal constants.Source: §6.2 · p. 26
  • The opportunity resource uses a predictable allocation process to represent coherent and dephased shares of progress, converting noisy query lower bounds into an optimization over the schedule.The allocation cannot inspect the current or future dephasing flags; finite cost forces θt = 1 when pt = 0.Source: §6.2 · pp. 26–27

6.2.1 Application: hybrid and IID specializations

  • For deterministic schedules with Q coherent and C dephased queries, R(µ) = Q^2 + C, yielding C + Q^2 = Ωε(fbs(f)).This is the hybrid-query specialization of the resource theorem.Source: §6.2.1 · p. 27
  • Corollary 6.5 specializes the opportunity bound to IID Bernoulli dephasing with probability p.The supplied corollary passage identifies the IID setting; its displayed bound is not fully stated in the passage text.Source: §6.2.1 · p. 27

6.2.2 Application: A Tight Aging-Noise Application

  • For search with pt = min{1, λt^γ}, the section matches lower bounds with an Oγ(S) block-Grover upper bound in each stated regime.The schedule parameters λ and γ set the overall noise scale and its rate of increase over time.Source: §6.2.2 · pp. 28–29

6.3 Proving the computational-opportunity theorem

  • Conditioning on the accessible history gives the one-query growth bound with time-varying pt, while the terminal progress condition remains unchanged.The proof therefore carries over the IID analysis with conditional dephasing probabilities.Source: §6.3 · p. 30
  • The lower bound extends from a center x⋆ to fbs(f) by translating the function, since query-index dephasing is invariant under the corresponding basis permutation.The proof first bounds the resource by the fractional block sensitivity centered at 0^n.Source: §6.3 · p. 31

AI Disclosure

The disclosure describes LLM assistance with editorial work and two substantive interactions. The authors state that they independently verified and take responsibility for the AI-assisted content.

AI Disclosure

  • LLMs assisted with checking typos, grammar, and editorial suggestions and corrections.The disclosure separately identifies two substantive interactions.Source: AI Disclosure · p. 32
  • Claude Fable 5 suggested a partial-function counterexample to extending the negligent-query lower bound, which the authors verified and generalized to Theorem 1.4.Source: AI Disclosure · p. 32
  • GPT-5.6 Sol suggested an opportunity-resource formulation after identifying a counterexample to a conjectured hybrid-bound generalization.The authors independently formulated and proved the Computational-Opportunity Theorem and developed its applications.Source: AI Disclosure · p. 32
  • The authors state that they verified the correctness and originality of AI-assisted content and take responsibility for the paper’s results.Source: AI Disclosure · p. 32
Loading 2610.00506v1…