Quantum algorithm for lexicographically minimal string rotation

DOI10.1007/s00224-023-10146-8arXiv2012.09376OpenAlexW4387906876MaRDI QIDQ6151147

Ming Sheng Ying, Qisheng Wang

Publication date: 9 February 2024

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2012.09376

zbMATH Keywords

quantum algorithmsquantum computingstring problemsquantum query complexitylexicographically minimal string rotation

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Theory of computing (68Qxx) Foundations, quantum information and its processing, quantum axioms, and philosophy (81Pxx)

Cites Work

• A surprisingly simple de Bruijn sequence construction
• Quantum pattern matching fast on average
• Automata for branching and layered temporal structures. An investigation into regularities of infinite transition systems
• String matching in \(\tilde O(\sqrt n+\sqrt m)\) quantum time
• Description and analysis of a bottom-up DFA minimization algorithm
• Lexicographically least circular substrings
• String-matching on ordered alphabets
• Optimal algorithms for computing the canonical form of a circular string
• Minimisation of acyclic deterministic automata in linear time
• A fast equivalence-checking algorithm for circular lists
• Nested quantum search and NP-hard problems
• Constructing de Bruijn sequences with co-lexicographic order: the \(k\)-ary grandmama sequence
• The standard factorization of Lyndon words: an average point of view
• Complexity measures and decision tree complexity: a survey.
• On maximal suffixes and constant-space linear-time versions of KMP algorithm.
• A lower bound on the quantum query complexity of read-once functions
• Minimisation of automata
• Quantum meets fine-grained complexity: sublinear time quantum algorithms for string problems
• Average-case quantum query complexity
• Reconstructing Strings from Substrings with Quantum Queries
• Factorizing words over an ordered alphabet
• Linear work suffix array construction
• Quantum verification of matrix products
• Linear Time Automorphism Algorithms for Trees, Interval Graphs, and Planar Graphs
• Fast canonization of circular strings
• A Space-Economical Suffix Tree Construction Algorithm
• Fast Pattern Matching in Strings
• Strengths and Weaknesses of Quantum Computing
• Handbook of Graph Theory
• A fast average case algorithm for lyndon decomposition
• Probability Inequalities for Sums of Bounded Random Variables
• Quantum Algorithms for the Triangle Problem
• Quantum lower bounds by polynomials
• Algorithms on Strings
• Quantum Walk Algorithm for Element Distinctness
• Quantum Algorithms for Evaluating Min-Max Trees
• Nested Quantum Walks with Quantum Data Structures
• Quantum lower bounds by quantum arguments
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Quantum algorithm for lexicographically minimal string rotation