Technical Summary: Quantum Search With Generalized Wildcards

Problem Definition

The paper addresses the Quantum Search with Wildcards problem, a generalization of the learning problem introduced by Ambainis and Montanaro [AM14]. The goal is to learn an unknown bit-string $x \in \{-1, 1\}^n$. In the standard model, an algorithm can query any subset of indices $S \subseteq [n]$ to check if the substring $x_S$ equals a chosen string $b \in \{-1, 1\}^S$ at unit cost.

This work generalizes the problem by restricting the allowed query subsets to an arbitrary fixed collection $\mathcal{Q} \subseteq 2^{[n]}$. An algorithm can only test $x_S = b$ if $S \in \mathcal{Q}$. The paper investigates the quantum query complexity of learning $x$ (denoted $Q_{\mathcal{Q}}(\text{rec})$) under various constraints on $\mathcal{Q}$, including:

• Bounded-size sets: $S$ where $|S| \le k$.
• Contiguous blocks: $S = [i, j]$.
• Prefixes: $S = [1, i]$.
• Only the full set: $S = [n]$.

Classically, learning $x$ requires $\Omega(n)$ queries even with wildcards, as each query yields at most 1 bit of information. In the unrestricted quantum setting ($\mathcal{Q} = 2^{[n]}$), Ambainis and Montanaro achieved $O(\sqrt{n} \log n)$, later tightened to $O(\sqrt{n})$ by Belovs [Bel15]. This paper seeks to characterize the complexity for restricted $\mathcal{Q}$.

Methodology

The authors develop a unifying framework based on the negative-weight adversary bound, specifically utilizing its primal formulation (a maximization semidefinite program, SDP).

1. Reduction to Parity

The authors first establish that for downward-closed query sets $\mathcal{Q}$, the complexity of learning the entire string is equivalent (up to constant factors) to computing the parity function $\oplus(x) = \prod x_i$. This allows the problem to be reduced to analyzing $Q_{\mathcal{Q}}(\oplus)$.

2. Symmetry Reduction

Using the primal adversary bound formulation for Boolean functions, the authors apply symmetry reduction. They show that for the parity function, the optimal adversary matrix $\Gamma$ can be assumed to be the communication matrix of an XOR function. That is, $\Gamma[x, y] = f(x \oplus y)$ for some function $f: \{-1, 1\}^n \to \mathbb{R}$. This reduces the optimization over matrices to an optimization over functions.

3. Fourier Analysis

By leveraging the fact that XOR communication matrices are diagonal in the Fourier basis, the authors translate the spectral norm constraints of the adversary bound into analytic properties of the function $f$.

• The numerator of the bound (spectral norm of $\Gamma$) corresponds to the maximum absolute value of $f$ (scaled).
• The denominator (spectral norm of $\Gamma$ restricted by a query) corresponds to the standard deviation of the restriction of $f$ to a subcube defined by the query set.

This leads to a characterization of the query complexity as the solution to an abstract optimization program, $val_{\mathcal{Q}}$.

Key Contributions and Results

1. General Characterization (Theorem 1.1)

The paper proves that the quantum query complexity of computing parity with query set $\mathcal{Q}$ is characterized by:
$$Q_{\mathcal{Q}}(\oplus) = \Theta(val_{\mathcal{Q}})$$
where
$$val_{\mathcal{Q}} := \max_{f \text{ is odd}} \frac{\|f\|_\infty}{\max_{S \in \mathcal{Q}, b} \sqrt{\text{Var}(f_{S|b})}}$$
Here, $f$ is an odd function ($f(x) = -f(-x)$), and $f_{S|b}$ is the restriction of $f$ to the subcube where variables in $\bar{S}$ are fixed to $b$. The complexity is determined by the ratio of the function's maximum value to the maximum standard deviation of its restriction over any valid query subcube.

2. Specific Bounds (Theorem 1.2 & Corollary 1.3)

The framework is applied to derive tight bounds for specific query sets:

• Bounded-size sets ($|S| \le k$):
  The complexity is $\Theta(n/\sqrt{k})$.
  • Significance: When $k=n$, this recovers the optimal $O(\sqrt{n})$ bound for the standard search with wildcards, matching Belovs' result but via a different technique.
• Contiguous blocks:
  The complexity is $\tilde{\Theta}(n)$.
  • Significance: This implies no quantum speedup over classical algorithms in settings like genome sequencing where only contiguous segments are accessible. It recovers a known lower bound of $\Omega(n/\log n)$ [CILG+12, BV23] and establishes a matching upper bound.
• Prefixes:
  The complexity is $\Theta(n)$.
  • Significance: This resolves an open question [XZL23] by proving that recovering a string cannot be done with sublinear prefix queries.
• Only the full set ($S=[n]$):
  The complexity is $\Theta(2^{n/2})$.
  • Significance: This recovers the standard Grover search lower bound $\Omega(\sqrt{N})$ for searching a database of size $N=2^n$.

Significance and Claims

The paper claims several significant contributions:

1. First Use of Primal Adversary for Upper Bounds: The authors state that to their knowledge, this is the first work to use the primal version of the negative-weight adversary bound (typically a lower-bound tool) to prove new quantum query upper bounds without explicitly resorting to SDP duality.
2. Unifying Framework: The work provides a single analytic framework that recovers known tight bounds (e.g., Belovs' $O(\sqrt{n})$) and derives new bounds for generalized settings, replacing complex algorithmic constructions or dual SDP solutions with a combinatorial analysis of real-valued functions on the Boolean hypercube.
3. Biological Relevance: The results are motivated by and applicable to computational biology (e.g., DNA/RNA sequencing), where measurements are often restricted to contiguous substrings. The paper concludes that in these specific restricted models, quantum algorithms do not offer a super-polynomial advantage over classical ones.

The authors note that while their framework yields tight bounds, it does not explicitly construct the quantum algorithms for the upper bounds, unlike the constructive approaches of Ambainis and Montanaro or Belovs. However, they argue that the primal formulation, when combined with symmetry and structural insight, is a practical tool for establishing tight complexity bounds.