Quantum Algorithm for the Multiple String Matching Problem

Danil Serov; Kamil Khadiev

REVIEW 4 major objections 4 minor 43 references

Quantum Algorithm for the Multiple String Matching Problem

T0 review · 4 major / 4 minor · reviewed 2026-08-12 · 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 for Multiple String Matching reports $O^*(n + \sqrt{mL})$ query complexity, matching the quantum lower bound up to a log factor.

desk verdict Nice idea, broken border search: the algorithm can report non-occurring dictionary strings, and the error-composition step is unproven. read the letter →

arxiv 2411.14850 v1 pith:D2CRA76R submitted 2024-11-22 quant-ph cs.DS

Kamil Khadiev , Danil Serov This is my paper · ORCID

classification quant-phcs.DS MSC 68Q1268W32

keywords multiplestringmatchingAho-CorasickalgorithmquantumquerycomplexitysuffixarraycomparatorGroversearchlongestcommonprefixinstrings

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

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.

What carries the argument

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$.

What would settle it

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$.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

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.

Reading between the lines

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

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.

Share X Bluesky LinkedIn Reddit HN

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

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.

The 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.

What 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.

Referee Report

4 major / 4 minor

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)).

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 (4)

[Section 3, Algorithm 1 and Lemma 5] 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 3, Algorithm 1] 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 3, proofs of Lemma 5 and Theorem 1] 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 3, Theorem 2] 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).

minor comments (4)

[Algorithm 1, overall structure] 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.
[Theorem 1 proof] 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 1 and abstract] 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 2.1 and Theorem 2] 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)'.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the algorithm is a composition of independent suffix-array, LCP-array, and quantum-LCP subroutines; no claimed prediction reduces to a fitted input or to the paper's own definitions.

full rationale

Walking the derivation chain, the central query bound O(n + sqrt(mL log n) + m log n) is obtained by (i) constructing a suffix array and LCP preprocessing with the external linear-time results in Lemmas 1-3; (ii) invoking the quantum LCP subroutine QLCP whose O(sqrt(d)) complexity is stated in Lemma 4 and credited to Kapralov et al. [18], with the same procedure also attributed to independently developed string comparators [8,20,24]; and (iii) applying a logarithmic number of binary-search steps per dictionary string plus Cauchy-Schwarz summation over the m strings. None of these ingredients is fitted to the paper's target data or defined in terms of the final occurrence lists. In particular, LeftBorderSearch and RightBorderSearch compute suffix-array borders with QLCP calls; the output Ij is not treated as a prediction of a fitted model. Although several references are authored or co-authored by Khadiev, the load-bearing QLCP and suffix-array lemmas are parameter-free external results with stated assumptions, not self-referential uniqueness claims, so they do not make the derivation circular. The assertion that a sequence of QLCP calls can be composed with error 0.1 via Kothari [32] is an unproved-in-this-paper correctness/composition step, but it is an appeal to an external theorem, not a definitional identification of the conclusion with the premise. The manuscript also omits a full correctness proof of the border-search procedure, and the reviewer's example suggests a possible bug (never verifying that a dictionary string is a prefix of the returned suffix); however, an omitted proof or implementation bug is a correctness risk, not a circularity pattern. No self-definitional, fitted-input, renaming, or imported-uniqueness step is present, so the honest circularity score is 0.

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

The algorithm relies on standard suffix array/LCP preprocessing (Lemmas 1-3) and on the quantum LCP subroutine (Lemma 4). The only non-standard assumption is the error-composition claim needed to keep the total error at 0.1 without extra overhead.

assumptions (4)

standard math Suffix array and LCP array for a string can be constructed in O(|u|) time and query complexity (Lemmas 1,2).
Standard string data structure results, cited and used in Algorithm 2.
standard math LCP of any two suffixes can be computed in O(1) after linear preprocessing (Lemma 3).
Standard RMQ-based LCP query, used in binary search steps.
domain assumption Quantum LCP QLCP(u,v) has query complexity O(sqrt(d)) where d is the first mismatch, with error 0.1 (Lemma 4).
This is a core subroutine based on First-One Search; it is cited from prior work [18,20,24] and assumed correct.
ad hoc to paper A sequence of dependent First-One Search calls with each error 0.1 can be converted to an algorithm with error 0.1 and the same total complexity (due to [32]).
This is asserted in Lemma 5 and Theorem 1 proofs but not derived. It is load-bearing for the claimed error probability and complexity.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Quantum Algorithm for the Multiple String Matching Problem." pith.science (2026). https://pith.science/paper/D2CRA76R

