Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2511.04669 · Leibniz international proceedings in informatics

Quantum Search With Generalized Wildcards

Arjan Cornelissen, Nikhil S. Mande, Subhasree Patro, Nithish Raja, Swagato Sanyal

quant-phcs.CCSubmitted Nov 6, 2025• Announced Nov 7, 2025• 1 citation
v1 · Nov 6, 2025v2 · Jul 17, 2026
arXivHTMLPDF

Abstract

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.

Related papers

Fast Quantum Algorithms for Learning Linear Threshold Functions

Aleksandrs Krivcenko, Tuyen Nguyen, Ronald de Wolf

Linear threshold functions (LTFs) are $\{-1,1\}$-valued functions $f_{w,θ}(x)=\text{sgn}(\langle w,x\rangle-θ)$, where $w\in\mathbb R^n$ has unit norm, $θ\in\mathbb R$, and $x\in\mathbb R^n$ or $\{-1,1\}^n$. If $θ=0$, the LTF is homogeneous, denoted $f_w=f_{w,0}$. LTFs are fundamental linear classifiers. We give three results: one for general LTFs and two for homogeneous LTFs. (1) With real-domain membership queries evaluating $f_{w,θ}(x)$ at any chosen $x\in\mathbb R^n$, we learn an LTF with classification error at most $\varepsilon$ under the standard Gaussian distribution using $O(\log(n/\varepsilon))$ queries and $\widetilde{O}(n)$ other gates. Classically, $Ω(n\log(1/\varepsilon))$ queries are required, giving an exponential quantum query speedup. (2) A homogeneous LTF $f_w$ over $\{-1,1\}^n$ whose $k$ nonzero weights are equal and positive is Majority on the support of $w$. We identify this hidden support exactly using $O(\log k)$ queries, exponentially improving Belovs' $O(k^{1/4})$ upper bound. Our algorithm uses $O(n\log n\log k)$ gates and has $O(\log n\log k)$ non-oracle depth. Classical algorithms require $Ω(k\log(n/k))$ queries. (3) Suppose a unitary $U$ prepares discretized Gaussian quantum examples, corresponding to $\int_x\sqrt{γ_n(x)}|x\rangle|f_w(x)\rangle\,dx$. This is weaker than membership queries. Using the efficient quantum Hermite transform circuit, we learn homogeneous LTFs with classification error at most $\varepsilon$ under the Gaussian distribution using $O(n^{1/4}/\sqrt{\varepsilon})$ applications of $U$ and $U^\dagger$ and $\widetilde{O}\!(\frac{n^{5/4}}{\sqrt{\varepsilon}}+\frac{n}{\varepsilon^2})$ other gates. Classically, $Ω(n/\varepsilon)$ examples are needed, giving a quartic quantum speedup in $n$. We show that the quantum query complexities in all three cases are optimal by proving matching lower bounds.

quant-pharXiv:2609.40331•Oct 1, 2026•0 citations

Quantum algorithms for search with wildcards and combinatorial group testing

Andris Ambainis, Ashley Montanaro

We consider two combinatorial problems. The first we call ``search with wildcards'': given an unknown $n$-bit string $x$, and the ability to check whether any subset of the bits of $x$ is equal to a provided query string, the goal is to output $x$. We give a nearly optimal $O(\sqrt{n} \log n)$ quantum query algorithm for search with wildcards, beating the classical lower bound of $\Omega(n)$ queries. Rather than using amplitude amplification or a quantum walk, our algorithm is ultimately based on the solution to a state discrimination problem. The second problem we consider is combinatorial group testing, which is the task of identifying a subset of at most $k$ special items out of a set of $n$ items, given the ability to make queries of the form ``does the set $S$ contain any special items?''\ for any subset $S$ of the $n$ items. We give a simple quantum algorithm which uses $O(k)$ queries to solve this problem, as compared with the classical lower bound of $\Omega(k \log(n/k))$ queries.

arXiv:1210.1148•Quantum Information and Computation•May 1, 2014•23 citations

Quantum algorithms and learning theory

Srinivasan Arunachalam

