Quantum Pattern Matching with Wildcards

Masoud Seddighin; Saeed Seddighin

REVIEW 4 major objections 4 minor 19 references

Quantum Pattern Matching with Wildcards

T0 review · 4 major / 4 minor · reviewed 2026-08-06 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read A quantum algorithm solves wildcard pattern matching in $\tilde O(\sqrt{n}\,\sqrt{k})$ time with high probability.

desk verdict First sublinear quantum algorithm for wildcard matching, with a clean core and two fixable bugs; worth refereeing. read the letter →

arxiv 2507.13885 v1 pith:VZELCRQQ submitted 2025-07-18 cs.DS

Masoud Seddighin , Saeed Seddighin This is my paper · ORCID

classification cs.DS

keywords quantumalgorithmspatternmatchingwildcardssublineartimeGroversearchamplitudeamplificationshiftedarraystring

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper gives a quantum algorithm that solves pattern matching with wildcards in $\tilde O(\sqrt{n}\,\sqrt{k})$ time with high probability, where $n$ is the text length and $k$ is the total number of wildcards in text and pattern combined. The runtime is sublinear in $n$ whenever $k=o(n)$, which answers a question Ramesh and Vinay raised in 2000 for the wildcard setting. The algorithm is stated for $k\ge\sqrt{n}$; the authors note a padding trick that increases the wildcard count without changing the problem, so the bound also covers smaller wildcard counts. A sympathetic reader should take the contribution as a proof that wildcard matching does not lose the quantum speedup that plain string matching enjoys.

What carries the argument

The central object is the shifted matching array $S(X,d)$: for a string $X$ and a shift $d$, it is the 0/1 array whose $i$-th entry is 0 when positions $i$ and $i+d$ agree and the first is not a wildcard, and 1 otherwise. Its sum, the shifted matching sum, measures how far the string is from being periodic with period $d$, treating wildcards as defects. Around this object the paper builds a two-case decomposition: if every pattern shift has large shifted sum, Lemma 3.1 gives a packing argument that filters candidate positions; if some shift has small shifted sum, Lemmas 3.2 and 3.3 pin any match to a short window near the listed $1$-positions of the text's shifted array. The quadratic speedup comes from Grover search applied at three levels—over shifts, over candidate positions, and over blocks—with Observation 3.1 supplying fast two-range estimates of array sums at thresholds $3k$ and $k/4$.

What would settle it

Take an array with exactly $1.5\beta$ ones and feed it to the two-range oracle from Observation 3.1; the guarantee allows either output, so construct a small family of wildcard instances where the Case 1 filter depends on that middle-range answer and check whether the algorithm still always returns a correct match. If there is an array and threshold for which the arbitrary middle output causes Lemma 3.1's uniqueness argument to misclassify the candidate set, the proof's case analysis fails.

Watch

Extended reading notes

Core claim

The paper's central claim is Theorem 3.4: for pattern matching with wildcards, whenever the total number of wildcards $k$ satisfies $k\ge\sqrt{n}$, there is a quantum algorithm that runs in $\tilde O(\sqrt{n}\,\sqrt{k})$ and succeeds with probability at least $1-n^{-c}$ for any chosen constant $c$. The proof splits every instance into two cases using the shifted matching sum of the pattern. In Case 1, every shift $d<k$ has a large shifted matching sum, and Lemma 3.1 shows that two starting positions closer than $k$ cannot both have fewer than $k/2$ mismatches; Grover search then finds and verifies the unique low-mismatch candidate in each block. In Case 2, some shift $d$ has a small shifted matching sum, and Lemmas 3.2 and 3.3 show that any match can only involve a bounded interval of the text around the listed $1$-positions of the shifted array, reducing the search to a small window. The proof's two assumptions—that $k$ is known and that $n/2<m\le n$—are removed by estimating $k$ and by a Grover search over overlapping text blocks.

Load-bearing premise

The load-bearing premise is that the cited quantum routine of Brassard et al. classifies a 0/1 array of length $\alpha$ in $\tilde O(\sqrt{\alpha/\beta})$ time as having sum at most $\beta$ or at least $2\beta$, with no correctness requirement for sums in between; the paper's case detection, candidate filter, and threshold tests all call this two-range oracle, which is cited rather than proved in the paper.

Editorial extensions

If this is right