@misc{pith2026241114850,
  author       = {Pith},
  title        = {Pith review of: Quantum Algorithm for the Multiple String Matching Problem},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/D2CRA76R}},
  note         = {Machine review of arXiv:2411.14850}
}

abstract

Let us consider the Multiple String Matching Problem. In this problem, we consider a long string, denoted by $t$, of length $n$. This string is referred to as a text. We also consider a sequence of $m$ strings, denoted by $S$, which we refer to as a dictionary. The total length of all strings from the dictionary is represented by the variable L. The objective is to identify all instances of strings from the dictionary within the text. The standard classical solution to this problem is Aho-Corasick Algorithm that has $O(n+L)$ query and time complexity. At the same time, the classical lower bound for the problem is the same $\Omega(n+L)$. We propose a quantum algorithm with $O(n+\sqrt{mL\log n}+m\log n)$ query complexity and $O(n+\sqrt{mL\log n}\log b+m\log n)=O^*(n+\sqrt{mL})$ time complexity, where $b$ is the maximal length of strings from the dictionary. This improvement is particularly significant in the case of dictionaries comprising long words. Our algorithm's complexity is equal to the quantum lower bound $O(n + \sqrt{mL})$, up to a log factor. In some sense, our algorithm can be viewed as a quantum analogue of the Aho-Corasick algorithm.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

43 extracted references · 41 canonical work pages

[32]

In: 31st International Symposium on Theoretical Aspects of Computer Science

Kothari, R.: An optimal quantum algorithm for the oracle identiﬁcation problem. In: 31st International Symposium on Theoretical Aspects of Computer Science. pp. 482–493 (2014)

work page 2014
[10]

SIAM journal on Computing 26(5), 1510–1523 (1997)

Bennett, C.H., Bernstein, E., Brassard, G., Vazirani, U .: Strengths and weaknesses of quantum computing. SIAM journal on Computing 26(5), 1510–1523 (1997)

work page 1997
[1]

Big Data Mining and Analytics 3(1), 41–55 (2019)

Ablayev, F., Ablayev, M., Huang, J.Z., Khadiev, K., Salik hova, N., Wu, D.: On quantum methods for machine learning problems part i: Quant um tools. Big Data Mining and Analytics 3(1), 41–55 (2019)

work page 2019
[2]

In: Mesh Methods for Boundary -Value Problems and Applications

Ablayev, F., Ablayev, M., Khadiev, K., Salihova, N., Vasi liev, A.: Quantum algo- rithms for string processing. In: Mesh Methods for Boundary -Value Problems and Applications. Lecture Notes in Computational Science and E ngineering, vol. 141 (2022)

work page 2022
[3]

Aho, A.V., Corasick, M.J.: Eﬃcient string matching: an ai d to bibliographic search. Commun. ACM 18(6), 333–340 (1975). https://doi.org/10.1145/360825.360855

arXiv 1975
[4]

In: Proceedings of the 2022 Annual ACM-SIAM Symposium on Discre te Algorithms (SODA)

Akmal, S., Jin, C.: Near-optimal quantum algorithms for s tring problems. In: Proceedings of the 2022 Annual ACM-SIAM Symposium on Discre te Algorithms (SODA). pp. 2791–2832. SIAM (2022)

work page 2022
[5]

Allauzen, C., Crochemore, M., Raﬃnot, M.: Factor oracle: A new structure for pattern matching. In: SOFSEM’99: Theory and Practice of Inf ormatics: 26th Con- ference on Current Trends in Theory and Practice of Informat ics Milovy, Czech Quantum Algorithm for the Multiple String Matching Problem 11 Republic, November 27—December 4, 1999 Proceedings 26. pp. ...

work page 1999
[6]