This thesis studies strengths and weaknesses of quantum computers. In the first part we present three contributions to quantum algorithms. 1) consider a search space of N elements. One of these elements is "marked" and our goal is to find this. We describe a quantum algorithm to solve this problem using essentially sqrt{N} queries and other operations, improving over the gate count of Grover's algorithm. 2) We give a succinct characterization of quantum algorithms in terms of polynomials, and develop a new technique for showing upper and lower bounds on quantum query complexity based on this. 3) One generic technique used to compute the minimum of a given function is "gradient descent". We present a quantum gradient-calculation algorithm and a gradient-optimization algorithm that is quadratically faster than classical algorithms. In the second part of this thesis we look at quantum learning theory. 1) We survey quantum learning theory, describing the main results known for three models of learning, using classical as well as quantum data: exact learning from membership queries, the probably approximately correct (PAC) learning model, and the agnostic learning model. 2) We then consider if a quantum learner can PAC-learn a given concept class from fewer quantum examples. We give a negative answer by showing that quantum examples are not more powerful than classical random examples, both for PAC learning and for agnostic learning.

•Apr 25, 2018•1 citation

Quantum Pattern Matching with Wildcards

Masoud Seddighin, Saeed Seddighin

Pattern matching is one of the fundamental problems in Computer Science. Both the classic version of the problem as well as the more sophisticated version where wildcards can also appear in the input can be solved in almost linear time $\tilde O(n)$ using the KMP algorithm and Fast Fourier Transform, respectively. In 2000, Ramesh and Vinay~\cite{ramesh2003string} give a quantum algorithm that solves classic pattern matching in sublinear time and asked whether the wildcard problem can also be solved in sublinear time? In this work, we give a quantum algorithm for pattern matching with wildcards that runs in time $\tilde O(\sqrt{n}\sqrt{k})$ when the number of wildcards is bounded by $k$ for $k \geq \sqrt{n}$. This leads to an algorithm that runs in sublinear time as long as the number of wildcards is sublinear.

arXiv:2507.13885•Jul 18, 2025•0 citations

A quantum algorithm for learning a graph of bounded degree