For every instance with $k=o(n)$, wildcard pattern matching is solvable in $\tilde O(\sqrt{n}\,\sqrt{k})=o(n)$ quantum time, so the wildcard case retains the sublinear speedup of plain quantum string matching.
When $k=\sqrt{n}$, the runtime is $\tilde O(n^{3/4})$; when $k=n$, it degrades to near-linear, matching the classical FFT baseline up to log factors.
Because $k$ can be estimated within a factor of 2 in $\tilde O(\sqrt{n})$ time, the algorithm does not need to know the wildcard count in advance.
The same bound holds when the pattern is much shorter than the text: splitting the text into overlapping blocks of size $2m$ and running a Grover search over the blocks adds only a $\sqrt{n/m}$ factor, yielding $\tilde O(\sqrt{n}\,\sqrt{k})$ overall.
Success probability can be boosted to any inverse-polynomial failure by the standard repetition argument, matching the usual high-probability guarantee in quantum algorithms.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The two-case decomposition suggests a template for other pattern-matching variants with a support parameter: find a shift whose self-difference is either systematically large or small, then use that as a certificate to filter or localize candidates; applying the same template to mismatch-count or edit-distance thresholds is a natural next step, though the paper does not claim it.
Because the runtime is $\tilde O(\sqrt{n}\,\sqrt{k})$, further improvement would require either a faster way to find a small-shift witness or a direct mismatch-counting routine without the two-range oracle; achieving $\tilde O(\sqrt{n}+\sqrt{k})$ would need a structural lemma beyond Lemma 3.1.
The algorithm's correctness relies on the arbitrary output of Observation 3.1 for sums in the middle range, so a stress test of the subroutine on arrays with sums near $1.5\beta$ would show whether the constant slack in the thresholds $3k$ and $k/4$ is necessary or can be tightened.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

First, the important thing: this is the first sublinear quantum algorithm for wildcard pattern matching, and it answers the Ramesh-Vinay question in the regime k >= sqrt(n), k = o(n). The two-case decomposition with shifted matching arrays is genuinely new—it doesn't reduce to the old Ramesh-Vinay algorithm or to FFT—and the three lemmas are clean. That's real progress.

The paper is mostly correct. The central lemmas hold and the runtime analysis is straightforward. Two small bugs:

1. In Case 2, the search range for the starting index is off by one. The text says "alpha <= i <= beta - m" and also "alpha <= i < beta - m + 1", which are the same set; but the correct upper bound is beta - m + 1. As defined, beta = p - 1 + d, and a valid match at start i needs i <= p - m + d = beta - m + 1. The range as written misses the last valid start. This is a one-character fix.

2. The case detection searches d in [1,k), but S(B,d) is only defined for d < m. When k >= m, the algorithm as written walks off the edge. Since k = o(n) and m >= n/2, the sublinear regime eventually has k < m, so the main claim survives; but the theorem as stated covers all k >= sqrt(n), including k >= m. That needs an explicit caveat or a separate handling of large k.

The stress-test worry about Observation 3.1 is, I think, a miss. The O(sqrt(alpha/beta)) query bound for deciding between [0,beta] and [2beta,alpha] is a standard consequence of amplitude estimation from Brassard et al. [6]; the paper cites it rather than proving it, which is normal for a quantum algorithms paper. The bound is not O(alpha/beta), so the feared collapse to linear runtime doesn't follow. If a referee insists, ask the authors to state the exact version they are relying on, but this is not a load-bearing flaw.

Who is this for: people working in quantum string algorithms and anyone tracking which classical problems get quantum speedups. It's not a broad-impact paper, but it is a clear answer to an open question in a niche. I'd send it to a serious referee. The bugs are local, the core idea is sound, and the result is new and worth having.

Referee Report

4 major / 4 minor

Summary. The paper presents a quantum algorithm for pattern matching when wildcards may appear in both the text and the pattern. For input sizes |A|=n, |B|=m and k total wildcards, the main theorem (Theorem 3.4) claims an O~(√n√k) time algorithm with high probability whenever k≥√n, which is sublinear when k=o(n). The approach splits into two cases via a shifted matching array: if all short shifts of the pattern have large shifted-match sum, a density argument (Lemma 3.1) shows that within any interval of k candidate starting positions there is at most one position with fewer than k/2 mismatches, so Grover search over positions and intervals solves the case; otherwise, a small-shift pattern is used with Lemmas 3.2 and 3.3 to reduce the candidate region and search it by Grover. The algorithm relies throughout on an external observation (Observation 3.1) for classifying 0/1 array sums in two ranges in time O~(√(α/β)). Unknown k is handled by a claimed approximation step, and the assumption n/2<m≤n is removed by splitting the text into overlapping instances.

