Quantum Algorithm Analysis for Lexicographically Minimal String Rotation Problem

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.