Asaf Ferber, Liam Hardiman

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(m \log n)$ 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 $\tilde{O}(d^2m^{3/4})$ quantum queries. This gives an upper bound of $\tilde{O}(m^{3/4})$ quantum queries when $G$ is a matching or a Hamiltonian cycle, which is far away from the lower bound of $Ω(\sqrt{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 $\tilde{O}(\sqrt{m})$ quantum queries, matching the theoretical lower bound up to logarithmic factors.

arXiv:2402.18714•Feb 28, 2024•0 citations

Quantum learning and universal quantum matching machine

Masahide Sasaki, A. Carlini

Suppose that three kinds of quantum systems are given in some unknown states $|f{〉}^{\ensuremath{\bigotimes}N},$ $|{g}_{1}{〉}^{\ensuremath{\bigotimes}K},$ and $|{g}_{2}{〉}^{\ensuremath{\bigotimes}K},$ and we want to decide which template state $|{g}_{1}〉$ or $|{g}_{2}〉,$ each representing the feature of the pattern class ${\mathcal{C}}_{1}$ or ${\mathcal{C}}_{2},$ respectively, is closest to the input feature state $|f〉.$ This is an extension of the pattern matching problem into the quantum domain. Assuming that these states are known a priori to belong to a certain parametric family of pure qubit systems, we derive two kinds of matching strategies. The first one is a semiclassical strategy that is obtained by the natural extension of conventional matching strategies and consists of a two-stage procedure: identification (estimation) of the unknown template states to design the classifier (learning process to train the classifier) and classification of the input system into the appropriate pattern class based on the estimated results. The other is a fully quantum strategy without any intermediate measurement, which we might call as the universal quantum matching machine. We present the Bayes optimal solutions for both strategies in the case of $K=1,$ showing that there certainly exists a fully quantum matching procedure that is strictly superior to the straightforward semiclassical extension of the conventional matching strategy based on the learning process.

arXiv:quant-ph/0202173•Physical Review A•Aug 6, 2002•105 citations
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}nx \in \{-1,1\}^nx∈{−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(nlog⁡n)O(\sqrt{n} \log n)O(n​logn) and a near-matching lower bound of Ω(n)Ω(\sqrt{n})Ω(n​). Belovs [Comput.~Comp.'15] subsequently showed a tight O(n)O(\sqrt{n})O(n​) upper bound.
We consider a natural generalization of this problem, parametrized by a subset Q⊆2[n]\cal{Q} \subseteq 2^{[n]}Q⊆2[n], where an algorithm may test whether xS=bx_S = bxS​=b for an arbitrary S∈QS \in \cal{Q}S∈Q and b∈{−1,1}Sb \in \{-1,1\}^Sb∈{−1,1}S of its choice, at unit cost. We show near-tight bounds when Q\cal{Q}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 xxx 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→Rf : \{-1,1\}^n \to \mathbb{R}f:{−1,1}n→R the ratio of the maximum value of fff to the maximum (over T∈QT \in \cal{Q}T∈Q) standard deviation of fff on a subcube whose free variables are exactly TTT.'
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.
Linear threshold functions (LTFs) are {−1,1}\{-1,1\}{−1,1}-valued functions fw,θ(x)=sgn(⟨w,x⟩−θ)f_{w,θ}(x)=\text{sgn}(\langle w,x\rangle-θ)fw,θ​(x)=sgn(⟨w,x⟩−θ), where w∈Rnw\in\mathbb R^nw∈Rn has unit norm, θ∈Rθ\in\mathbb Rθ∈R, and x∈Rnx\in\mathbb R^nx∈Rn or {−1,1}n\{-1,1\}^n{−1,1}n. If θ=0θ=0θ=0, the LTF is homogeneous, denoted fw=fw,0f_w=f_{w,0}fw​=fw,0​. LTFs are fundamental linear classifiers. We give three results: one for general LTFs and two for homogeneous LTFs. (1) With real-domain membership queries evaluating fw,θ(x)f_{w,θ}(x)fw,θ​(x) at any chosen x∈Rnx\in\mathbb R^nx∈Rn, we learn an LTF with classification error at most ε\varepsilonε under the standard Gaussian distribution using O(log⁡(n/ε))O(\log(n/\varepsilon))O(log(n/ε)) queries and O~(n)\widetilde{O}(n)O(n) other gates. Classically, Ω(nlog⁡(1/ε))Ω(n\log(1/\varepsilon))Ω(nlog(1/ε)) queries are required, giving an exponential quantum query speedup. (2) A homogeneous LTF fwf_wfw​ over {−1,1}n\{-1,1\}^n{−1,1}n whose kkk nonzero weights are equal and positive is Majority on the support of www. We identify this hidden support exactly using O(log⁡k)O(\log k)O(logk) queries, exponentially improving Belovs' O(k1/4)O(k^{1/4})O(k1/4) upper bound. Our algorithm uses O(nlog⁡nlog⁡k)O(n\log n\log k)O(nlognlogk) gates and has O(log⁡nlog⁡k)O(\log n\log k)O(lognlogk) non-oracle depth. Classical algorithms require Ω(klog⁡(n/k))Ω(k\log(n/k))Ω(klog(n/k)) queries. (3) Suppose a unitary UUU prepares discretized Gaussian quantum examples, corresponding to ∫xγn(x)∣x⟩∣fw(x)⟩ dx\int_x\sqrt{γ_n(x)}|x\rangle|f_w(x)\rangle\,dx∫x​γn​(x)​∣x⟩∣fw​(x)⟩dx. This is weaker than membership queries. Using the efficient quantum Hermite transform circuit, we learn homogeneous LTFs with classification error at most ε\varepsilonε under the Gaussian distribution using O(n1/4/ε)O(n^{1/4}/\sqrt{\varepsilon})O(n1/4/ε​) applications of UUU and U†U^\daggerU† and O~ ⁣(n5/4ε+nε2)\widetilde{O}\!(\frac{n^{5/4}}{\sqrt{\varepsilon}}+\frac{n}{\varepsilon^2})O(ε​n5/4​+ε2n​) other gates. Classically, Ω(n/ε)Ω(n/\varepsilon)Ω(n/ε) examples are needed, giving a quartic quantum speedup in nnn. We show that the quantum query complexities in all three cases are optimal by proving matching lower bounds.
We consider two combinatorial problems. The first we call ``search with wildcards'': given an unknown nnn-bit string xxx, and the ability to check whether any subset of the bits of xxx is equal to a provided query string, the goal is to output xxx. We give a nearly optimal O(nlog⁡n)O(\sqrt{n} \log n)O(n​logn) quantum query algorithm for search with wildcards, beating the classical lower bound of Ω(n)\Omega(n)Ω(n) queries. Rather than using amplitude amplification or a quantum walk, our algorithm is ultimately based on the solution to a state discrimination problem. The second problem we consider is combinatorial group testing, which is the task of identifying a subset of at most kkk special items out of a set of nnn items, given the ability to make queries of the form ``does the set SSS contain any special items?''\ for any subset SSS of the nnn items. We give a simple quantum algorithm which uses O(k)O(k)O(k) queries to solve this problem, as compared with the classical lower bound of Ω(klog⁡(n/k))\Omega(k \log(n/k))Ω(klog(n/k)) queries.
This thesis studies strengths and weaknesses of quantum computers. In the first part we present three contributions to quantum algorithms. 1) consider a search space of N elements. One of these elements is "marked" and our goal is to find this. We describe a quantum algorithm to solve this problem using essentially sqrt{N} queries and other operations, improving over the gate count of Grover's algorithm. 2) We give a succinct characterization of quantum algorithms in terms of polynomials, and develop a new technique for showing upper and lower bounds on quantum query complexity based on this. 3) One generic technique used to compute the minimum of a given function is "gradient descent". We present a quantum gradient-calculation algorithm and a gradient-optimization algorithm that is quadratically faster than classical algorithms. In the second part of this thesis we look at quantum learning theory. 1) We survey quantum learning theory, describing the main results known for three models of learning, using classical as well as quantum data: exact learning from membership queries, the probably approximately correct (PAC) learning model, and the agnostic learning model. 2) We then consider if a quantum learner can PAC-learn a given concept class from fewer quantum examples. We give a negative answer by showing that quantum examples are not more powerful than classical random examples, both for PAC learning and for agnostic learning.
Pattern matching is one of the fundamental problems in Computer Science. Both the classic version of the problem as well as the more sophisticated version where wildcards can also appear in the input can be solved in almost linear time O~(n)\tilde O(n)O~(n) using the KMP algorithm and Fast Fourier Transform, respectively. In 2000, Ramesh and Vinay~\cite{ramesh2003string} give a quantum algorithm that solves classic pattern matching in sublinear time and asked whether the wildcard problem can also be solved in sublinear time? In this work, we give a quantum algorithm for pattern matching with wildcards that runs in time O~(nk)\tilde O(\sqrt{n}\sqrt{k})O~(n​k​) when the number of wildcards is bounded by kkk for k≥nk \geq \sqrt{n}k≥n​. This leads to an algorithm that runs in sublinear time as long as the number of wildcards is sublinear.
We are presented with a graph, GGG, on nnn vertices with mmm edges whose edge set is unknown. Our goal is to learn the edges of GGG with as few queries to an oracle as possible. When we submit a set SSS of vertices to the oracle, it tells us whether or not SSS induces at least one edge in GGG. 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(mlog⁡n)O(m \log n)O(mlogn) for a general graph GGG with mmm 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 GGG has maximum degree ddd and is O(1)O(1)O(1)-colorable, Montanaro and Shao presented an algorithm that learns the edges of GGG in at most O~(d2m3/4)\tilde{O}(d^2m^{3/4})O~(d2m3/4) quantum queries. This gives an upper bound of O~(m3/4)\tilde{O}(m^{3/4})O~(m3/4) quantum queries when GGG is a matching or a Hamiltonian cycle, which is far away from the lower bound of Ω(m)Ω(\sqrt{m})Ω(m​) queries given by Ambainis and Montanaro. We improve on the work of Montanaro and Shao in the case where GGG has bounded degree. In particular, we present a randomized algorithm that, with high probability, learns cycles and matchings in O~(m)\tilde{O}(\sqrt{m})O~(m​) quantum queries, matching the theoretical lower bound up to logarithmic factors.
Suppose that three kinds of quantum systems are given in some unknown states $|f{〉}^{\ensuremath{\bigotimes}N},$ $|{g}_{1}{〉}^{\ensuremath{\bigotimes}K},$ and $|{g}_{2}{〉}^{\ensuremath{\bigotimes}K},$ and we want to decide which template state ∣g1〉|{g}_{1}〉∣g1​〉 or ∣g2〉,|{g}_{2}〉,∣g2​〉, each representing the feature of the pattern class C1{\mathcal{C}}_{1}C1​ or C2,{\mathcal{C}}_{2},C2​, respectively, is closest to the input feature state ∣f〉.|f〉.∣f〉. This is an extension of the pattern matching problem into the quantum domain. Assuming that these states are known a priori to belong to a certain parametric family of pure qubit systems, we derive two kinds of matching strategies. The first one is a semiclassical strategy that is obtained by the natural extension of conventional matching strategies and consists of a two-stage procedure: identification (estimation) of the unknown template states to design the classifier (learning process to train the classifier) and classification of the input system into the appropriate pattern class based on the estimated results. The other is a fully quantum strategy without any intermediate measurement, which we might call as the universal quantum matching machine. We present the Bayes optimal solutions for both strategies in the case of K=1,K=1,K=1, showing that there certainly exists a fully quantum matching procedure that is strictly superior to the straightforward semiclassical extension of the conventional matching strategy based on the learning process.