PaperlayerView exact revision on arXiv

Source-linked AI summary

Quantum Query Complexity Beyond the Worst Case

Srinivasan Arunachalam, Yanlin Chen, Amin Shiraz Gilani

arXiv:2609.35580v1quant-phcs.CC

TL;DR

Smoothed analysis studies algorithm performance between worst-case and average-case settings, and this paper initiates its systematic study for quantum query complexity. It characterizes symmetric functions and gives a total-function separation and quantum speedups for string problems, while restricting its focus to query complexity.

  • Problem

    The paper asks whether smoothing—small random perturbations of adversarial inputs—can reveal quantum query advantages beyond worst-case analysis.

    Source: §1 · p. 3

  • Method

    The authors study smoothed quantum query algorithms for symmetric Boolean functions, a total version of Simon’s problem, and string problems including pattern matching and edit distance.

    Source: §1.1 · pp. 3–5

  • Results

    The paper gives an exponential smoothed quantum-classical separation for a total function, near-tight smoothed query characterizations for symmetric Boolean functions, and quantum speedups for string problems in various regimes.

    Source: §1.1 · pp. 4–5

  • Takeaways & Limitations

    The results show that small random perturbations can expose quantum query speedups that worst-case analysis alone may not reveal.

    Source: §1.1 · p. 3

    The paper focuses mostly on query complexity and leaves the time model for future work.

    Source: §2.3 · p. 9

Abstract

from arXiv · show

