Speaker
Description
The Levenshtein (edit) distance is a fundamental measure of string similarity, central to genomics, natural-language processing, databases, and coding theory.
However, it is costly to compute, and Hamming-based quantum fingerprints are ill-suited for it, since rigid position alignment collapses under a single insertion or deletion.
We introduce a quantum encoding of sequences, built from the rotary position embeddings, in which a positional shift acts as a global phase rather than a re-indexing. The fidelity between encoded states is then strongly and smoothly correlated with the Levenshtein distance, robustly up to sequences of a billion symbols. The encoding is classically computable in linear time, and batched comparison reduces to a single matrix multiplication. Exploiting this, our quantum-inspired GPU-accelerated mapper RotorMap aligns long DNA reads $50$ - $700\times$ faster than Minimap2 running on a single thread. For quantum hardware we introduce the Angular encoding, which prepares a correlation-preserving state directly and which we validate on QPUs. As a potential application, we consider a quantum DNA authentication problem and conjecture that a quantum advantage in one-way communication complexity could be achieved over any comparable classical solution.
| Topic | Encoding and processing of data in quantum systems |
|---|