2026-08-27T21:20:11Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27513 2026-08-27T06:04:07Z ddc:004 open_access

Quantum Closest-Pair Search for Biological Sequences via k-Mer Distribution Statistics Song, Zhezheng Xander Kingsford, Carl quantum algorithms closest-pair search k-mer statistics Bhattacharyya coefficient Dürr-Høyer maximum finding quantum amplitude estimation Finding highly similar pairs of biological sequences is a fundamental task in bioinformatics. For alignment-free k-mer distributional similarities, the induced feature space is high-dimensional and lacks the low-dimensional geometric structure used by classical exact closest-pair algorithms. Thus, for a collection of N sequences in the pairwise-score setting, exhaustive evaluation over the binom(N,2) candidate pairs is the natural classical baseline. We present the first quantum framework targeting alignment-free closest-pair search in biological sequence collections using distributional k-mer statistics. The central technical contribution is the construction of a coherent pairwise-score estimation circuit for this similarity measure. It encodes empirical k-mer distributions as square-root amplitude states and provides a sparse prefix-tree construction for preparing these states, under which the state overlap is exactly the Bhattacharyya coefficient. Standard SWAP-test and quantum-amplitude-estimation subroutines provide a coherent bounded-precision estimator for the squared Bhattacharyya overlap. We analyze maximum finding under an explicit assumption that a fixed ε-resolved total order over all legal pairs admits an efficient clean coherent implementation. Under this assumption, the procedure returns, with probability at least 2/3, a pair whose squared Bhattacharyya score is within ε of the optimal score, using O(N) expected comparison-oracle calls. If the optimal score is separated from every strictly suboptimal score by more than ε, the returned pair is exactly optimal. Combining this comparison-order assumption with an idealized qRAM-style data-access model gives the conditional sequential gate complexity Õ(NL/ε), whereas explicit multiplexed indexed loading gives Õ(N²L/ε). We also provide a proof-of-concept Q#implementation that integrates coherent indexed loading, SWAP-test-based score estimation, finite-precision marking, and Grover-style search, providing circuit-level validation of the main computational components. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Zhezheng Xander Song and Carl Kingsford 2026 Is Part Of LIPIcs, Volume 390, 26th International Conference on Algorithms for Bioinformatics (WABI 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.WABI.2026.9 urn:nbn:de:0030-drops-275130 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2026.9 eng https://creativecommons.org/licenses/by/4.0/legalcode