{"id":"05187e56-93ff-4203-b0ba-ec69d1a5f603","arxiv_id":"2507.13885","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"A quantum algorithm solves wildcard pattern matching in O~(sqrt(n) sqrt(k)) time when the total number of wildcards k is at least sqrt(n).","lead":"This paper gives a quantum algorithm that finds a pattern in a text even when both may contain wildcard characters, running in O~(sqrt(n) sqrt(k)) time. It is the first quantum speedup for wildcard pattern matching and answers an open question posed by Ramesh and Vinay in 2000.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The algorithm's sublinear runtime and correctness both hinge on Observation 3.1, an external two-range counting oracle whose exact query bound and intermediate-output behavior are not proved or checked in the manuscript.","rationale":"The reader's weakest_assumption identifies the dependence on Observation 3.1, and I agree that this is the most load-bearing concern. The full algorithm--case detection, candidate filtering, and the approximation of k--repeatedly invokes the same two-range classification oracle. If that oracle does not deliver its stated query complexity, the headline O~(sqrt(n) sqrt(k)) bound is not supported: replacing sqrt(alpha/beta) with alpha/beta makes the Case 1 interval search linear at the advertised threshold k = sqrt(n). The manuscript treats Observation 3.1 as a black box from [6] and gives no proof, no statement about the constant factors, and no discussion of the alpha < 2 beta regime that arises in the shifted-sum tests. These are verification gaps, not necessarily fatal errors: quantum counting from [6] is widely believed to give such a two-range classifier, and the alpha < 2 beta case can likely be handled with the same estimator. Still, because the central theorem depends on the exact formulation of an external result, a careful re-derivation is required before the algorithm can be considered fully established. The reader also flags an off-by-one and the unstated d < m restriction in Case 2; those are local and fixable, and they do not affect the asymptotic claim. I therefore find no reason to move the verdict away from CONDITIONAL, and I do not see a different weak assumption that is more central to the main theorem.","tokens_in":6388,"tokens_out":29571,"duration_ms":336291,"concrete_test":"Re-derive Observation 3.1 from the quantum counting theorem of Brassard-Hoyer-Mosca-Tapp: write the explicit decision procedure that estimates the sum with absolute error below beta/2 and compares against the threshold 1.5*beta, then count the required oracle queries. Verify that this gives O(sqrt(alpha/beta)) up to polylog factors for all alpha and beta, including alpha < 2 beta, and that the failure probability can be made n^{-c} for any constant c. If the derivation requires an extra factor or imposes alpha >= 2 beta, the paper must supply a corrected statement or the affected case analysis in Sections 3.1 and 3.2 must be revised.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim collapses if Observation 3.1 is not exactly as stated. The algorithm uses this oracle in three load-bearing places: (i) in Section 3 to decide which case holds, via a Grover search over shifts d with beta = 3k; (ii) in Case 1 to filter candidate starts, using the mismatch-count test with beta = k/4; and (iii) in Section 3.3 to approximate k within a factor of 2. Every runtime bound inherits the O~(sqrt(alpha/beta)) query count. If the correct bound were O~(alpha/beta), the Case 1 interval search would take O~(n^{3/2}/k), which is linear when k = sqrt(n), destroying the sublinear claim. The paper neither proves Observation 3.1 nor addresses arrays of length alpha < 2 beta, a regime that actually occurs in the shifted-sum tests when m-d < 6k. The case split can likely be patched for alpha < 2 beta, but the exact two-range decision with arbitrary output in (beta, 2 beta) and the stated query complexity must be verified against Brassard et al. [6]. The off-by-one search range in Case 2 is real but local; the external oracle is the deeper dependency.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":6579,"tokens_out":15302,"duration_ms":171983,"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":[{"comment":"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":"Section 3, Observation 3.1 and its uses"},{"comment":"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":"Section 3.2, search range in Case 2"},{"comment":"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":"Section 3.3, approximation of k"},{"comment":"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.","section":"Section 3.1, uniqueness claim after Lemma 3.1"}],"minor_comments":[{"comment":"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]).","section":"Section 3.1, interval partition"},{"comment":"For α<2β the second range is empty; the statement of the observation should explicitly cover this edge case, since it occurs in the algorithm.","section":"Observation 3.1"},{"comment":"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.","section":"Footnote 1"},{"comment":"The notation 'n−c' should be typeset as n^{-c}, and the repeated use of '˜O' should be cleaned up for publication.","section":"Throughout"}],"recommendation":"major_revision","confidential_remarks":"The paper's contribution is the case analysis and the reduction to shifted matching, not a fundamentally new quantum primitive. The referees should verify that the main result does not already appear under a different framing in the quantum string algorithms literature (e.g., [15]). The dependence on Observation 3.1 is heavy; if the authors cannot supply a precise statement of that external result, the paper would need to be rejected, but in my judgment the identified issues are local and repairable within the scope of a revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","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.\n\nThe paper is mostly correct. The central lemmas hold and the runtime analysis is straightforward. Two small bugs:\n\n1. 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.\n\n2. 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.\n\nThe 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.\n\nWho 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.","headline":"First sublinear quantum algorithm for wildcard matching, with a clean core and two fixable bugs; worth refereeing.","tokens_in":7154,"tokens_out":10580,"would_cite":true,"duration_ms":110246,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"A quantum algorithm solves wildcard pattern matching in $\\tilde O(\\sqrt{n}\\,\\sqrt{k})$ time with high probability.","keywords":["quantum algorithms","pattern matching","wildcards","sublinear time","Grover search","amplitude amplification","shifted matching array","string algorithms"],"falsifier":"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.","tokens_in":6135,"feed_emoji":"⚛️","tokens_out":12308,"duration_ms":124774,"temperature":0.7,"pith_summary":"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.","feed_headline":"Wildcard pattern matching goes sublinear on quantum computers","feed_subtitle":"With k wildcards total, the search runs in O~(√n√k) time whenever k ≥ √n, answering a 2000 open question.","key_machinery":"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$.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies Observation 3.1, the two-range 0/1 array sum classification routine in $\\tilde O(\\sqrt{\\alpha/\\beta})$; every case test and threshold in the algorithm relies on it.","marker":"[6]"},{"why":"Supplies Grover search and element listing, used to find a shift $d$, to find the unique low-mismatch candidate in Case 1, and to list 1-positions of shifted arrays in Case 2.","marker":"[11]"},{"why":"Gives the sublinear quantum algorithm for classic pattern matching and poses the wildcard sublinear-time question this paper answers.","marker":"[17]"},{"why":"Provides the classical near-linear FFT algorithm for wildcard matching, the baseline the sublinear quantum algorithm improves upon when $k=o(n)$.","marker":"[7]"}],"fun_headline_variants":["Quantum wildcard search hits sublinear time","Sublinear quantum algorithm for wildcard matching","Wildcard matching gets quantum sublinear speedup","Quantum answers wildcard matching open question","√n√k quantum time for wildcard patterns"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Quantum wildcard search hits sublinear time","Sublinear quantum algorithm for wildcard matching","Wildcard matching gets quantum sublinear speedup","Quantum answers wildcard matching open question","√n√k quantum time for wildcard patterns"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00029,"raw_usage":{"total_tokens":1701,"prompt_tokens":955,"completion_tokens":746,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":571,"completion_tokens_details":{"reasoning_tokens":678}},"tokens_in":571,"tokens_out":746,"duration_ms":8363,"temperature":1.0,"reasoning_tokens":678,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T16:20:16.222720+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"A fast quantum mechanical algorithm for database search","cited_arxiv_id":null,"evidence_quote":"Supplies Grover search and element listing, used to find a shift $d$, to find the unique low-mismatch candidate in Case 1, and to list 1-positions of shifted arrays in Case 2."},{"cited_title":"String matching in ˜O(√n + √m) quantum time","cited_arxiv_id":null,"evidence_quote":"Gives the sublinear quantum algorithm for classic pattern matching and poses the wildcard sublinear-time question this paper answers."},{"cited_title":"Simple deterministic wildcard matching","cited_arxiv_id":null,"evidence_quote":"Provides the classical near-linear FFT algorithm for wildcard matching, the baseline the sublinear quantum algorithm improves upon when $k=o(n)$."}],"review_version":1}