Quantum algorithms for sequence alignment and assembly
Your genome is about three billion letters long. Sequencing machines read it in short fragments that must be aligned to a reference and assembled, and comparing sequences across species, patients or tumours is the daily work of genomics. These are classical string problems, and they are expensive at scale. Could Grover-style speedups or quantum annealing help? Here the honest answer is short, and instructive.
On the plate: aligning two sequences by dynamic programming.
Alignment and its classical limit
The Smith–Waterman algorithm (1981) finds the best local alignment of two sequences by filling a table: each cell scores the best alignment ending there, from its three neighbours (match or mismatch, gap in one sequence, gap in the other). For sequences of lengths and it costs . Arturs Backurs and Piotr Indyk proved in 2015 that edit distance cannot be computed in strongly subquadratic time unless the strong exponential time hypothesis (SETH) fails, so the quadratic cost is likely optimal classically. Practical tools such as BLAST and BWA use heuristics and indexing to avoid the full table. Established
Align, then count queries
Align , with mismatch penalty 1.0 and gap penalty 1.0 (match +2). The plate fills the table and traces back the best local alignment. For exact pattern matching, Hariharan Ramesh and V. Vinay gave in 2003 a quantum algorithm using about queries for a pattern of length in a text of length ; Ashley Montanaro showed in 2017 that average-case speedups can be larger. Annealing-based assembly, such as QuASeR in 2021, maps fragment ordering to a QUBO. Established as algorithms.
The critique
A quadratic query speedup needs the genome inside a quantum memory that can be queried in superposition, which no hardware provides and which would itself take about operations to load (Chapter 120). Ryan Babbush and colleagues showed in 2021 that, after error-correction overheads, quadratic speedups need enormous problem sizes and days of runtime to beat classical computers, and modest-size genomics problems run in seconds on GPUs. Annealing-based assembly has not beaten classical assemblers. Genomics is a poor near-term target for quantum computing. Speculative; practically unlikely in the near term.
What you now have
Smith–Waterman alignment, the SETH-based quadratic lower bound, practical heuristics, quantum pattern matching with square-root query counts, annealing-based assembly, and why I/O and error-correction overhead cancel quadratic speedups.
· · ·
Three questions to carry with you.
And one to work out. For a text of letters, about how many queries is ?
Sources: T. F. Smith and M. S. Waterman, J. Mol. Biol. 147, 195 (1981). A. Backurs and P. Indyk, Proc. 47th ACM STOC, 51 (2015). H. Ramesh and V. Vinay, J. Discrete Algorithms 1, 103 (2003). A. Montanaro, Algorithmica 77, 16 (2017). A. Sarkar et al., PLoS One 16, e0249850 (2021) (QuASeR). R. Babbush et al., PRX Quantum 2, 010103 (2021).