Quantum algorithm for lexicographically minimal string rotation

DOI10.1007/S00224-023-10146-8MaRDI QIDQ6151147zbMATH OpenOpenAlexFDO

Authors Qisheng Wang, Mingsheng Ying

Publication date 9 February 2024

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

Copyright license Creative Commons Attribution 4.0 International

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)

Abstract: Lexicographically minimal string rotation (LMSR) is a problem to find the minimal one among all rotations of a string in the lexicographical order, which is widely used in equality checking of graphs, polygons, automata and chemical structures. In this paper, we propose an $O(n^{3/4})$ quantum query algorithm for LMSR. In particular, the algorithm has average-case query complexity $O(sqrtnlogn)$, which is shown to be asymptotically optimal up to a polylogarithmic factor, compared with its $Omegaleft(sqrtn/lognight)$ lower bound. Furthermore, we claim that our quantum algorithm outperforms any (classical) randomized algorithms in both worst-case and average-case query complexities by showing that every (classical) randomized algorithm for LMSR has worst-case query complexity $Omega(n)$ and average-case query complexity $Omega(n/logn)$. Our quantum algorithm for LMSR is developed in a framework of nested quantum algorithms, based on two new results: (i) an $O(sqrtn)$ (optimal) quantum minimum finding on bounded-error quantum oracles; and (ii) its $Oleft(sqrtnlog(1/varepsilon)ight)$ (optimal) error reduction. As a byproduct, we obtain some better upper bounds of independent interest: (i) $O(sqrtN)$ (optimal) for constant-depth MIN-MAX trees on $N$ variables; and (ii) $O(sqrtnlogm)$ for pattern matching which removes $operatornamepolylog(n)$ factors.

Recommendations

• Near-optimal quantum algorithms for string problems
• Near-optimal quantum algorithms for string problems
• Quantum algorithms for the most frequently string search, intersection of two string sequences and sorting of strings problems
• Reconstructing strings from substrings with quantum queries

Cites work

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

Cited in

(7)

• Near-optimal quantum algorithms for string problems
• A note on quantum divide and conquer for minimal string rotation
• Simple linear time algorithm for sorting strings in omega-order with applications
• Internal pattern matching queries in a text and applications
• Near-optimal quantum algorithms for string problems
• Quantum data structure for range minimum query
• Double-ended palindromic trees in linear time

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

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