Significance. If the advertised bound is correct, this would be the first sublinear-time quantum algorithm for wildcard pattern matching and would answer the open question posed by Ramesh and Vinay. The manuscript's internal lemmas (3.1 through 3.3) are clean, the case split is natural, and the paper gives explicit runtime expressions and identifies the parameter regime k≥√n. However, the result is conditional on an unproved two-range sum-classification subroutine from the literature, and several proof details (an off-by-one search range, an asserted but undescribed approximation of k, and a misstatement about uniqueness in Case 1) need correction. With those repairs, the paper would be a solid contribution.

major comments (4)

[Section 3, Observation 3.1 and its uses] The central subroutine is taken from [6] and is used in the case detection (β=3k), in the Case 1 candidate filter (β=k/4), and in Section 3.3. Yet the manuscript neither proves Observation 3.1 nor states the exact theorem in [6] with its success probability and constants. This is load-bearing: the quoted O~(√(α/β)) bound is what makes all runtimes sublinear; if the correct bound were O~(α/β), the Case 1 interval search would become O~(n^{3/2}/k), which is linear at k=√n and would destroy the main claim. The manuscript also applies the observation to arrays of length α<2β (for instance, in the case-detection tests when m-d<6k), a regime in which the second range [2β,α] is empty and the stated behavior needs clarification. Please include a proof or a precise pointer with the exact guarantees from [6].
[Section 3.2, search range in Case 2] With β defined as the last index of A that can participate in a match, the valid starting positions are α≤i≤β-m+1. The text states 'for each index α ≤ i ≤ β − m' and later 'for any α ≤ i < β− m + 1'; both ranges exclude i=β-m+1. A match ending at β is therefore never examined. The ranges should be replaced by α≤i≤β-m+1 (equivalently α≤i<β-m+2).
[Section 3.3, approximation of k] The procedure for approximating k is asserted but not described. The sentence 'we can determine in time O~(√n) via Observation 3.1 a value k′ such that k ≤ k′ ≤ 2k' is not supported by Observation 3.1 as stated, which classifies sums of a given 0/1 array relative to a known threshold and does not by itself estimate the unknown total number of wildcards in two strings. The authors should specify a quantum counting or estimation subroutine, cite it precisely, and prove the O~(√n) bound under the assumption k≥√n.
[Section 3.1, uniqueness claim after Lemma 3.1] The sentence 'We know that the latter is the case for at most one i in range [α,β]' is incorrect if 'latter' refers to 'at least k/2' mismatches; many positions can have at least k/2 mismatches. What Lemma 3.1 bounds is the number of starts with fewer than k/2 mismatches. Because Observation 3.1's 'small' output implies a sum below k/2, the proof can be repaired, but the text as written does not establish the uniqueness needed for the Grover search, and the ambiguous wording should be corrected.

minor comments (4)

[Section 3.1, interval partition] The text divides the interval [0,n-1] into intervals of size at most k; since valid starting positions lie in [0,n-m], the interval should be [0,n-m] (or the intervals should be intersected with [0,n-m]).
[Observation 3.1] For α<2β the second range is empty; the statement of the observation should explicitly cover this edge case, since it occurs in the algorithm.
[Footnote 1] The construction replacing each character by two characters does not in general guarantee that the new number of wildcards is at least √(2n) when the pattern is short (m<√n); the assumption k≥√n remains a genuine restriction and should be stated as such.
[Throughout] The notation 'n−c' should be typeset as n^{-c}, and the repeated use of '˜O' should be cleaned up for publication.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the main theorem is derived from stated combinatorial lemmas and standard external quantum subroutines, with no predicted quantity fitted from the inputs.

full rationale

The paper's derivation chain is self-contained rather than circular. The central claim, Theorem 3.4, follows from Lemma 3.1, Lemma 3.2, and Lemma 3.3, each proved inside the paper from the definitions of matched characters, shifted matching arrays, and the bound k on wildcards. The runtime bounds are built from Grover search and from Observation 3.1, which is explicitly attributed to Brassard et al. [6], an external source independent of the present authors. There is no parameter fitted to the text or pattern, no quantity defined in terms of the target result, and no renamed known pattern presented as a new derivation. The algorithm's correctness does depend on the exact query complexity and two-range output guarantee of Observation 3.1, but dependence on an external, cited subroutine is not circularity; it is a normal technical dependency. The self-citations in the reference list concern related string-algorithm results and are not load-bearing for the main theorem. Thus no circular step is present, and the honest finding is a circularity score of 0.

