2026-08-25T10:37:44Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27300 2026-08-25T07:42:36Z ddc:004 open_access

Quantum Search with Generalized Wildcards Cornelissen, Arjan Mande, Nikhil S. Patro, Subhasree Raja, Nithish Sanyal, Swagato quantum algorithms quantum query complexity adversary bound symmetry reduction substring queries 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}ⁿ. 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) and a near-matching lower bound of Ω(√n). Belovs [Comput. Comp.'15] subsequently showed a tight O(√n) upper bound. We consider a natural generalization of this problem, parametrized by a subset Q ⊆ 2^{[n]}, where an algorithm may test whether x_S = b for an arbitrary S ∈ Q and b ∈ {-1,1}^S of its choice, at unit cost. We show the following: - For all k ∈ [n], when Q is the collection of all sets of size at most k, the quantum query complexity is Θ(n/√k). In particular when 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 Q is the collection of contiguous blocks, the quantum query complexity is Θ̃(n). - When Q is the collection of prefixes, the quantum query complexity is Θ(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 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}ⁿ → ℝ the ratio of the maximum value of f to the maximum (over T ∈ Q) standard deviation of f on a subcube whose free variables are exactly 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Arjan Cornelissen and Nikhil S. Mande and Subhasree Patro and Nithish Raja and Swagato Sanyal 2026 Is Part Of LIPIcs, Volume 389, 21st Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.TQC.2026.3 urn:nbn:de:0030-drops-273007 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2026.3 eng https://creativecommons.org/licenses/by/4.0/legalcode