Quantum Algorithm for Lexicographically Minimal String Rotation

Wang, Q; Ying, M

Quantum Algorithm for Lexicographically Minimal String Rotation

Wang, Q Ying, M

Permalink

Publisher:: SPRINGER
Publication Type:: Journal Article
Citation:: Theory of Computing Systems, 2023, 68, (1)
Issue Date:: 2023-01-01

Recently Added

	Filename	Description	Size
	Quantum Algorithm for Lexicographically Minimal String Rotation.pdf	Published version	643.97 kB	Adobe PDF	View/Open

Copyright Clearance Process

Recently Added
In Progress
Open Access

This item is new to OPUS and is not currently available.

Full metadata record

Field	Value	Language
dc.contributor.author	Wang, Q
dc.contributor.author	Ying, M https://orcid.org/0000-0003-4847-702X
dc.date.accessioned	2024-02-08T04:00:51Z
dc.date.available	2024-02-08T04:00:51Z
dc.date.issued	2023-01-01
dc.identifier.citation	Theory of Computing Systems, 2023, 68, (1)
dc.identifier.issn	1432-4350
dc.identifier.issn	1433-0490
dc.identifier.uri	http://hdl.handle.net/10453/175482
dc.description.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(n3 / 4) quantum query algorithm for LMSR. In particular, the algorithm has average-case query complexity O(nlogn) , which is shown to be asymptotically optimal up to a polylogarithmic factor, compared to its Ω(n/logn) 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.
dc.language	English
dc.publisher	SPRINGER
dc.relation	National Natural Science Foundation of China61832015
dc.relation.ispartof	Theory of Computing Systems
dc.relation.isbasedon	10.1007/s00224-023-10146-8
dc.rights	info:eu-repo/semantics/restrictedAccess
dc.subject	0102 Applied Mathematics, 0802 Computation Theory and Mathematics, 0805 Distributed Computing
dc.subject.classification	Computation Theory & Mathematics
dc.subject.classification	4606 Distributed computing and systems software
dc.subject.classification	4613 Theory of computation
dc.subject.classification	4901 Applied mathematics
dc.title	Quantum Algorithm for Lexicographically Minimal String Rotation
dc.type	Journal Article
utslib.citation.volume	68
utslib.for	0102 Applied Mathematics
utslib.for	0802 Computation Theory and Mathematics
utslib.for	0805 Distributed Computing
pubs.organisational-group	University of Technology Sydney
pubs.organisational-group	University of Technology Sydney/Faculty of Engineering and Information Technology
pubs.organisational-group	University of Technology Sydney/Strength - QSI - Centre for Quantum Software and Information
utslib.copyright.status	recently_added	*
dc.date.updated	2024-02-08T04:00:50Z
pubs.issue	1
pubs.publication-status	Published
pubs.volume	68
utslib.citation.issue	1

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(n3 / 4) quantum query algorithm for LMSR. In particular, the algorithm has average-case query complexity O(nlogn) , which is shown to be asymptotically optimal up to a polylogarithmic factor, compared to its Ω(n/logn) 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.

Please use this identifier to cite or link to this item:

http://hdl.handle.net/10453/175482