In the search with wildcards problem [Ambainis, Montanaro, Quantum Inf.~Comput.'14], one's goal is to learn an unknown bit-string $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(\sqrt{n} \log n)$ and a near-matching lower bound of $Ω(\sqrt{n})$. Belovs [Comput.~Comp.'15] subsequently showed a tight $O(\sqrt{n})$ upper bound.
We consider a natural generalization of this problem, parametrized by a subset $\cal{Q} \subseteq 2^{[n]}$, where an algorithm may test whether $x_S = b$ for an arbitrary $S \in \cal{Q}$ and $b \in \{-1,1\}^S$ of its choice, at unit cost. We show near-tight bounds when $\cal{Q}$ is any of the following collections: bounded-size sets, contiguous blocks, prefixes, and only the full set.
All of these results are derived using a framework that we develop. Using symmetries of the task at hand we show that the quantum query complexity of learning $x$ is characterized, up to a constant factor, by an optimization program, which is succinctly described as follows: `maximize over all odd functions $f : \{-1,1\}^n \to \mathbb{R}$ the ratio of the maximum value of $f$ to the maximum (over $T \in \cal{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.
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. 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(nlogn) 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 xS=b for an arbitrary S∈Q and b∈{−1,1}S of its choice, at unit cost. We show near-tight bounds when Q is any of the following collections: bounded-size sets, contiguous blocks, prefixes, and only the full set.
All of these results are derived using a framework that we develop. Using symmetries of the task at hand we show that the quantum query complexity of learning x is characterized, up to a constant factor, by an optimization program, which is succinctly described as follows: `maximize over all odd functions f:{−1,1}n→R 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.
We are presented with a graph, G, on n vertices with m edges whose edge set is unknown. Our goal is to learn the edges of G with as few queries to an oracle as possible. When we submit a set S of vertices to the oracle, it tells us whether or not S induces at least one edge in G. This so-called OR-query model has been well studied, with Angluin and Chen giving an upper bound on the number of queries needed of O(mlogn) for a general graph G with m edges. When we allow ourselves to make *quantum* queries (we may query subsets in superposition), then we can achieve speedups over the best possible classical algorithms. In the case where G has maximum degree d and is O(1)-colorable, Montanaro and Shao presented an algorithm that learns the edges of G in at most O~(d2m3/4) quantum queries. This gives an upper bound of O~(m3/4) quantum queries when G is a matching or a Hamiltonian cycle, which is far away from the lower bound of Ω(m) queries given by Ambainis and Montanaro. We improve on the work of Montanaro and Shao in the case where G has bounded degree. In particular, we present a randomized algorithm that, with high probability, learns cycles and matchings in O~(m) quantum queries, matching the theoretical lower bound up to logarithmic factors.
Linear threshold functions are fw,θ(x)=sign(⟨x,w⟩−θ), where the weight vector w∈Rn is a unit vector, θ∈R is a threshold, and typically x∈Rn or x∈{−1,1}n. When θ=0, the LTF is called homogeneous, and we write fw:=fw,0. Such functions are among the most important objects in machine learning, since they serve to linearly discriminate positive and negative examples. We give three positive results about learning LTFs:
1. Suppose we can make real-domain queries, meaning we can compute fw,θ(x) at any x∈Rn of our choice. We give a quantum algorithm that learns fw,θ up to Euclidean error ε using O(log(n/ε)) membership queries and O(n) other gates. Then we have also learned fw,θ up to error O(ε) when x is Gaussian. Classical algorithms need Ω(nlog(1/ε)) queries.
2. A homogeneous LTF fw on domain {−1,1}n where w has only k nonzero entries of the same value, is the Majority function on the support of w. Belovs gave a bounded-error quantum algorithm that identifies the hidden support exactly (and hence learns fw) using O(k1/4) queries. We give an exponential improvement, using O(logk) queries.
3. Suppose we have a unitary U that can produce (discretized) quantum examples under Gaussian measure, corresponding to ∫xγn(x)∣x⟩∣fw(x)⟩dx. This is a weaker access model than membership queries. We give a quantum algorithm based on the efficient Hermite transform of Jain et al. to learn homogeneous LTFs fw with error ε under the Gaussian distribution, using O(n1/4/ε) applications of U and U† and O(n2/ε4) other gates.
We consider the quantum query complexity of local search as a function of graph geometry. Given a graph G=(V,E) with n vertices and black box access to a function f:V→R, the goal is find a vertex v that is a local minimum, i.e. with f(v)≤f(u) for all (u,v)∈E, using as few oracle queries as possible. We show that the quantum query complexity of local search on G is Ω(gn43), where g is the vertex congestion of the graph. For a β-expander with maximum degree Δ, this implies a lower bound of $ Ω\bigl(\frac{\sqrtβ \; n^{\frac{1}{4}}}{\sqrtΔ \; \log{n}} \bigr)$. We obtain these bounds by applying the strong weighted adversary method to a construction by Brânzei, Choo, and Recker (2024). As a corollary, on constant degree expanders, we derive a lower bound of Ω(lognn41). This improves upon the best prior quantum lower bound of $Ω\bigl( \frac{n^{\frac{1}{8}}}{\log{n}}\bigr) $ by Santha and Szegedy (2004). In contrast to the classical setting, a gap remains in the quantum case between our lower bound and the best-known upper bound of O(n31) for such graphs.
A degenerate string is a sequence of sets of characters. A generalized degenerate (GD) string extends this notion to the sequence of sets of strings, where strings of the same set are of equal length. Finding an exact match for a pattern string inside a GD string can be done in O(mn+N) time (Ascone et al., WABI 2024), where m is the pattern length, n is the number of strings and N the total length of strings constituting the GD string. This is the best classical algorithm achieved so far, and no matching lower bound, neither unconditional nor conditional, has been shown. We make progress on this problem proposing a quantum algorithm that achieves running time O~(mnN), thus beating the current best classical solution. To the best of our knowledge, this is the first quantum algorithm proposed in the context of GD strings. We present our results starting from the framework of classical parallel computing, which we believe makes them intuitive to understand and possibly easy to generalise to other similar structures.
We study the quantum query complexity of several basic graph problems. 1) We prove a tight Θ(n3/2) bound for finding a maximum-out-degree vertex in an n-vertex tournament, resolving a conjecture of Mande, Paraashar, and Saurabh [FSTTCS'23]. 2) Using the same proof idea, we give a direct proof that finding a maximum-degree vertex in an n-vertex undirected graph requires Θ(n3/2) quantum queries, a bound implicit in the work of Apers and Lee [CCC'21]. Both lower bounds above hold even for computing only the maximum degree or maximum out-degree. 3) We also study Maximum (k,n−k)-Cut, which asks for the largest cut with one side of size k. For every constant k≥1, we give an O(n2−1/(k+1))-query quantum algorithm. 4) We establish a reduction to Maximum (k,n−k)-Cut involving k-Graph Collision, which asks whether the marked vertices of a known graph contain a k-clique. For k≥3, this yields unconditional lower bounds with exponents strictly larger than 3/2, showing that this problem is strictly harder than computing maximum degree. Additionally, under a conjecture we propose for k-Graph Collision, the reduction yields a lower bound matching our upper bound above.
Abstract Collision resistance is one of the most fundamental properties in cryptography. With the development of quantum computing, significant attention has been directed toward understanding the quantum query complexity of collision-finding problems in hash functions. The quantum query complexity of collision-finding in general non-uniform random functions remained an open problem until the recent work of Peng et al. (ASIACRYPT 2025), who nearly resolved it by introducing a novel parameter γ γ . Based on this parameter, they established an upper bound of O(γ1/6) O ( γ 1 / 6 ) and a matching lower bound of Ω~(γ1/6) Ω ~ ( γ 1 / 6 ) . However, the quantum query complexity of finding multi-collisions in non-uniform random functions has remained open. A s -collision to a function f is a set of distinct input x1,…,xs x 1 , ⋯ , x s such that f(x1)=f(x2)⋯=f(xs) f ( x 1 ) = f ( x 2 ) ⋯ = f ( x s ) . In this work, we address this challenge by similarly introducing a new generalized parameter γs γ s . Based on this parameter, we establish nearly tight bounds—an upper bound of O(γs) O ( γ s ) and a lower bound of Ω~(γs) Ω ~ ( γ s ) —thereby nearly resolving this open problem. Moreover, although the existing results for 2-collisions do not generalize straightforwardly to the case of s -collision ( s>2 s > 2 ), we demonstrate that the result of Peng et al. can be viewed as a special case of our more general framework. This clearly establishes our work as a direct generalization of their contribution.