date 8/27/2026
groups All Papers 2026 quantum xander
projects quantum
title Quantum Closest-Pair Search for Biological Sequences via k-Mer Distribution Statistics

import header.scroll
mediumColumns 1
printTitle

bibliography
 authors Zhezheng Xander Song and Carl Kingsford 
 year 2026
 citation In 26th International Conference on Algorithms for Bioinformatics (WABI 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 390, pp. 9:1-9:18
 link https://doi.org/10.4230/LIPIcs.WABI.2026.9

* 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. 

endSnippet

* 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.


paperlinks
 doi https://doi.org/10.4230/LIPIcs.WABI.2026.9

bibtexLink bibtex/2026-song-qsketch.bib
endColumns
import footer.scroll