In: Proc

Ambainis, A.: Understanding quantum algorithms via quer y complexity. In: Proc. Int. Conf. of Math. 2018. vol. 4, pp. 3283–3304 (2018)

work page 2018

Show all 43 references

[7]

Quantum Information and Computation 17(3&4), 251–261 (2017)

Arunachalam, S., de Wolf, R.: Optimizing the number of gat es in quantum search. Quantum Information and Computation 17(3&4), 251–261 (2017)

2017
[8]

In: 2017 IEEE Computer So ciety Annual Symposium on VLSI (ISVLSI)

Babu, H.M.H., Jamal, L., Dibbo, S.V., Biswas, A.K.: Area a nd delay eﬃcient design of a quantum bit string comparator. In: 2017 IEEE Computer So ciety Annual Symposium on VLSI (ISVLSI). pp. 51–56. IEEE (2017)

2017
[9]

In: Latin American Symposium on Theoretical Informatics

Bender, M.A., Farach-Colton, M.: The lca problem revisit ed. In: Latin American Symposium on Theoretical Informatics. pp. 88–94. Springer (2000)

2000
[11]

Fortschritte der Physik 46(4-5), 493–505 (1998)

Boyer, M., Brassard, G., Høyer, P., Tapp, A.: Tight bound s on quantum searching. Fortschritte der Physik 46(4-5), 493–505 (1998)

1998
[12]

In: In- ternational colloquium on automata, languages, and progra mming

Commentz-Walter, B.: A string matching algorithm fast o n the average. In: In- ternational colloquium on automata, languages, and progra mming. pp. 118–132. Springer (1979)

1979
[13]

McGraw-Hill (2001)

Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms. McGraw-Hill (2001)

2001
[14]

SIAM Journal on Computing 35(6), 1310–1328 (2006)

Dürr, C., Heiligman, M., Høyer, P., Mhalla, M.: Quantum q uery complexity of some graph problems. SIAM Journal on Computing 35(6), 1310–1328 (2006)

2006
[15]

In: Pro- ceedings of the twenty-eighth annual ACM symposium on Theor y of computing

Grover, L.K.: A fast quantum mechanical algorithm for da tabase search. In: Pro- ceedings of the twenty-eighth annual ACM symposium on Theor y of computing. pp. 212–219. ACM (1996)

1996
[16]

Physical Review A 66(5), 052314 (2002)

Grover, L.K.: Trade-oﬀs in the quantum search algorithm . Physical Review A 66(5), 052314 (2002)

2002
[17]

Jordan, S.: Quantum algorithms zoo (2023), http://quan tumalgorithmzoo.org/

2023
[18]

CEUR Workshop Proceedings 3072, 287–301 (2022)

Kapralov, R., Khadiev, K., Mokut, J., Shen, Y., Yagafaro v, M.: Fast classical and quantum algorithms for online k-server problem on trees . CEUR Workshop Proceedings 3072, 287–301 (2022)

2022
[19]

Lecture Notes in Computer Science, volume=2089, pages=0181–0181, year=2001, publisher=Springer-Verlag GmbH

Kasai, T., Lee, G., Arimura, H., Arikawa, S., Park, K.: Li near-time longest- common-preﬁx computation in suﬃx arrays and its applicatio ns. Lecture Notes in Computer Science, volume=2089, pages=0181–0181, year=2001, publisher=Springer-Verlag GmbH

2001
[20]

In: Interna- tional Conference on Theory and Practice of Natural Computi ng

Khadiev, K., Ilikaev, A.: Quantum algorithms for the mos t frequently string search, intersection of two string sequences and sorting of strings problems. In: Interna- tional Conference on Theory and Practice of Natural Computi ng. pp. 234–245 (2019)

2019
[21]

arXiv preprint arXiv:2212.14205 (2022)

Khadiev, K.: Lecture notes on quantum algorithms. arXiv preprint arXiv:2212.14205 (2022)

2022 arXiv
[22]

Quantum Information and Computation 24(3-4), 267–294 (2024)

Khadiev, K., Bosch-Machado, C.M., Chen, Z., Wu, J.: Quan tum algorithms for the shortest common superstring and text assembling problems. Quantum Information and Computation 24(3-4), 267–294 (2024)

