Quantum Algorithm for Lexicographically Minimal String Rotation
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2020
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909090365571072 |
|---|---|
| author | Wang, Qisheng Ying, Mingsheng |
| author_facet | Wang, Qisheng Ying, Mingsheng |
| contents | 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(\sqrt n \log n)$, which is shown to be asymptotically optimal up to a polylogarithmic factor, compared to its $Ω\left(\sqrt{n/\log n}\right)$ lower bound. Furthermore, we show that our quantum algorithm outperforms any (classical) randomized algorithms in both worst and average cases. As an application, it is used in benzenoid identification and disjoint-cycle automata minimization. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2012_09376 |
| institution | arXiv |
| publishDate | 2020 |
| record_format | arxiv |
| spellingShingle | Quantum Algorithm for Lexicographically Minimal String Rotation Wang, Qisheng Ying, Mingsheng Quantum Physics Computational Complexity Data Structures and Algorithms 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(\sqrt n \log n)$, which is shown to be asymptotically optimal up to a polylogarithmic factor, compared to its $Ω\left(\sqrt{n/\log n}\right)$ lower bound. Furthermore, we show that our quantum algorithm outperforms any (classical) randomized algorithms in both worst and average cases. As an application, it is used in benzenoid identification and disjoint-cycle automata minimization. |
| title | Quantum Algorithm for Lexicographically Minimal String Rotation |
| topic | Quantum Physics Computational Complexity Data Structures and Algorithms |
| url | https://arxiv.org/abs/2012.09376 |