{"id":"e5a61c87-82f7-4a31-9990-e246cbdfb531","arxiv_id":"2411.14850","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A quantum algorithm using suffix arrays and quantum longest-common-prefix comparisons solves multiple string matching in O*(n + sqrt(mL)) queries, matching the lower bound up to logs.","lead":"This paper presents a quantum algorithm for finding all occurrences of a dictionary of strings inside a long text, with query complexity O*(n + sqrt(mL)). The result matches the quantum lower bound up to logarithmic factors and speeds up prior classical and quantum approaches for large dictionaries of long words.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"LeftBorderSearch never verifies that the returned suffix starts with the dictionary string, so absent patterns that fall between suffixes produce false occurrence lists.","rationale":"The central claim is Theorem 1: Algorithm 2 solves Multiple String Matching. For that to hold, LeftBorderSearch must return the first suffix prefixed by sj and must signal absence when there is none. The current pseudocode only tests absence at the global extremes; the binary search maintains a lexicographic lower bound, not a prefix-match guarantee. A string can lie between adjacent suffixes without occurring, and the algorithm then reports a false match. The counterexample t='abc', S=('abz') is decisive: even with perfect QLCP and LCPSuf oracles, Algorithm 1 returns 2 and Algorithm 2 outputs a non-empty occurrence list for a string that does not occur. This is a concrete correctness bug rather than a missing proof. The reader's error-composition concern is valid but secondary: even if the [32] claim were resolved, the algorithm still fails on absent strings. The fix appears small (a final prefix check costs O(sqrt(|sj|)) per string and sums to O(sqrt(mL)), preserving the claimed bounds, and the answer=0 off-by-one should be corrected), but as written the main theorem is false. I therefore adjust the verdict from CONDITIONAL to REJECT, while noting that a repaired version may be plausible.","tokens_in":10076,"tokens_out":13992,"duration_ms":146872,"concrete_test":"Run the trace on the exact pseudocode: build the suffix array of t='abc', set S=('abz'), and execute Algorithm 1 with QLCP/LCPSuf as perfect oracles. The trace gives LeftBorderSearch(j)=2 and no -1 sentinel from either border search, so Algorithm 2 populates Ij with a non-empty list. If this reproduces, Theorem 1 as stated is false; a minimal repair is to test LCP(St_lef_tj,sj)=|sj| (and symmetrically for the right border) before outputting Ij.","verdict_should_be":"REJECT","load_bearing_attack":"Algorithm 1's only empty-result tests are against the first and last suffixes of the suffix array. If a dictionary string lies lexicographically between two suffixes but is not a prefix of any suffix, the binary search converges to an insertion position, and Algorithm 2 treats it as a match. Concretely, take t='abc' (suffixes St1='abc', St2='bc', St3='c') and dictionary S=('abz'). With error-free QLCP: Llcp=LCP('abc','abz')=2, Rlcp=LCP('c','abz')=0. In the loop M=2 and LCPSuf(1,2)=0 < Llcp, so Ri becomes 2; the loop exits and LeftBorderSearch returns 2. Since RightBorderSearch also cannot return -1 ('abz' is neither less than St1 nor greater than Stn), Algorithm 2 outputs a non-empty occurrence list for 'abz', although 'abz' does not occur in t. The pseudocode's extra branch 'if Llcp = |sj| then answer=0' is also wrong: when the first suffix already has the pattern as prefix, the left border should be 1, not 0. These failures are independent of the unresolved [32] error-composition step.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a quantum algorithm for the Multiple String Matching Problem: given a text t of length n and a dictionary S of m strings with total length L, it aims to output all occurrences of dictionary strings in t. The algorithm first builds a suffix array and LCP data structure for t; for each dictionary string sj it performs two quantum binary searches (LeftBorderSearch and RightBorderSearch) that use a quantum LCP subroutine QLCP to locate the interval of suffixes having sj as a prefix, and then outputs the corresponding suffix positions. The claimed query complexity is O(n + sqrt(mL log n) + m log n) and the claimed time complexity is O(n + sqrt(mL log n) log b + m log n), with error probability 0.1. The paper also sketches a classical lower bound Omega(n+L) and a quantum lower bound Omega(n+sqrt(mL)).","tokens_in":10321,"tokens_out":9143,"duration_ms":95938,"significance":"If the algorithm were correct, it would be the first quantum multiple-string-matching algorithm with worst-case complexity O^*(n + sqrt(mL)), matching the stated quantum lower bound up to logarithmic factors and providing a genuine speedup for dictionaries with long words. The high-level idea of combining suffix arrays with quantum LCP-based binary search is natural and, if properly repaired, could be a useful contribution. However, as submitted, the correctness of the core search procedure is not established; the manuscript contains a concrete false-positive bug, an incorrect edge-case branch, an unproven error-composition step, and a lower-bound proof with apparent errors. The paper also inherits the positive feature of relying on established building blocks (suffix-array construction, LCP queries, Grover-style first-one search) rather than circular reasoning.","major_comments":[{"comment":"The left-border search does not verify that the suffix returned by the binary search actually has sj as a prefix, so absent dictionary strings can be reported as occurring. Concretely, let t = 'abc', whose suffixes in lexicographic order are ('abc', 'bc', 'c'), and let the dictionary be S = {'abz'}. LeftBorderSearch computes Llcp = QLCP('abc', 'abz') = 2 and Rlcp = QLCP('c', 'abz') = 0. Since 'abz' is neither less than 'abc' nor greater than 'c', both empty-result checks fail. In the single loop iteration, M = 2, Llcp >= Rlcp, and LCPSuf(1,2) = 0 < Llcp, so Ri is set to 2; the loop exits and the procedure returns 2. The analogous RightBorderSearch also cannot return -1 because 'abz' lies lexicographically between St1 and Stn, so Algorithm 2 outputs a non-empty occurrence list for 'abz', although 'abz' is not a substring of the text. This counterexample falsifies the claims of Lemma 5 and Theorem 1 as stated.","section":"Section 3, Algorithm 1 and Lemma 5"},{"comment":"The branch 'if Llcp = |sj| then answer <- 0' is incorrect. If the first suffix St1 already has sj as a prefix, the left border of the interval of suffixes with prefix sj is 1, not 0. For instance, with t = 'abc' and S = {'a'}, Llcp = 1 = |sj|, so the algorithm returns 0; Algorithm 2 would then use suf[0] or produce an invalid occurrence interval, instead of the correct answer Ij = (suf1). This is an independent error in the pseudocode that would need to be fixed even after adding a final prefix-verification step.","section":"Section 3, Algorithm 1"},{"comment":"The error-composition argument is not demonstrated. The proof notes that each QLCP call has error probability 0.1 and that O(log n) or O(m log n) such calls are made, then states 'Due to [32], such sequence can be converted to an algorithm with the same total complexity and error probability 0.1' (similarly in Theorem 1). No explanation is given of how reference [32] implies this for sequences of dependent First-One Search calls where the next call uses the result of the previous one. If this composition property is not valid, the algorithm's error probability would be close to 1, or an extra log(1/epsilon) factor would be needed for amplification, which would weaken the claimed matching of the lower bound. This is load-bearing and requires a formal lemma with proof.","section":"Section 3, proofs of Lemma 5 and Theorem 1"},{"comment":"The quantum lower-bound proof contains an apparent error. The first reduction says that searching for all positions of '1' among n bits has quantum query complexity Omega(sqrt(n t)) by [10], where t is the number of occurrences of 1; the text then says 'In the worst case, it is also Omega(n).' For the cited bound, the worst case over t is t=1, giving Omega(sqrt(n)), not Omega(n). Thus the claimed Omega(n) quantum lower bound is not established by this argument. The sentence in the second reduction that the classical search problem has complexity Omega(n) should presumably read Omega(L). The lower-bound section needs to be rewritten to give a valid proof of the stated bound (for example, by arguing separately about the output size or using an appropriate decision version).","section":"Section 3, Theorem 2"}],"minor_comments":[{"comment":"The three 'if' blocks in Step 7 and Step 8 behave like else-if chains only because the conditions are mutually exclusive; using explicit else-if would make this clearer and avoid confusion when reading the pseudocode.","section":"Algorithm 1, overall structure"},{"comment":"The time-complexity formula contains an undefined symbol d: 'O(n + sqrt(mL log n) log d + m log b)' should be 'O(n + sqrt(mL log n) log b + m log n)' or something explicitly defined.","section":"Theorem 1 proof"},{"comment":"The notation O^* is used in the abstract and introduction without a definition; it should be defined at first use, e.g., as hiding polylogarithmic factors.","section":"Section 1 and abstract"},{"comment":"There are two typos in the lower-bound discussion: 'Ω(n + l)' should be 'Ω(n + L)', and 'the classical query complexity of this problem is Ω(n)' in the second reduction should likely be 'Ω(L)'.","section":"Section 2.1 and Theorem 2"}],"recommendation":"major_revision","confidential_remarks":"The false-positive bug in Algorithm 1 is serious and must be fixed before the paper can be accepted. The fix likely requires a final verification that the returned suffix starts with sj, and the complexity of that verification must be accounted for; it is not present in the current manuscript. The error-composition step via [32] also needs a real proof, and the lower-bound section should be rewritten. If the authors can repair these points within the scope of the paper, the result may be publishable; in its current form, the central correctness claim is not supported."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Kamil and Danil have a genuinely nice idea here: use a suffix array plus the quantum LCP (First-One Search) to locate all occurrences of every dictionary string, and the claimed O(n + sqrt(mL log n) + m log n) query bound is exactly what you'd hope for. The Cauchy-Schwarz aggregation over dictionary lengths is clean, and the construction of the suffix array is standard. The trouble is that the algorithm as written is not correct. LeftBorderSearch (Algorithm 1) never checks that the suffix it lands on actually starts with the dictionary string. Its only empty-result tests are against the first and last suffixes. So a pattern that sits lexicographically between two suffixes but is a prefix of neither falls through. Example: t='abc', S=('abz'). First suffix 'abc' agrees with 'abz' on 'ab'; last suffix 'c' disagrees immediately. The binary search compares LCPSuf(1,2)=LCP('abc','bc')=0 with Llcp=2, decides the right half is useless, sets Ri=2, and returns 2. RightBorderSearch also returns a normal index, so Algorithm 2 reports 'abz' as occurring in 'abc'. It does not. The branch `if Llcp=|sj| then answer<-0` is also wrong; when the first suffix has the pattern as prefix, the left border is 1, not 0. These are not typos—they are load-bearing correctness failures.\n\nThe other soft spot is the error-composition claim. The proof leans on 'due to [32]' for the statement that a sequence of First-One Search calls with total complexity T and per-call error 0.1 can be converted to one algorithm with error 0.1 and same complexity. That is exactly what is needed for the constant-error theorem, and it is asserted, not shown. The lower bound proof is also sketchy and has obvious typos (Omega(n) where Omega(L) is meant in the classical case), though the quantum lower bound Omega(sqrt(mL)) is plausible.\n\nWhat is genuinely new is the combination: prior quantum string matching was single-pattern or worse in m. If the border-search bug is fixed—say, by a final verification that the returned suffixes actually have s_j as a prefix, or by restructuring the binary search to maintain an invariant—the complexity argument probably goes through. So the idea deserves a serious look. But the version on arXiv is not ready. I'd send it to review with a referee instructed to check correctness of the border search and the [32] composition, and I would not cite or build on it until those are fixed.","headline":"Nice idea, broken border search: the algorithm can report non-occurring dictionary strings, and the error-composition step is unproven.","tokens_in":10809,"tokens_out":3265,"would_cite":false,"duration_ms":32984,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q12","68W32"],"pacs":[],"model":"deepseek-v4-flash","headline":"A quantum algorithm for Multiple String Matching reports $O^*(n + \\sqrt{mL})$ query complexity, matching the quantum lower bound up to a log factor.","keywords":["multiple string matching","Aho-Corasick algorithm","quantum query complexity","suffix array","quantum string comparator","Grover search","longest common prefix","search in strings"],"falsifier":"Construct a dictionary and text for which Algorithm 1's QLCP calls are forced to run on adversarially chosen positions, simulate the algorithm, and count oracle queries; if the total exceeds $O(\\sqrt{|s_j|\\log n} + \\log n)$ per word by a logarithmic factor, the sequence-composition claim would be falsified. A more direct check is to exhibit two or three adaptive First-One Search instances, each with error $0.1$, whose composition provably requires an extra logarithmic factor in queries to keep the total error bounded by $1/3$.","tokens_in":9847,"feed_emoji":"⚛️","tokens_out":9691,"duration_ms":106347,"temperature":0.7,"pith_summary":"The paper proposes a quantum algorithm for the Multiple String Matching Problem: given a text of length $n$ and a dictionary of $m$ strings of total length $L$, report every position where any dictionary string occurs in the text. The algorithm claims $O(n + \\sqrt{mL\\log n} + m\\log n)$ query complexity and $O(n + \\sqrt{mL\\log n}\\log b + m\\log n)$ time complexity, where $b$ is the longest dictionary word, both of which are $O^*(n + \\sqrt{mL})$. If the claim holds, this is the first quantum algorithm for the problem with this near-optimal complexity, matching the quantum lower bound up to a log factor and beating the classical $O(n + L)$ bound when a constant fraction of dictionary words are long. The authors describe the method as a quantum analogue of the Aho–Corasick algorithm.","feed_headline":"Quantum search finds every dictionary match in near-optimal time","feed_subtitle":"Matches the quantum lower bound up to a log factor and beats classical Aho-Corasick on long words.","key_machinery":"The machinery is the suffix array of the text together with its LCP array and constant-time longest-common-prefix queries between any two suffixes, plus a quantum LCP procedure $QLCP(u,v)$ built from First-One Search (a Grover-based subroutine) that compares strings in $O(\\sqrt{d})$ queries, where $d$ is the first mismatching position. For each dictionary word, the algorithm runs a binary search over the suffix array, maintaining LCP values with the current left and right border suffixes; the monotonic growth of these LCP values limits the total quantum comparison cost to $O(\\sqrt{|s_j|\\log n})$. This structure is what converts the naive per-word search into a total complexity that is near-linear in $n$ plus a square-root term in $mL$.","core_discovery":"The central claim (Theorem 1) is that a binary search over the text's suffix array, guided by quantum longest-common-prefix (QLCP) comparisons, can locate, for each dictionary word, the full contiguous interval of suffixes that have that word as a prefix. Each left/right border search costs $O(\\sqrt{|s_j|\\log n} + \\log n)$ queries, and summing over $j$ with the Cauchy–Schwarz inequality yields total query complexity $O(n + \\sqrt{mL\\log n} + m\\log n)$, with time complexity carrying one extra $\\log b$ factor from quantum-gate overhead. The paper further proves a quantum lower bound of $\\Omega(n + \\sqrt{mL})$ and concludes that the algorithm reaches it up to a log factor.","pith_inferences":["The same suffix-array-plus-QLCP pattern should generalize to other dictionary problems, such as finding for each text position the longest dictionary word that matches there, with similar $O^*(n + \\sqrt{mL})$ bounds after composing the left and right border searches.","Replacing the per-word loop by a persistent quantum data structure for the dictionary could potentially remove the $m\\log n$ term when $m$ is large, a route the paper does not explore.","Because the lower-bound proof uses only a single dictionary word and a text of zeros, any further speedup would likely have to come from additional structure in the dictionary rather than from the text.","A careful implementation should count actual Grover iterations rather than oracle queries; the extra $\\log b$ factor in time complexity is where gate-level overhead appears in practice."],"forward_implications":["The algorithm matches the stated quantum lower bound $\\Omega(n + \\sqrt{mL})$ up to a logarithmic factor, leaving only a log-factor gap to optimal quantum query complexity for multiple string matching.","For dictionaries where $O(m)$ strings have length $\\omega(\\log n)$, the term $\\sqrt{mL\\log n}$ is $o(L)$ and $m\\log n$ is $o(L)$, so the quantum algorithm beats the classical $O(n + L)$ Aho–Corasick bound.","The algorithm solves the find-all-occurrences version, not merely existence: it returns for every dictionary word the full interval of suffixes that start with that word.","The per-word query cost $O(\\sqrt{|s_j|\\log n} + \\log n)$ means the speedup is most pronounced when the dictionary consists of long patterns.","Any future improvement to the quantum LCP subroutine or to suffix-array range LCP queries would directly tighten the whole algorithm's bound."],"supporting_citations":[{"why":"Supplies the classical Aho–Corasick algorithm with $O(n + L)$ complexity that serves as the baseline and the algorithm the result is described as quantizing.","marker":"[3]"},{"why":"Supplies the suffix-array data structure and the binary-search-over-suffix-array framework that the quantum algorithm adapts.","marker":"[38]"},{"why":"Provides the $O(n)$ suffix-array construction procedure used in the preprocessing step of Algorithm 2.","marker":"[36]"},{"why":"Provides the constant-time longest-common-prefix queries between arbitrary suffixes that let each binary-search step compare suffix LCPs in $O(1)$.","marker":"[9]"},{"why":"Provides the quantum LCP procedure based on First-One Search that gives the $O(\\sqrt{d})$ string comparison used throughout the border searches.","marker":"[18]"},{"why":"Supplies the composition lemma used to convert a sequence of adaptive First-One Search calls into one algorithm with constant error probability and unchanged total complexity.","marker":"[32]"},{"why":"Provides the unstructured-search lower bounds used to prove the classical and quantum lower bounds for the problem.","marker":"[10]"}],"fun_headline_variants":["Quantum string matching achieves near-optimal query bounds","Quantum Aho-Corasick algorithm matches lower bound up to log","Quantum multiple string matching is near-optimal for long words","Quantum search for dictionary matches is near-optimal","Quantum algorithm for string matching approaches quantum lower bound"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that many small quantum searches that depend on each other's answers can be chained together at no extra query cost beyond the sum of their individual costs, while keeping the total error probability at a constant $0.1$; this composition step is asserted via [32] rather than proved in the paper.","fun_headline_variants_meta":{"raw":{"variants":["Quantum string matching achieves near-optimal query bounds","Quantum Aho-Corasick algorithm matches lower bound up to log","Quantum multiple string matching is near-optimal for long words","Quantum search for dictionary matches is near-optimal","Quantum algorithm for string matching approaches quantum lower bound"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000627,"raw_usage":{"total_tokens":2894,"prompt_tokens":936,"completion_tokens":1958,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":552,"completion_tokens_details":{"reasoning_tokens":1881}},"tokens_in":552,"tokens_out":1958,"duration_ms":18511,"temperature":1.0,"reasoning_tokens":1881,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T14:48:43.371578+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Construct a dictionary and text for which Algorithm 1's QLCP calls are forced to run on adversarially chosen positions, simulate the algorithm, and count oracle queries; if the total exceeds $O(\\sqrt{|s_j|\\log n} + \\log n)$ per word by a logarithmic factor, the sequence-composition claim would be falsified. A more direct check is to exhibit two or three adaptive First-One Search instances, each with error $0.1$, whose composition provably requires an extra logarithmic factor in queries to keep the total error bounded by $1/3$.","supporting_citations":[{"cited_title":"In: Proceedings of the First Annual ACM-SIAM Symposium on Discr ete Algorithms","cited_arxiv_id":null,"evidence_quote":"Supplies the suffix-array data structure and the binary-search-over-suffix-array framework that the quantum algorithm adapts."},{"cited_title":"In : String Processing and In- formation Retrieval","cited_arxiv_id":null,"evidence_quote":"Provides the $O(n)$ suffix-array construction procedure used in the preprocessing step of Algorithm 2."},{"cited_title":"In: Latin American Symposium on Theoretical Informatics","cited_arxiv_id":null,"evidence_quote":"Provides the constant-time longest-common-prefix queries between arbitrary suffixes that let each binary-search step compare suffix LCPs in $O(1)$."},{"cited_title":"CEUR Workshop Proceedings 3072, 287–301 (2022)","cited_arxiv_id":null,"evidence_quote":"Provides the quantum LCP procedure based on First-One Search that gives the $O(\\sqrt{d})$ string comparison used throughout the border searches."},{"cited_title":"In: 31st International Symposium on Theoretical Aspects of Computer Science","cited_arxiv_id":null,"evidence_quote":"Supplies the composition lemma used to convert a sequence of adaptive First-One Search calls into one algorithm with constant error probability and unchanged total complexity."},{"cited_title":"SIAM journal on Computing 26(5), 1510–1523 (1997)","cited_arxiv_id":null,"evidence_quote":"Provides the unstructured-search lower bounds used to prove the classical and quantum lower bounds for the problem."}],"review_version":1}