QiBAM: Approximate Sub-String Index Search on Quantum Accelerators Applied to DNA Read Alignment

Aritra Sarkar, Zaid Al-Ars, Carmen G. Almudever, Koen L.M. Bertels

Research output: Contribution to journalArticleScientificpeer-review

66 Downloads (Pure)


With small-scale quantum processors transitioning from experimental physics labs to industrial products, these processors in a few years are expected to scale up and be more robust for efficiently computing important algorithms in various fields. In this paper, we propose a quantum algorithm to address the challenging field of data processing for genome sequence reconstruction. This research describes an architecture-aware implementation of a quantum algorithm for sub-sequence alignment. A new algorithm named QiBAM (quantum indexed bidirectional associative memory) is proposed, which uses approximate pattern-matching based on Hamming distances. QiBAM extends the Grover’s search algorithm in two ways, allowing: (1) approximate matches needed for read errors in genomics, and (2) a distributed search for multiple solutions over the quantum encoding of DNA sequences. This approach gives a quadratic speedup over the classical algorithm. A full implementation of the algorithm is provided and verified using the OpenQL compiler and QX Simulator framework. Our implementation represents a first exploration towards a full-stack quantum accelerated genome sequencing pipeline design.
Original languageEnglish
Article number2433
Pages (from-to)1-17
Number of pages17
JournalElectronics (Switzerland)
Issue number19
Publication statusPublished - 2021


  • accelerator architectures
  • associative memory
  • DNA read alignment
  • genomics
  • pattern matching
  • quantum algorithms
  • quantum computing
  • quantum search


Dive into the research topics of 'QiBAM: Approximate Sub-String Index Search on Quantum Accelerators Applied to DNA Read Alignment'. Together they form a unique fingerprint.

Cite this