A general quantum circuit for string matching: unleashing quantum path parallelism

DOI10.1016/J.TCS.2026.116059MaRDI QIDQ7263473zbMATH OpenFDO

Authors Simone Faro, Arianna Pavone, C. Viola

Publication date 12 June 2026

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.TCS.2026.116059

zbMATH Keywords

quantum computingsequence analysistext processing

Mathematics Subject Classification ID

Quantum algorithms and complexity in the theory of computing (68Q12) Theory of computing (68Qxx) Algorithms on strings (68W32)

Cites work

• A single quantum cannot be cloned
• Approximating Edit Distance in Truly Subquadratic Time: Quantum and MapReduce
• Average-optimal string matching
• scientific article; zbMATH DE number 1809602 (Why is no real title available?)
• scientific article; zbMATH DE number 1256737 (Why is no real title available?)
• scientific article; zbMATH DE number 2183071 (Why is no real title available?)
• scientific article; zbMATH DE number 801745 (Why is no real title available?)
• scientific article; zbMATH DE number 845841 (Why is no real title available?)
• Overlap matching.
• Parallel quantum computation and quantum codes
• Pattern Matching with Swaps
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Quantum fan-out is powerful
• Quantum lower bounds by polynomials
• Quantum lower bounds for fanout
• Quantum meets fine-grained complexity: sublinear time quantum algorithms for string problems
• Quantum pattern matching fast on average
• Quantum random access memory
• Quantum string matching unfolded and extended
• String matching in O( n+ m) quantum time
• String matching with up to k swaps and mismatches

This page was built for publication: A general quantum circuit for string matching: unleashing quantum path parallelism

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7263473)