2024
[23]

In: International Co nference on Micro- and Nano-Electronics 2021

Khadiev, K., Enikeeva, S.: Quantum version of self-bala nced binary search tree with strings as keys and applications. In: International Co nference on Micro- and Nano-Electronics 2021. vol. 12157, pp. 587 – 594. Internati onal Society for Optics and Photonics, SPIE (2022). ht...

2022 doi
[24]

Mathematics 10(3), 377 (2022) 12 K

Khadiev, K., Ilikaev, A., Vihrovs, J.: Quantum algorith ms for some strings prob- lems based on quantum string comparator. Mathematics 10(3), 377 (2022) 12 K. Khadiev and D. Serov

2022
[25]

In: Unconventional Computation and Natu ral Computation

Khadiev, K., Kravchenko, D.: Quantum algorithm for dyck language with multiple types of brackets. In: Unconventional Computation and Natu ral Computation. pp. 68–83 (2021)

2021
[26]

In: International Conference on Micro- and Nano-E lectronics 2021

Khadiev, K., Machado, C.M.B.: Quantum algorithm for the shortest superstring problem. In: International Conference on Micro- and Nano-E lectronics 2021. vol. 12157, pp. 579 – 586. International Society for Optics and Ph otonics, SPIE (2022). https://doi.org/10.1117/12.2624618

2022 doi
[27]

NONLINEAR PHENOMENA IN COMPLEX SYST EMS 24(3), 207–221 (2021)

Khadiev, K., Remidovskii, V.: Classical and quantum alg orithms for assembling a text from a dictionary. NONLINEAR PHENOMENA IN COMPLEX SYST EMS 24(3), 207–221 (2021)

2021
[28]

Natural Computing 20(4), 713–724 (2021)

Khadiev, K., Remidovskii, V.: Classical and quantum alg orithms for constructing text from dictionary problem. Natural Computing 20(4), 713–724 (2021)

2021
[29]

Mathematics 11(22), 4707 (2023)

Khadiev, K., Savelyev, N., Ziatdinov, M., Melnikov, D.: Noisy tree data structures and quantum applications. Mathematics 11(22), 4707 (2023)

2023
[30]

In: International Confer ence on Unconventional Computation and Natural Computation

Khadiev, K., Serov, D.: Quantum property testing algori thm for the concatena- tion of two palindromes language. In: International Confer ence on Unconventional Computation and Natural Computation. pp. 134–147. Springe r (2024)

2024
[31]

SIAM journal on computing 6(2), 323–350 (1977)

Knuth, D.E., Morris, Jr, J.H., Pratt, V.R.: Fast pattern matching in strings. SIAM journal on computing 6(2), 323–350 (1977)

1977
[33]

In: Combinatorial Pattern Matching: 12th Annual Symposium, CP M 2001 Jerusalem, Israel, July 1–4, 2001 Proceedings 12

Landau, G.M., Kasai, T., Lee, G., Arimura, H., Arikawa, S ., Park, K.: Linear- time longest-common-preﬁx computation in suﬃx arrays and i ts applications. In: Combinatorial Pattern Matching: 12th Annual Symposium, CP M 2001 Jerusalem, Israel, July 1–4, 2001 Proceedings 12. pp....

2001
[34]

Algorithmica pp

Le Gall, F., Seddighin, S.: Quantum meets ﬁne-grained co mplexity: Sublinear time quantum algorithms for string problems. Algorithmica pp. 1 –36 (2022)

2022
[35]

In: 13th Innovatio ns in Theoretical Com- puter Science Conference (ITCS 2022)

Le Gall, F., Seddighin, S.: Quantum meets ﬁne-grained co mplexity: Sublinear time quantum algorithms for string problems. In: 13th Innovatio ns in Theoretical Com- puter Science Conference (ITCS 2022). Schloss Dagstuhl-Le ibniz-Zentrum für In- formatik (2022)

2022
[36]

In : String Processing and In- formation Retrieval

Li, Z., Li, J., Huo, H.: Optimal in-place suﬃx sorting. In : String Processing and In- formation Retrieval. pp. 268–284. Springer International Publishing, Cham (2018)

