One Liner:

A quantum algorithm that searches all rotations of a string in superposition to accelerate the search for its lexicographically minimal rotation.

Abstract:

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.

Video: https://1513041.mediaspace.kaltura.com/media/Gary+Pham+-+Quantum+Research+Senior+Design+2425+%28Prof.+Mark+Boardy+Supervision%29+-+Final+Term/1_byvrvdyi

Print Poster: View Poster

Digital: View Poster

Team Members

Advisors