Smoothed analysis is a central framework in classical algorithms for explaining the performance of algorithms beyond the worst case, often explaining why algorithms perform well in practice. We initiate a systematic study of its quantum counterpart and show the following results. $(1)$ We show that there is a total function whose smoothed quantum query complexity is exponentially smaller than its classical query complexity. $(2)$ We give near-tight characterizations of smoothed randomized and quantum query complexities for symmetric Boolean functions, unifying the worst-case complexity results of [Beals et al, FOCS'98] and average-case complexity results of [Ambainis and de Wolf, STACS'00]. $(3)$ We study string problems such as pattern matching and edit distance and, in various regimes, give polynomial to superpolynomial quantum speedups. Our main technical ingredients include a near-tight quantum algorithm for $\varepsilon$-approximating the number of collisions between two non-repetitive strings, improving the result of Le Gall and Ng [QIC'22]. Together, our results show that smoothing can reveal larger quantum speedups than worst-case analysis suggests, opening a path towards quantum advantage on more realistic inputs.

1 Introduction

This paper brings smoothed analysis—a framework that interpolates between worst-case and average-case analysis—to quantum query complexity. It studies symmetric functions, a total-function separation, and string problems, while outlining further questions for the area.

1.1 Main results

  • A total version of Simon’s problem has worst-case quantum query complexity Ω(2^(n/2)), yet admits a polynomial-query smoothed quantum algorithm, separating smoothed quantum and classical complexity exponentially.The problem removes Simon’s promise and asks whether the function has a period.Source: §1.1 · p. 4
  • For every symmetric Boolean function, transition cost and weighted influence characterize smoothed randomized and quantum query complexities up to polylogarithmic factors.The characterization extends the paper’s analysis to both query models.Source: §1.1 · p. 4
  • The paper’s symmetric-function upper bounds estimate Hamming weight with increasing precision and stop once the consistent weights determine the function value.Random sampling is used classically and amplitude estimation quantumly; contributions across transitions lead to weighted influence in the quantum bound.Source: §1.1 · p. 4
  • For exact pattern matching with an arbitrary explicit pattern and a perturbed text, the authors report optimal bounds; the corresponding random-instance quantum algorithm also retains a super-polynomial improvement under smoothing.The latter setting perturbs both text and pattern, while the exact formulation perturbs only the text.Source: §1.1 · p. 5
  • When smoothed-string edit distance R = ω(√n), the quantum query complexity is polynomially smaller; for R = Θ(n), it falls from eO(√n/σ) to eO(n1/3/σ).The comparison is against the earlier smoothed edit-distance bound described in the passage.Source: §1.1 · p. 6
  • The collision-estimation improvements and collision-enumeration algorithm provide complementary primitives for quantumizing the Ulam-distance framework.The enumeration algorithm uses eO(n2/3(m + 1)1/3) queries to recover m collisions between two non-repetitive strings.Source: §1.1 · p. 6

1.2 Open questions

  • The authors identify open directions including Fourier sampling beyond abelian groups, other practical problems, smoothed quantum-state learning, and guarantees for quantum heuristics.They frame the work as an initial study and leave basic questions open.Source: §1.2 · p. 7

2 Preliminaries

The preliminaries establish probability tools, quantum subroutines, and the discrete smoothed-query model used in the paper. The model interpolates between worst-case and uniform-average expected query complexity while requiring correctness on every input.

2.1 Useful lemmas

  • Concentration inequalities, binomial point-mass bounds, and log-concavity of sums of independent Bernoulli variables provide probability estimates for later analyses.The probability mass function has a mode within one of its mean; a summation lemma bounds weighted harmonic terms for nondecreasing sequences.Source: §2.1 · pp. 7–8

2.2 Quantum subroutines

  • Amplitude estimation and fixed-point amplitude amplification provide quantum subroutines, while quantum walks on Johnson graphs support query-cost analyses.The Johnson-graph walk has spectral gap Θ(1/r) for r ≤ N/2 and updates one stored input index per move.Source: §2.2 · p. 9

2.3 Smoothed model and query complexity

  • The discrete smoothed model independently resamples input bits with probability σ and minimizes expected query cost over perturbations of each center, while requiring correctness on every input.At σ = 0 it recovers worst-case expected query complexity; at σ = 1 it gives uniform-average expected cost.Source: §2.3 · pp. 9–10

3 Total function separation

For the total version of Simon’s problem, the paper proves an O(n/σ) smoothed quantum query bound and an exponential quantum–classical separation for inverse-polynomial smoothing. The algorithm uses standard Fourier sampling, with smoothing supplying structure that makes the procedure efficient.

3 Total function separation

  • For σ ≥ Ω(n/N), Q_sm,σ(Simon) = O(n/σ); for σ ≥ 1/poly(n), the smoothed quantum and classical complexities are exponentially separated.Here N = 2^n, and the result concerns the total problem without a promise on the input function.Source: §3 · pp. 10, 11, 14
  • The result reuses the standard hidden-subgroup Fourier-sampling primitive; the paper suggests exploring whether related techniques could yield speedups for non-Abelian groups.The authors describe the non-Abelian possibility as a direction for further exploration.Source: §3 · p. 11
  • The algorithm is correct on every input: a YES instance never yields a full-span sample set, while either branch returns the correct answer on a NO instance.On YES instances, every Fourier sample is orthogonal to a nonzero period, so the samples span a proper subspace.Source: §3 · p. 11
  • Smoothing produces at least Nσ/64 singleton fibers with probability 1 − 2^−Ω(n), enabling Fourier sampling to generate samples that help certify the absence of a hidden period.A singleton fiber yields a uniformly distributed Fourier sample; the algorithm repeats sampling O(n/σ) times before using its exhaustive fallback if needed.Source: §3 · pp. 12–13
  • The O(n/σ)-query Fourier-sampling stage has an exhaustive fallback costing at most N queries, but smoothing makes invoking it exponentially unlikely.The paper bounds the fallback probability by 2^−Cn for some C > 1.Source: §3 · p. 13

4 Characterizing query complexity of symmetric functions

This section characterizes smoothed query complexity for total symmetric Boolean functions using transition cost and weighted influence, connecting worst-case and average-case analyses. Under uniform smoothing, representative thresholds, Majority, and Parity illustrate how transition locations affect complexity and why transition cost alone does not determine smoothed quantum complexity.

4 Characterizing query complexity of symmetric functions

  • For every total symmetric Boolean function, randomized smoothed complexity is eΘ(min{n, transcostσ(f)^2}), while the quantum characterization also accounts for weighted influence.Weighted influence sums transition query costs weighted by the probabilities of reaching adjacent layers; transition cost captures the largest single-transition contribution after accounting for the perturbed weight’s spread.Source: §4 · p. 14, §4.2 · p. 18

4.1 Query complexity at a fixed Hamming weight

  • At each fixed Hamming weight, one algorithm per query model achieves eO of the hardest distinguishing cost across opposite-valued weights, matching the corresponding lower bound up to logarithmic factors.Symmetrization makes expected cost depend only on Hamming weight, and the upper-bound algorithms estimate the weight with increasing precision until the function value is determined.Source: §4.1 · pp. 16, 18

4.2 Averaging over the perturbed weight

  • Averaging fixed-weight costs over the perturbed-weight distribution yields a randomized bound governed by transition cost and a quantum bound that also sums contributions from multiple transitions.The analysis accounts both for the probability of landing beside transitions and for the cost of distinguishing a typical perturbed weight from a weight across a transition.Source: §4.2 · pp. 18, 20

4.3 Examples and comparisons

  • With no perturbation, the characterization recovers quantum complexity eΘ(max_j t_j) and randomized complexity eΘ(n) for nonconstant functions; transition costs range from √n for Or to Θ(n) for several examples.The threshold at √n has transition cost Θ(n^3/4), while thresholds at n/4, Majority, and Parity have transitions of cost Θ(n). At σ = 1, perturbed weights concentrate within O(√n) of n/2, making transition location relative to the mean important.Source: §4.3 · pp. 20–21
  • Or and thresholds at √n and n/4 have transition cost Theta(1) and e^Theta(1) query complexity in both models under smoothing.Their weighted influence is exponentially small; the n/4 threshold has worst-case complexity linear up to logarithmic factors.Source: §4.3 · pp. 21–22
  • For Or, reading coordinates until finding a one or exhausting the input has constant expected cost on a uniform input.Correctness is still required on every input; only expected query cost is averaged over the perturbation.Source: §4.3 · pp. 21–22
  • Majority and Parity both have transition cost Theta(√n), but their weighted influences and smoothed query complexities differ: Majority is e^Theta(√n) quantumly and e^Theta(n) randomized, while Parity remains e^Theta(n) in both.Their weighted influences differ by a factor of √n.Source: §4.3 · pp. 21–22

5 Pattern matching in the smoothed model

This section studies quantum pattern matching under characterwise smoothing, including settings where the pattern is queried or given explicitly. It establishes algorithmic results and a smoothed quantum query lower bound in the regime ρm ≥ Ω(log n).

5.1 Smoothed pattern matching

  • For m = Θ(n), σ ≥ n^-1/2+ε yields n^(1/2−ε+o(1)) quantum queries, while σ = n^-o(1) yields n^o(1), versus the classical average-case bound eΩ(√n).These speedups follow from the smoothed algorithm when ρm = Ω(log n).Source: §5.1 · pp. 23, 25

5.2 Smoothed pattern matching when pattern is known

  • For explicit patterns, the smoothed model fixes the pattern in a matching Yes instance and rerandomizes the rest of the text; the analysis focuses on ρm ≥ c log n.Below this regime, unrerandomized length-m blocks may remain, and the Yes and No instance sets may overlap.Source: §5.2 · p. 25

5.2.1 Randomized query complexity

  • For an explicit pattern with ρm ≥ Ω(log n), randomized query complexity is ˜O(n/(ρm)) and Ω(n/(ρm)).The upper bound samples text positions to eliminate incompatible offsets; the lower bound uses a fixed all-zero pattern and text.Source: §5.2.1 · pp. 26–27

5.2.2 Quantum query complexity

  • For explicit patterns, the quantum construction partitions candidate offsets into blocks and uses Grover-based disagreement tests followed by amplitude amplification to find a match.The block test accepts with certainty when its block contains a match; each successful update eliminates at least half of the remaining candidate strings.Source: §5.2.2 · pp. 27–28
  • When ρm ≥ Ω(log n), Lemma 5.16 establishes a quantum query lower bound for smoothed pattern matching.The supplied theorem statement does not include the bound’s value.Source: §5.2.2 · p. 29
  • The proof partitions the text into length-m blocks and two cells per block, using strings with nonzeros in every cell as no-instances and a zeroed block to form yes-instances.Conditioned on every cell containing a nonzero symbol, the blocks are independent; any run of zeros is then at most m − 2 long.Source: §5.2.2 · pp. 29–30
  • The proof bounds the adversary matrix’s query sensitivity by √(2ρ) at each position and gives norm n/m for the sum of commuting projections.These quantities are used in the distributional adversary argument.Source: §5.2.2 · p. 30

6 Edit distance in the smoothed model

This section develops quantum methods for smoothed edit distance by reducing it to Ulam distance and building Ulam and edit-distance estimation, testing, and approximation algorithms. The methods use collision-estimation and collision-finding tools, substring-overlap handling, multiscale sampling, variable-time approximate counting, and partial alignment.

6 Edit distance in the smoothed model

  • For non-repetitive strings with edit distance R = Ω(n), the quantum Ulam estimator uses eO(n^1/3) queries, improving on the classical eO(√n) scale.The estimator gives a constant-factor approximation; its construction combines quantum gap and product testers with a quantum partial-alignment procedure.Source: §6 · pp. 31–32
  • With overwhelming probability over smoothing, the reduction yields a quantum O(1/σ)-approximation algorithm for edit distance, with an eO(1/σ) approximation loss and query-simulation overhead.The smoothed model perturbs characters independently with probability σ, coupling perturbations for characters matched by a fixed longest common subsequence.Source: §6 · pp. 31–32

6.1 New quantum collision subroutines

  • The collision toolkit progresses from a gap tester to multiplicative and additive collision estimators, and includes enumeration of m collisions in eO(n^2/3(m + 1)^1/3) queries.The gap tester distinguishes at most ℓ1 from at least ℓ2 collisions; the estimators use a known lower bound on the collision count.Source: §6.1 · pp. 33, 35
  • Because the quantum procedures can have highly nonuniform query costs, the algorithms use a variable-time approximate-counting primitive to combine tests efficiently.The Ulam framework also replaces simply Groverizing individual routines with quantum collision estimation, a faster gap tester, and a variable-time quantum product estimator.Source: §6 · pp. 31–32, §6.1 · p. 37
  • Quantum pair finding returns a uniformly random disjoint collision pair, conditioned on success, when a lower bound on the number of pairs is known and the stated size condition holds.The algorithm succeeds with probability at least 2/3; conditioned on returning a pair, each of the L pairs is returned with probability 1/L.Source: §6.1 · p. 39

6.2 Quantum GapUlamTest

  • A quantum local test distinguishes whether prefix-substring symmetric difference exceeds t at some t in [4a] or is at most 0.8t for every such t, using eO(a^1/3) queries.This primitive tests whether a matching pair is significantly misaligned, supporting the multiscale Q-GapUlamTest for distinguishing edit distance at most a from at least b when a < b/512.Source: §6.2 · pp. 40–41

6.3 Quantum Ulam product tester

  • For k non-repetitive string pairs of length at most βR, the quantum Ulam product tester distinguishes whether their total Ulam distance is above R or below R/32768.It combines scale-dependent Q-GapUlamTests using variable-time approximate counting, rather than applying the most expensive test to every pair.Source: §6.3 · pp. 42–43
  • Theorem 6.8 distinguishes the two cases in the Ulam product tester, completing its proof.Source: §6.3 · p. 44

6.4 Quantum algorithms for Ulam distance and smoothed edit distance

  • With probability at least 2/3, partial alignment finds common-LCS matching positions with consecutive gaps at most 2βR, for non-repetitive strings at distance at most R and β = Ω(log^4 n).It tests whether local windows contain sufficiently many collisions before using quantum pair-finding; the analysis makes a sampled collision likely to belong to the fixed LCS.Source: §6.4 · pp. 44–45
  • A bounded-error quantum algorithm outputs a constant-factor approximation to the Ulam distance R = ed(A, B) for non-repetitive strings.The algorithm combines partial alignment, which decomposes the strings into substring pairs, with the quantum product tester.Source: §6.4 · p. 46
  • With overwhelming probability over smoothing, a bounded-error quantum algorithm gives an O(1/σ)-approximation to edit distance on a σ-smoothed instance.The algorithm accesses the smoothed input strings X and Y.Source: §6.4 · p. 47

A.1 Proof of the correctness of Algorithm 2

The proof setup defines blocks and collision-based quantities for non-repetitive strings under the stated parameter conditions.

A.1 Proof of the correctness of Algorithm 2

  • The setup assumes non-repetitive strings A and B of length n, with a dividing n and δ ≤ 1/2.It defines A_k and B_k as length-a windows at the specified offsets.Source: §A.1 · p. 51
  • X is defined as the sum of the sizes of the set differences I_k across all n/a blocks.Each I_k is defined from A_k and B_k in the theorem statement.Source: §A.1 · p. 51
  • Y_δ counts matching-symbol pairs in overlapping blocks that have a prefix mismatch exceeding 2δt for some t ≤ 4a.The matching symbol must lie in A_k ∩ B_k for some block k.Source: §A.1 · p. 51

Proof of the correctness of Algorithm 2.

The proof establishes that Algorithm 2’s estimates of X and Y are accurate enough to distinguish the close and far cases. Its bounds hold jointly with probability at least 1−τ.

Proof of the correctness of Algorithm 2.

A.2 Proof of the correctness of Algorithm 3

The proof shows that Algorithm 3 returns anchors in a fixed longest common subsequence and that its search loops terminate with high probability. The anchors partition the strings into corresponding short substrings.

A.2 Proof of the correctness of Algorithm 3

  • The probability that the i-th returned anchor is bad across O(log R) scales is eO(fi/(βR)).Source: §A.2 · p. 53
  • At each step, the j-loop stops by z=O(max{1,fi}) with high probability because a window containing enough LCS positions passes the density test.At the smallest j with z=2^j≥fi, the proof obtains an estimate of at least 0.88z, exceeding the 0.85z threshold.Source: §A.2 · p. 54
  • With high probability, every returned anchor belongs to a fixed LCS, so the returned matching positions form a subsequence of it.The argument bounds the total failure probability by eO(1/β), small for sufficiently large β=polylog(n).Source: §A.2 · p. 54
  • The procedure uses the same windows as PartialAlign in, and its anchors partition both strings into corresponding substrings of length at most 2βR.Source: §A.2 · p. 54

A.3 Proof of Claim 6.6

The proof analyzes a random subset conditioned on containing a specified number of collision pairs and having a specified size. It reduces the conditioned-on-set case to an equivalent instance with adjusted parameters.

A.3 Proof of Claim 6.6

  • The argument establishes the required probability claim after bounding the conditional size probability and removing the conditioning on I.Source: §A.3 · pp. 54–56
  • Conditioning on I⊆S reduces the problem to non-repetitive strings of length n−1 with the same λ collision pairs, with parameters replaced by n−1, s−2, ρ′, and λρ′.For s≤3, t=1 and the conclusion follows directly because S\I contains at most one index.Source: §A.3 · p. 54
  • A uniformly random size-s subset is obtained by choosing positions independently with probability θ=s/(2n), then conditioning on |R|=s.Source: §A.3 · p. 54
  • The proof compares the probability of the joint event |R|=s and Nλ(R)=t−1 with the probability of Nλ(R)=t−1 under independent sampling.It uses the binomial distribution of Nλ(R) and, conditioned on that count, expresses |R| through independent binomial variables.Source: §A.3 · p. 55

A.4 Multiple-collision search for a fixed matching

This section develops collision enumeration for a fixed input whose collision pairs form a matching. It establishes collision-count probability bounds and describes quantum operations for changing uniform states.

A.4 Multiple-collision search for a fixed matching

  • The collision-enumeration argument applies to a fixed input because it uses only that the collision pairs are disjoint.It includes the quantum states, operations, and error accumulated over repeated measurements.Source: §A.4 · p. 56
  • The initial state |V⟩ costs r queries: prepare a uniform r-subset, then query its positions.Source: §A.4 · p. 57
  • The sizes of the relevant sets depend only on N, q, and r, so they can be computed without queries once those parameters are known.Source: §A.4 · p. 57
  • For a uniformly random r-subset with 2≤r≤N/4, the section analyzes the number of fully contained pairs in a matching.Source: §A.4 · pp. 57–58
  • For a fixed matching, any interval of Θ(√µ) consecutive integers within O(√µ) of µ has probability bounded above and below by positive constants.The bounds continue to hold after previously reported pairs and their positions are deleted.Source: §A.4 · pp. 57, 59

It uses

The procedure uses Johnson-graph quantum walks and reversible collision extraction to enumerate collisions between non-repetitive strings. Repeated extraction and counting yield a high-probability enumeration algorithm with near-linear-in-the-target-count query complexity.

Quantum walk

  • The Johnson-graph reflection is implemented by phase estimation to precision Θ(1/√r), repeated O(log(1/δ)) times, with error at most δ.The zero-phase state is unchanged exactly; every other eigenvector is approximately negated.Source: It uses · p. 60

One extraction

  • Each successful extraction reports a collision pair, deletes its two positions, and leaves the uniform state on the remaining subsets.The recorded pair and common value allow reversible removal without another query.Source: It uses · p. 61

One enumeration round

  • eO(N^2/3 q^1/3) queries suffice to report K distinct collision pairs in one round, with failure probability at most η.Choosing r = ⌈(N^2q)^(1/3)⌉ or r = ⌊N/4⌋ gives the stated asymptotic bound.Source: It uses · pp. 62, 64
  • The extraction interval retains a constant fraction of current subsets after every deletion, supporting repeated extraction throughout a round.The interval remains Θ(√µ) integers within O(√µ) of the updated mean.Source: It uses · p. 63

Full enumeration

  • The algorithm first estimates the collision count, then refines that estimate to recover the exact count m using padded strings.The first estimate bounds the count within constant factors; the second uses relative error 1/(4ḡ), after which rounding and subtracting one gives m.Source: It uses · pp. 64–65
  • For m ≥ 1, enumeration takes O(log(m + 1)) rounds, and all collision pairs are reported with probability at least 1 − τ.Each round removes ⌈qj/32⌉ pairs, and the assigned failure probabilities sum to at most τ.Source: It uses · p. 65

A.5 Reversible access to the implicit Ulam instance

The section makes the implicit Ulam instance accessible to quantum procedures using reversible, subset-indexed databases. This preserves collision relations while increasing input-query complexity by O(L).

Local collision test

  • Reversible local collision testing uses O(L) queries, and the fixed local records let the matching predicate be computed reversibly.The records store O(L)-length neighborhoods around the relevant positions.Source: §A.5 · p. 66

Subset database

  • The database preserves exactly the collisions between selected positions and introduces no additional collisions.Stored labels are distinct on each side, and a shared label holds exactly when the positions match.Source: §A.5 · pp. 67–68
  • A subset database is uniquely determined by its position sets and the strings, so different update orders reaching the same sets yield the same database state.This makes setup and update operations well-defined on superpositions.Source: §A.5 · pp. 67–68

A.5 Reversible access to the implicit Ulam instance

  • The proof of Theorem 6.3 can use quantum queries to the original smoothed strings, with an O(L) multiplicative increase in input-query complexity.The result is conditioned on the high-probability event of Lemma 4.6 of.Source: §A.5 · pp. 68–69

Limitation

  • The overhead concerns input-query complexity; additional reversible elementary-operation costs are not analyzed.Computing all collision relations among local records may require extra operations.Source: §A.5 · p. 69
Loading 2609.35580v1…