Quantum Search With Generalized Wildcards
Arjan Cornelissen, Nikhil S. Mande, Subhasree Patro, Nithish Raja, Swagato Sanyal · 2025
Read Quantum Search With Generalized Wildcards by Arjan Cornelissen, Nikhil S. Mande, Subhasree Patro, Nithish Raja, Swagato Sanyal (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-04669.txt.
Introduction
Arjan Cornelissen leads five authors generalizing quantum search with wildcards. The original problem hides a bit string that algorithms probe by testing chosen subsets. Earlier quantum methods reached a tight cost near the square root of the length.
The new version limits which subsets may be tested, set by a chosen collection. Costs stay unit per test, whatever subset is picked from the allowed family. The team proves near-tight bounds for several natural collections, including bounded-size subsets. The results show how query limits, not just string size, set the true quantum advantage in such search games.
Catalog record
| CREATOR | Arjan Cornelissen, Nikhil S. Mande, Subhasree Patro, Nithish Raja, Swagato Sanyal |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 112 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2511-04669
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Quantum Search With Generalized Wildcards Arjan Cornelissen, Nikhil S. Mande, Subhasree Patro, Nithish Raja, Swagato Sanyal Abstract In the “search with wildcards” problem [Ambainis, Montanaro, Quantum Inf. Comput.’14], one’s goal is to learn an unknown bit-string x ∈ { − 1 , 1 } n x\in\{-1,1\}^{n} . An algorithm may, at unit cost, test equality of any subset of the hidden string with a string of its choice. Ambainis and Montanaro showed a quantum algorithm of cost O ( n log n ) O(\sqrt{n}\log n) and a near-matching lower bound of Ω ( n ) \Omega(\sqrt{n}) . Belovs [Comput. Comp.’15] subsequently showed a tight O ( n ) O(\sqrt{n}) upper bound. We consider a natural generalization of this problem, parametrized by a subset 𝒬 ⊆ 2 [ n ] \mathcal{Q}\subseteq 2^{[n]} , where an algorithm may test whether x S = b x_{S}=b for an arbitrary S ∈ 𝒬 S\in\mathcal{Q} and b ∈ { − 1 , 1 } S b\in\{-1,1\}^{S} of its choice, at unit cost. We show the following: • For all k ∈ [ n ] k\in[n] , when 𝒬 \mathcal{Q} is the collection of all sets of size at most k k , the quantum query complexity is Θ ( n / k ) \Theta(n/\sqrt{k}) . In particular when k = n k=n , this corresponds to the standard search with wildcards setting. This recovers and generalizes the tight characterization of Belovs, and Ambainis and Montanaro, using completely different techniques. • When 𝒬 \mathcal{Q} is the collection of contiguous blocks, the quantum query complexity is Θ ~ ( n ) \widetilde{\Theta}(n) . • When 𝒬 \mathcal{Q} is the collection of prefixes, the quantum query complexity is Θ ( n ) \Theta(n) . All of these results are derived using a framework that we develop. We apply a symmetry reduction to the primal version of the negative-weight adversary bound, and show that the quantum query complexity of learning x x is characterized, up to a constant factor, by a particular optimization program, which can be succinctly described as follows: ‘maximize over all odd functions f : { − 1 , 1 } n → ℝ f:\{-1,1\}^{n}\to\mathbb{R} the ratio of the maximum value of f f to the maximum (over T ∈ 𝒬 T\in\mathcal{Q} ) standard deviation of f f on a subcube whose free variables are exactly T T .’ To the best of our knowledge, ours is the first work to use the primal version of the negative-weight adversary bound (which is a maximization program typically used to show lower bounds) to show new quantum query upper bounds without explicitly resorting to SDP duality. 1 Introduction Reconstructing an unknown string from limited access to its substrings is a natural and widely studied task across many areas of science and engineering. In computational biology, for example, genome assembly and DNA sequencing rely on reconstructing a long unknown strand from local substring measurements (see, for example, [ SS95 , RSC+10 , CWE15 , LD24 ] and the references therein). Beyond applied motivations, the problem provides a clean and mathematically tractable model for understanding the complexity of learning a hidden string via substring queries. Most relevant to our work is the search with wildcards problem, introduced by Ambainis and Montanaro [ AM14 ] . In this problem, the goal is to learn a hidden bitstring x\in\{-1,1\}^{n} (i.e., an algorithm must correctly output x with high probability) using the minimum number of queries in the following wildcard query model. At unit cost, an algorithm may “check its guess for x ” on any subset of the inputs. Formally, at unit cost, an algorithm may make a query (S,b) where S\subseteq[n],b\in\{-1,1\}^{S} . The query returns 1 if x_{S}=b , and 0 otherwise. Wildcard queries are a generalization of the usual query model, which only allows for |S|=1 . Classically even in the wildcard model every query provides at most 1 bit of information, yielding an information-theoretic lower bound of \Omega(n) for learning x . In the usual quantum query model with |S|=1 , even though roughly a factor-2 speedup is possible [ vD98 ] , this is essentially the best speedup one can get [ FGGS99 ] . Ambainis and Montanaro [ AM14 ] showed that in the wildcard model, quantum algorithms can learn x using only O(\sqrt{n}\log n) queries, exhibiting roughly a quadratic quantum speedup over the classical lower bound. However, their analysis and algorithm crucially rely on the ability to query all subsets of coordinates. In many practical settings, this assumption can be unrealistic. For instance, in de novo genome sequencing and related problems in computational biology [ RSC+10 ] , one has no promise on the input string, and the goal is to reconstruct it. In practical sequencing settings, the accessible measurements are limited to contiguous segments of the underlying strand; one cannot, for instance, simultaneously probe all odd positions at unit cost. Likewise, in more general settings one might be restricted to a fixed family of allowed subsets \mathcal{Q}\subseteq 2^{[n]} , and the structure of \mathcal{Q} can significantly affect the power of the algorithm. In this work, we study the quantum query complexities of learning an unknown string when the allowed query subsets are drawn from an arbitrary fixed collection \mathcal{Q} . This unifies previously studied models, including the standard query model \mathcal{Q}=\left\{\left\{i\right\}:i\in[n]\right\} , and the search-with-wildcards model \mathcal{Q}=2^{[n]} under a single framework. 1.1 Our Results We refer the reader to Section 2 for formal definitions. We summarize here the notions that we need to state our main results. For an arbitrary collection of sets \mathcal{Q}\subseteq 2^{[n]} and a function F:\{-1,1\}^{n}\to E , let \mathsf{Q}^{\mathcal{Q}}(F) denote the quantum query query complexity of computing F , where an algorithm can make unit-cost queries of the form \mathbb{I}[x_{S}=b_{S}] for an arbitrary S\in\mathcal{Q} and b\in\{-1,1\}^{S} of its choice. We call \mathsf{Q}^{\mathcal{Q}}(F) the quantum \mathcal{Q} -substring query complexity of F . Let \oplus(\cdot) denote the parity function, i.e., \oplus(x)=\prod_{i=1}^{n}x_{i} for x\in\{-1,1\}^{n} . A function f:\{-1,1\}^{n}\to\mathbb{R} is said to be odd if f(x)=-f(-x) for all x\in\{-1,1\}^{n} . We write \mathbf{Var}(f):=\mathbf{Var}_{\mathbf{x}\sim\{-1,1\}^{n}}[f(\mathbf{x})] for the variance of the random variable f(\mathbf{x}) , where \mathbf{x} is sampled uniformly at random from \{-1,1\}^{n} . Our main technical contribution is to show that the quantum \mathcal{Q} -substring query complexity of parity is characterized by the optimal value of an abstract analytic optimization program. Below, f_{S|b} refers to the function f restricted to the bits in \bar{S} set to b . Theorem 1.1 . Let n be a positive integer and \mathcal{Q}\subseteq 2^{[n]} . Then \mathsf{Q}^{\mathcal{Q}}(\oplus)=\Theta(\mathsf{val}_{\mathcal{Q}}) , where \mathsf{val}_{\mathcal{Q}}:=\left(\max_{\begin{subarray}{c}f:\{-1,1\}^{n}\to\mathbb{R}\\ f\textnormal{ is an odd function}\end{subarray}}\frac{\|f\|_{\infty}}{\max\limits_{\begin{subarray}{c}S\in\mathcal{Q},\\ b\in\{-1,1\}^{\bar{S}}\end{subarray}}\sqrt{\mathbf{Var}(f_{S|b})}}\right). (1) In other words, this characterization can concisely be stated as: \mathsf{Q}^{\mathcal{Q}}(\oplus) is asymptotically equal to the maximum, over all odd functions f:\{-1,1\}^{n}\to\mathbb{R} , of the ratio of \|f\|_{\infty} to the largest standard deviation of f in a subcube whose free variables are a valid query set. In order to show this, we use the characterization of quantum query complexity by the negative-weight adversary bound [ HLŠ07 , Rei11 ] . We show that for all \mathcal{Q} , the corresponding adversary bound equals \mathsf{val}_{\mathcal{Q}} as defined above. We next analyze \mathsf{val}_{\mathcal{Q}} , as defined in Equation