A quantum algorithm that searches all rotations of a string in superposition to accelerate the search for its lexicographically minimal rotation.
The lexicographically minimal string rotation (LMSR) problem aims to find the smallest rotation of a string in dictionary order. This problem has broad applications in text processing, bioinformatics, and data compression. Classical solutions like Booth’s algorithm solve LMSR in linear time. However, quantum computing has shown promise in accelerating search-based problems through superposition and parallelism. This project introduces a quantum algorithm for LMSR that leverages quantum parallelism to evaluate all string rotations simultaneously. The algorithm is implemented using IBM’s Qiskit and evaluated on near-term quantum hardware. While current devices still fall short of classical performance, the algorithm is further analyzed under the assumption of QRAM (Quantum Random Access Memory), a theoretical model for storing and retrieving quantum data efficiently. With QRAM support, the algorithm demonstrates the potential to outperform both classical methods and current quantum approaches.
Many objects, such as molecules, strings, or lists, can be rotated without altering their underlying structure. For example, the string "bat" has three cyclic rotations: "bat", "atb", and "tba". Among these, "atb" is the lexicographically smallest, and hence the LMSR. In chemistry, Benzenoids (a class of organic compounds containing benzene rings) exhibit similar symmetry: they can rotate while maintaining structural identity. Finding a canonical form like the LMSR helps standardize comparisons and calculations across such rotatable systems. Classical algorithms such as Booth’s exploit character comparisons to solve LMSR in linear time. But classical systems can only evaluate one rotation at a time. Quantum computers, in contrast, exploit superposition to represent multiple states simultaneously. This project harnesses that principle to encode all rotations of a string into a quantum state, enabling parallel evaluation of possible answers. The algorithm is built and tested using Qiskit, IBM’s quantum SDK. Although it currently runs slower than classical methods due to hardware limitations, it serves as a proof of concept. The design assumes two theoretical QRAM models - binary-tree-based and hash-based - to analyze future performance. With QRAM, the algorithm is expected to outperform the best-known classical approaches. Beyond LMSR, this framework generalizes to any problem involving rotatable data structures. It provides a subroutine that may be incorporated into more complex quantum routines requiring symmetry-breaking or canonicalization. For more details, follow this link to understand further the process of this research: https://kagamirudo.github.io/Quantum-Research-2024/index.html
Team Members
Gary Pham
gary.pham@drexel.edu
Advisors
Mark Boady
mwb33@drexel.edu