Quantum property testing algorithm for the concatenation of two palindromes language

DOI10.1007/978-3-031-63742-1_10MaRDI QIDQ7013620zbMATH OpenFDO

Authors Kamil Khadiev, Danil Serov

Publication date 12 March 2025

Full work available at URL https://doi.org/10.1007/978-3-031-63742-1_10

zbMATH Keywords

context-free languagespalindromesproperty testingquantum algorithmsquery complexitystrings

Mathematics Subject Classification ID

Biologically inspired models of computation (DNA computing, membrane computing, etc.) (68Q07) Other nonclassical models of computation (68Q09) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Quantum algorithms and complexity in the theory of computing (68Q12)

Cites work

• A quantum query complexity trichotomy for regular languages
• Advanced Data Structures
• Algorithms and Computation
• Classical and Quantum Algorithms for Assembling a Text from a Dictionary
• Classical and quantum algorithms for constructing text from dictionary problem
• Fast Pattern Matching in Strings
• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• scientific article; zbMATH DE number 1256737 (Why is no real title available?)
• scientific article; zbMATH DE number 2156274 (Why is no real title available?)
• Introduction to algorithms
• Near-optimal quantum algorithms for string problems
• Property testing and its connection to learning and approximation
• Quantum algorithm for Dyck language with multiple types of brackets
• Quantum algorithms for string processing
• Quantum algorithms for the most frequently string search, intersection of two string sequences and sorting of strings problems
• Quantum bounds for 2D-grid and Dyck language
• Quantum computation and quantum information. 10th anniversary edition
• Quantum meets fine-grained complexity: sublinear time quantum algorithms for string problems
• Quantum pattern matching fast on average
• Quantum Property Testing
• Regular languages are testable with a constant number of queries
• Robust Characterizations of Polynomials with Applications to Program Testing
• Simulation methods for quantum walks on graphs applied to formal language recognition
• Strengths and Weaknesses of Quantum Computing
• String matching in O( n+ m) quantum time
• Testing membership in parenthesis languages

This page was built for publication: Quantum property testing algorithm for the concatenation of two palindromes language

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