Assumptions & free parameters 0 free parameters · 3 assumptions · 0 invented entities

No free parameters are fitted to data; the constants 3, 6, and 8 are algorithm design choices. The paper introduces no new particles, forces, or conserved quantities. Its assumptions are standard quantum algorithmic tools and the standard query model.

assumptions (3)

standard math Quantum amplitude amplification and estimation (Brassard et al. 2000) provides Observation 3.1
Used throughout the algorithm to estimate sums of 0/1 arrays in O~(sqrt(alpha/beta)) time with the stated two-range guarantee (Section 3, Observation 3.1).
standard math Grover's algorithm and element listing can find and list marked elements in O~(sqrt(n) sqrt(k)) time
Used for searching over shifts, intervals, and listing S(A,d) ones in Section 3.2.
domain assumption Success probability can be amplified to 1 - n^{-c} for any constant c with only logarithmic overhead
Stated at the start of Section 3 and standard for bounded-error quantum algorithms.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Quantum Pattern Matching with Wildcards." pith.science (2026). https://pith.science/paper/VZELCRQQ

@misc{pith2026250713885,
  author       = {Pith},
  title        = {Pith review of: Quantum Pattern Matching with Wildcards},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/VZELCRQQ}},
  note         = {Machine review of arXiv:2507.13885}
}

abstract

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.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

19 extracted references · 17 canonical work pages

[6]

Quantum amplitude amplifica- tion and estimation

Gilles Brassard, Peter Hoyer, Michele Mosca, and Alain Tapp. Quantum amplitude amplifica- tion and estimation. arXiv preprint quant-ph/0005055, 2000

arXiv 2000
[1]

Pattern Matching with Mismatches and Wildcards

Gabriel Bathie, Panagiotis Charalampopoulos, and Tatiana Starikovskaya. Pattern matching with mismatches and wildcards. arXiv preprint arXiv:2402.07732, 2024. 5

work page Pith review arXiv 2024
[2]

Improved mpc algorithms for edit distance and ulam distance

Mahdi Boroujeni and Saeed Seddighin. Improved mpc algorithms for edit distance and ulam distance. In The 31st ACM Symposium on Parallelism in Algorithms and Architectures, pages 31–40, 2019

work page 2019
[3]

1+ ε approximation of tree edit distance in quadratic time

Mahdi Boroujeni, Mohammad Ghodsi, MohammadTaghi Hajiaghayi, and Saeed Seddighin. 1+ ε approximation of tree edit distance in quadratic time. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 709–720, 2019

work page 2019
[4]

Improved algorithms for edit distance and lcs: beyond worst case

Mahdi Boroujeni, Masoud Seddighin, and Saeed Seddighin. Improved algorithms for edit distance and lcs: beyond worst case. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1601–1620. SIAM, 2020

work page 2020
[5]

Approximating edit distance in truly subquadratic time: Quantum and mapreduce

Mahdi Boroujeni, Soheil Ehsani, Mohammad Ghodsi, MohammadTaghi HajiAghayi, and Saeed Seddighin. Approximating edit distance in truly subquadratic time: Quantum and mapreduce. Journal of the ACM (JACM), 68(3):1–41, 2021

work page 2021
[7]

Simple deterministic wildcard matching

Peter Clifford and Rapha¨ el Clifford. Simple deterministic wildcard matching. Information Processing Letters, 101(2):53–54, 2007

work page 2007
[8]

Pattern matching with don’t cares and few errors

Rapha¨ el Clifford, Klim Efremenko, Ely Porat, and Amir Rothschild. Pattern matching with don’t cares and few errors. Journal of Computer and System Sciences, 76(2):115–124, 2010

work page 2010

Show all 19 references

[9]

A black box for online approximate pattern matching

Rapha¨ el Clifford, Klim Efremenko, Benny Porat, and Ely Porat. A black box for online approximate pattern matching. Information and Computation, 209(4):731–736, 2011

2011
[10]

Introduction to algorithms

Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, and Clifford Stein. Introduction to algorithms. MIT press, 2022

2022
[11]

A fast quantum mechanical algorithm for database search

Lov K Grover. A fast quantum mechanical algorithm for database search. In Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, pages 212–219, 1996

1996
[12]

Ap- proximating lcs in linear time: Beating the barrier