2018
[37]

Theory of Computing 12(18), 1–35 (2016)

Lin, C.Y.Y., Lin, H.H.: Upper bounds on quantum query com plexity inspired by the elitzur–vaidman bomb tester. Theory of Computing 12(18), 1–35 (2016)

2016
[38]

In: Proceedings of the First Annual ACM-SIAM Symposium on Discr ete Algorithms

Manber, U., Myers, G.: Suﬃx arrays: A new method for on-li ne string searches. In: Proceedings of the First Annual ACM-SIAM Symposium on Discr ete Algorithms. p. 319–327. SODA ’90, Society for Industrial and Applied Mat hematics (1990)

1990
[39]

Algorithmica 77(1), 16–39 (2017)

Montanaro, A.: Quantum pattern matching fast on average . Algorithmica 77(1), 16–39 (2017)

2017
[40]

Cambridge univ

Nielsen, M.A., Chuang, I.L.: Quantum computation and qu antum information. Cambridge univ. press (2010)

2010
[41]

Journal of Discrete Algorithms 1(1), 103–110 (2003)

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

2003
[42]

University of Amsterdam (2001)

de Wolf, R.: Quantum computing and communication comple xity. University of Amsterdam (2001)

2001
[43]

Wu, S., Manber, U.: A fast algorithm for multi-pattern se arching. Tech. Rep. TR- 94-17, Department of Computer Science, University of Arizo na, Tucson, AZ (1994)

1994

Pith tools

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

[1] [32]

In: 31st International Symposium on Theoretical Aspects of Computer Science

Kothari, R.: An optimal quantum algorithm for the oracle identiﬁcation problem. In: 31st International Symposium on Theoretical Aspects of Computer Science. pp. 482–493 (2014)

work page 2014

[2] [10]

SIAM journal on Computing 26(5), 1510–1523 (1997)

Bennett, C.H., Bernstein, E., Brassard, G., Vazirani, U .: Strengths and weaknesses of quantum computing. SIAM journal on Computing 26(5), 1510–1523 (1997)

work page 1997

[3] [1]

Big Data Mining and Analytics 3(1), 41–55 (2019)

Ablayev, F., Ablayev, M., Huang, J.Z., Khadiev, K., Salik hova, N., Wu, D.: On quantum methods for machine learning problems part i: Quant um tools. Big Data Mining and Analytics 3(1), 41–55 (2019)

work page 2019

[4] [2]

In: Mesh Methods for Boundary -Value Problems and Applications

Ablayev, F., Ablayev, M., Khadiev, K., Salihova, N., Vasi liev, A.: Quantum algo- rithms for string processing. In: Mesh Methods for Boundary -Value Problems and Applications. Lecture Notes in Computational Science and E ngineering, vol. 141 (2022)

work page 2022

[5] [3]

Aho, A.V., Corasick, M.J.: Eﬃcient string matching: an ai d to bibliographic search. Commun. ACM 18(6), 333–340 (1975). https://doi.org/10.1145/360825.360855

arXiv 1975

[6] [4]

In: Proceedings of the 2022 Annual ACM-SIAM Symposium on Discre te Algorithms (SODA)

Akmal, S., Jin, C.: Near-optimal quantum algorithms for s tring problems. In: Proceedings of the 2022 Annual ACM-SIAM Symposium on Discre te Algorithms (SODA). pp. 2791–2832. SIAM (2022)

work page 2022

[7] [5]

Allauzen, C., Crochemore, M., Raﬃnot, M.: Factor oracle: A new structure for pattern matching. In: SOFSEM’99: Theory and Practice of Inf ormatics: 26th Con- ference on Current Trends in Theory and Practice of Informat ics Milovy, Czech Quantum Algorithm for the Multiple String Matching Problem 11 Republic, November 27—December 4, 1999 Proceedings 26. pp. ...

work page 1999

[8] [6]

In: Proc

Ambainis, A.: Understanding quantum algorithms via quer y complexity. In: Proc. Int. Conf. of Math. 2018. vol. 4, pp. 3283–3304 (2018)

work page 2018