MohammadTaghi Hajiaghayi, Masoud Seddighin, Saeed Seddighin, and Xiaorui Sun. Ap- proximating lcs in linear time: Beating the barrier. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1181–1200. SIAM, 2019

2019
[13]

Massively parallel approx- imation algorithms for edit distance and longest common subsequence

MohammadTaghi Hajiaghayi, Saeed Seddighin, and Xiaorui Sun. Massively parallel approx- imation algorithms for edit distance and longest common subsequence. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1654–1672. SIAM, 2019

2019
[14]

String match- ing with wildcards in the massively parallel computation model

MohammadTaghi Hajiaghayi, Hamed Saleh, Saeed Seddighin, and Xiaorui Sun. String match- ing with wildcards in the massively parallel computation model. In Proceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architectures, pages 275–284, 2021

2021
[15]

Quantum Algorithms For String Problems

Ce Jin. Quantum Algorithms For String Problems. PhD thesis, Massachusetts Institute of Technology, 2022

2022
[16]

Quantum meets fine-grained complexity: Sublinear time quantum algorithms for string problems

Fran¸ cois Le Gall and Saeed Seddighin. Quantum meets fine-grained complexity: Sublinear time quantum algorithms for string problems. Algorithmica, 85(5):1251–1286, 2023. 6

2023
[17]

String matching in ˜O(√n + √m) quantum time

Hariharan Ramesh and V Vinay. String matching in ˜O(√n + √m) quantum time. Journal of Discrete Algorithms, 1(1):103–110, 2003

2003
[18]

Approximation algorithms for lcs and lis with truly improved running times

Aviad Rubinstein, Saeed Seddighin, Zhao Song, and Xiaorui Sun. Approximation algorithms for lcs and lis with truly improved running times. SIAM Journal on Computing, (0):FOCS19– 276, 2023

2023
[19]

3+ ε approximation of tree edit distance in truly subquadratic time

Masoud Seddighin and Saeed Seddighin. 3+ ε approximation of tree edit distance in truly subquadratic time. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022), pages 115–1. Schloss Dagstuhl–Leibniz-Zentrum f¨ ur Informatik, 2022. 7

2022

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.

[1] [6]

Quantum amplitude amplifica- tion and estimation

Gilles Brassard, Peter Hoyer, Michele Mosca, and Alain Tapp. Quantum amplitude amplifica- tion and estimation. arXiv preprint quant-ph/0005055, 2000

arXiv 2000

[2] [1]

Pattern Matching with Mismatches and Wildcards

Gabriel Bathie, Panagiotis Charalampopoulos, and Tatiana Starikovskaya. Pattern matching with mismatches and wildcards. arXiv preprint arXiv:2402.07732, 2024. 5

work page Pith review arXiv 2024

[3] [2]

Improved mpc algorithms for edit distance and ulam distance

Mahdi Boroujeni and Saeed Seddighin. Improved mpc algorithms for edit distance and ulam distance. In The 31st ACM Symposium on Parallelism in Algorithms and Architectures, pages 31–40, 2019

work page 2019

[4] [3]

1+ ε approximation of tree edit distance in quadratic time

Mahdi Boroujeni, Mohammad Ghodsi, MohammadTaghi Hajiaghayi, and Saeed Seddighin. 1+ ε approximation of tree edit distance in quadratic time. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 709–720, 2019

work page 2019

[5] [4]

Improved algorithms for edit distance and lcs: beyond worst case

Mahdi Boroujeni, Masoud Seddighin, and Saeed Seddighin. Improved algorithms for edit distance and lcs: beyond worst case. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1601–1620. SIAM, 2020

work page 2020

[6] [5]

Approximating edit distance in truly subquadratic time: Quantum and mapreduce

Mahdi Boroujeni, Soheil Ehsani, Mohammad Ghodsi, MohammadTaghi HajiAghayi, and Saeed Seddighin. Approximating edit distance in truly subquadratic time: Quantum and mapreduce. Journal of the ACM (JACM), 68(3):1–41, 2021

work page 2021

[7] [7]

Simple deterministic wildcard matching

Peter Clifford and Rapha¨ el Clifford. Simple deterministic wildcard matching. Information Processing Letters, 101(2):53–54, 2007

work page 2007

[8] [8]

Pattern matching with don’t cares and few errors

Rapha¨ el Clifford, Klim Efremenko, Ely Porat, and Amir Rothschild. Pattern matching with don’t cares and few errors. Journal of Computer and System Sciences, 76(2):115–124, 2010

work page 2010