QiBAM: approximate sub-string index search on quantum accelerators applied to DNA read alignment
Open accessAbstract
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.
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
It basically extends Grover's search algorithm to allow for errors in the alignment between reads and the reference sequence stored in a quantum memory (QRAM).
“It basically extends Grover’s search algorithm to allow for errors in the alignment between reads and the reference sequence stored in a quantum memory (QRAM).”
From Quantum computing algorithms: getting closer to critical problems in computational biology (2022) · cites this paper as [140]
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Cites
A fast quantum mechanical algorithm for database search
Grover, L. K. (1996) · Proceedings of the twenty-eighth annual ACM symposium on Theory of computing - STOC '96 · doi:10.1145/237814.237866 · Cited by 8,830 · see citing works
Quantum Mechanics Helps in Searching for a Needle in a Haystack
Grover, L. K. (1997) · Physical Review Letters · doi:10.1103/physrevlett.79.325 · Cited by 4,306 · cited 1× · see citing works
“In this research, we will be developing the quantum search algorithm [12,13] on an unstructured database, as proposed by Lov Grover.”
MethodNeural-network quantum state tomography
Torlai, G., Mazzola, G., Carrasquilla, J., Troyer, M., Melko, R. G., & Carleo, G. (2018) · Nature Physics · doi:10.1038/s41567-018-0048-5 · Cited by 855 · see citing works
(1996) · Cited by 824 · see citing works
Synthesis of quantum-logic circuits
Shende, V., Bullock, S. S., & Markov, I. L. (2006) · IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems · doi:10.1109/tcad.2005.855930 · Cited by 682 · see citing works
Grover’s quantum searching algorithm is optimal
Zalka, C. (1999) · Physical Review A · doi:10.1103/physreva.60.2746 · Cited by 635 · see citing works
Brassard, G., Høyer, P., & Tapp, A. (1998) · Lecture notes in computer science · doi:10.1007/bfb0055105 · Cited by 322 · see citing works
Ventura, D. A. (2000) · Information Sciences · doi:10.1016/s0020-0255(99)00101-2 · Cited by 284 · see citing works
qHiPSTER: The Quantum High Performance Software Testing EnvironmentPreprint
Smelyanskiy, M., Sawaya, N. P. D., & Aspuru‐Guzik, A. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1601.07195 · Cited by 173 · see citing works
Hardware acceleration of BWA-MEM genomic short read mapping for longer read lengths
Houtgast, E. J., Sima, V.-M., Bertels, K., & Al-Ars, Z. (2018) · Computational Biology and Chemistry · doi:10.1016/j.compbiolchem.2018.03.024 · Cited by 148 · see citing works
Self-citationGrover’s quantum search algorithm for an arbitrary initial amplitude distribution
Biham, E., Biham, O., Biron, D., Grassl, M., & Lidar, D. A. (1999) · Physical Review A · doi:10.1103/physreva.60.2742 · Cited by 120 · see citing works
An experimental microarchitecture for a superconducting quantum processor
Fu, X., Rol, M. A., Bultink, C. C., van Someren, J., Khammassi, N., Ashraf, I., Vermeulen, R. F. L., de Sterke, J. C., Vlothuizen, W., Schouten, R. N., et al. (2017) · IEEE/ACM International Symposium on Microarchitecture (MICRO) · doi:10.1145/3123939.3123952 · Cited by 99 · see citing works
Self-citationQX: A high-performance quantum computer simulation platform
Khammassi, N., Ashraf, I., Fu, X., Almudéver, C. G., & Bertels, K. (2017) · Design, Automation, and Test in Europe · doi:10.23919/date.2017.7927034 · Cited by 98 · see citing works
Self-citationViamontes, G. F., Markov, I. L., & Hayes, J. P. (2005) · Computing in Science & Engineering · doi:10.1109/mcse.2005.53 · Cited by 90 · see citing works
QuASeR: Quantum Accelerated de novo DNA sequence reconstruction
Sarkar, A., Al-Ars, Z., & Bertels, K. (2021) · PLoS ONE · doi:10.1371/journal.pone.0249850 · Cited by 61 · see citing works
Self-citationOpenQL: A Portable Quantum Programming Framework for Quantum Accelerators
Khammassi, N., Ashraf, I., van Someren, J., Nane, R., Krol, A. M., Rol, M. A., Lao, L., Bertels, K., & Almudéver, C. G. (2021) · ACM Journal on Emerging Technologies in Computing Systems · doi:10.1145/3474222 · Cited by 60 · see citing works
Self-citationEfficient Decomposition of Unitary Matrices in Quantum Circuit Compilers
Krol, A. M., Sarkar, A., Ashraf, I., Al-Ars, Z., & Bertels, K. (2022) · Applied Sciences · doi:10.3390/app12020759 · Cited by 55 · see citing works
Self-citationQuantum associative memory with distributed queries
Ezhov, A. A., Nifanova, A. V., & Ventura, D. A. (2000) · Information Sciences · doi:10.1016/s0020-0255(00)00057-8 · Cited by 52 · see citing works
Quantum Computer Architecture: Towards Full-Stack Quantum Accelerators
Bertels, K., Sarkar, A., Hubregtsen, T., Serrao, M., Mouedenne, A. A., Yadav, A., Krol, A. M., & Ashraf, I. (2020) · Design, Automation, and Test in Europe · doi:10.23919/date48585.2020.9116502 · Cited by 46 · see citing works
Self-citationQuantum associative memory with exponential capacity
Ventura, D. A., & Martinez, T. R. (2002) · International Joint Conference on Neural Networks (IJCNN) · doi:10.1109/ijcnn.1998.682319 · Cited by 45 · see citing works
There’s Plenty of Room at the Bottom
Feynman, R. P. (2012) · The electrical engineering handbook/Electrical engineering handbook series/Electrical engineering handbook · doi:10.1201/b11930-3 · Cited by 45 · see citing works
Decoding surface code with a distributed neural network–based decoder
Varsamopoulos, S., Bertels, K., & Almudéver, C. G. (2020) · Quantum Machine Intelligence · doi:10.1007/s42484-020-00015-9 · Cited by 41 · see citing works
Self-citationEstimating Algorithmic Information Using Quantum Computing for Genomics Applications
Sarkar, A., Al-Ars, Z., & Bertels, K. (2021) · Applied Sciences · doi:10.3390/app11062696 · Cited by 37 · see citing works
Self-citationFast quantum search algorithms in protein sequence comparisons: Quantum bioinformatics
Hollenberg, L. C. L. (2000) · Physical Review E · doi:10.1103/physreve.62.7532 · Cited by 33 · see citing works
cQASM v1.0: Towards a Common Quantum Assembly LanguagePreprint
Khammassi, N., Guerreschi, G. G., Ashraf, I., Hogaboam, J., Almudéver, C. G., & Bertels, K. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1805.09607 · Cited by 29 · see citing works
Self-citationQuantum Computing—From NISQ to PISQ
Bertels, K., Sarkar, A., & Ashraf, I. (2021) · IEEE Micro · doi:10.1109/mm.2021.3099195 · Cited by 28 · see citing works
Self-citationQuantum Accelerated Computer Architectures
Riesebos, L., Fu, X., Mouedenne, A. A., Lao, L., Varsamopoulos, S., Ashraf, I., van Someren, J., Khammassi, N., Almudéver, C. G., & Bertels, K. (2019) · IEEE International Symposium on Circuits and Systems proceedings · doi:10.1109/iscas.2019.8702488 · Cited by 24 · see citing works
Self-citationA Quantum Associative Memory Based on Grover’s Algorithm
Ventura, D. A., & Martinez, T. R. (1999) · Artificial Neural Nets and Genetic Algorithms · doi:10.1007/978-3-7091-6384-9_5 · Cited by 21 · see citing works
Mathematical Grammar of Biology
Yamagishi, M. E. B. (2017) · SpringerBriefs in mathematics · doi:10.1007/978-3-319-62689-5 · Cited by 14 · see citing works
Quantum Associative Memory with Improved Distributed Queries
Njafa, J.-P. T., Engo, S. G. N., & Woafo, P. (2012) · International Journal of Theoretical Physics · doi:10.1007/s10773-012-1237-0 · Cited by 12 · see citing works
Artificial Associative Memory Using Quantum Processes
Ventura, D. A. (1998) · Cited by 11 · see citing works
Quantum Algorithms: for pattern-matching in genomic sequences
Sarkar, A. (2018) · Research Repository (Delft University of Technology) · Cited by 9 · see citing works
Self-citationGiannakis, K., Papalitsas, C., Theocharopoulou, G., Fanarioti, S., & Andronikos, T. (2019) · International Conference on Information, Intelligence, Systems & Applications (IISA) · doi:10.1109/iisa.2019.8900740 · Cited by 8 · see citing works
OpenQL : A Portable Quantum Programming Framework for Quantum AcceleratorsPreprint
Khammassi, N., Ashraf, I., van Someren, J., et al. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2005.13283 · Cited by 7 · see citing works
Quantum Pattern MatchingPreprint
Mateus, P., & Omar, Y. (2005) · arXiv (Cornell University) · doi:10.48550/arxiv.quant-ph/0508237 · Cited by 7 · see citing works
Sampling with quantum mechanicsPreprint
John, M. P. (2003) · arXiv (Cornell University) · doi:10.48550/arxiv.quant-ph/0306181 · Cited by 1 · see citing works
Flagged first, then by citations
Research works printed but not linked: 2
- Ventura, D.; Martinez, T. Initializing the amplitude distribution of a quantum state. Found. Phys. Lett. 1999, 12, 547-559. [CrossRef] · DOI
- Lao, L.; Manzano, D.M.; van Someren, H.; Ashraf, I.; Almudever, C.G. Mapping of quantum circuits onto NISQ superconducting processors. arXiv 2019, arXiv:1908.04226. · arXiv
Cited by
Sorted by citations
The state of quantum computing applications in health and medicine
Flöther, F. F. (2023) · Research Directions Quantum Technologies · doi:10.1017/qut.2023.4 · Cited by 128 · see citing works
Biology and medicine in the landscape of quantum advantages
Cordier, B. A., Sawaya, N. P. D., Guerreschi, G. G., & McWeeney, S. K. (2022) · Journal of The Royal Society Interface · doi:10.1098/rsif.2022.0541 · Cited by 87 · see citing works
Genome assembly using quantum and quantum-inspired annealing
Boev, A. S., Rakitko, A. S., Usmanov, S. R., Kobzeva, A. N., Popov, I. V., Ilinsky, V. V., Kiktenko, E. O., & Fedorov, A. K. (2021) · Scientific Reports · doi:10.1038/s41598-021-88321-5 · Cited by 63 · see citing works
Towards practical applications in quantum computational biology
Fedorov, A. K., & Gelfand, M. S. (2021) · Nature Computational Science · doi:10.1038/s43588-021-00024-z · Cited by 62 · see citing works
QuASeR: Quantum Accelerated de novo DNA sequence reconstruction
Sarkar, A., Al-Ars, Z., & Bertels, K. (2021) · PLoS ONE · doi:10.1371/journal.pone.0249850 · Cited by 61 · see citing works
Self-citationEfficient Decomposition of Unitary Matrices in Quantum Circuit Compilers
Krol, A. M., Sarkar, A., Ashraf, I., Al-Ars, Z., & Bertels, K. (2022) · Applied Sciences · doi:10.3390/app12020759 · Cited by 55 · see citing works
Self-citationQuantum computing in bioinformatics: a systematic review mapping
Nałęcz-Charkiewicz, K., Charkiewicz, K., & Nowak, R. M. (2024) · Briefings in Bioinformatics · doi:10.1093/bib/bbae391 · Cited by 54 · see citing works
Quantum computing algorithms: getting closer to critical problems in computational biology
Marchetti, L., Nifosì, R., Martelli, P. L., Da Pozzo, E., Cappello, V., Banterle, F., Trincavelli, M. L., Martini, C., & D’Elia, M. (2022) · Briefings in Bioinformatics · doi:10.1093/bib/bbac437 · Cited by 47 · see citing works
Quantum Computer Architecture: Towards Full-Stack Quantum Accelerators
Bertels, K., Sarkar, A., Hubregtsen, T., Serrao, M., Mouedenne, A. A., Yadav, A., Krol, A. M., & Ashraf, I. (2020) · Design, Automation, and Test in Europe · doi:10.23919/date48585.2020.9116502 · Cited by 46 · see citing works
Self-citationQuantum computing research in medical sciences
Alrashed, S., & Min‐Allah, N. (2024) · Informatics in Medicine Unlocked · doi:10.1016/j.imu.2024.101606 · Cited by 40 · see citing works
Estimating Algorithmic Information Using Quantum Computing for Genomics Applications
Sarkar, A., Al-Ars, Z., & Bertels, K. (2021) · Applied Sciences · doi:10.3390/app11062696 · Cited by 37 · see citing works
Self-citationQuantum Computer Architecture Toward Full-Stack Quantum Accelerators
Bertels, K., Sarkar, A., Hubregtsen, T., Serrao, M., Mouedenne, A. A., Yadav, A., Krol, A. M., Ashraf, I., & Almudéver, C. G. (2020) · IEEE Transactions on Quantum Engineering · doi:10.1109/tqe.2020.2981074 · Cited by 35 · see citing works
Self-citationFrom GPUs to AI and quantum: three waves of acceleration in bioinformatics
Schmidt, B., & Hildebrandt, A. (2024) · Drug Discovery Today · doi:10.1016/j.drudis.2024.103990 · Cited by 28 · see citing works
Mokhtari, M., Khoshbakht, S., Ziyaei, K., Akbari, M. E., & Moravveji, S. S. (2024) · Briefings in Bioinformatics · doi:10.1093/bib/bbae074 · Cited by 24 · see citing works
QPack: Quantum Approximate Optimization Algorithms as universal benchmark for quantum computersPreprint
Mesman, K. J., Al-Ars, Z., & Möller, M. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2103.17193 · Cited by 23 · see citing works
Self-citationApplications of Quantum Computing in Health Sector
Arshad, M. W., Murtza, I., & Arshad, M. A. (2023) · Journal of Data Science and Intelligent Systems · doi:10.47852/bonviewjdsis3202656 · Cited by 21 · see citing works
The Future of Drug Development with Quantum Computing
Bonde, B. K., Patil, P., & Choubey, B. (2023) · Methods in molecular biology · doi:10.1007/978-1-0716-3449-3_7 · Cited by 19 · see citing works
Complexity of life sciences in quantum and AI era
Pyrkov, A. N., Aliper, A., Bezrukov, D. S., Podolskiy, D. I., Ren, F., & Zhavoronkov, A. A. (2024) · Wiley Interdisciplinary Reviews Computational Molecular Science · doi:10.1002/wcms.1701 · Cited by 17 · see citing works
Matarèse, B. F. E., & Purushotham, A. D. (2025) · Quantum Reports · doi:10.3390/quantum7010009 · Cited by 17 · see citing works
Quantum computing on nucleic acid research: Approaching towards next-generation computing
Chakraborty, C., Bhattacharya, M., Dhama, K., & Lee, S. (2023) · Molecular Therapy — Nucleic Acids · doi:10.1016/j.omtn.2023.06.007 · Cited by 14 · see citing works
Quantum Accelerator Stack: A Research RoadmapPreprint
Bertels, K., Sarkar, A., Krol, A. M., Budhrani, R., Samadi, J., Geoffroy, E., Matos, J. S., Abreu, R., Gielen, G. E., & Ashraf, I. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2102.02035 · Cited by 14 · see citing works
Self-citationReview of quantum algorithms for medicine, finance and logistics
Ciacco, A., Guerriero, F., & Macrina, G. (2025) · Soft Computing · doi:10.1007/s00500-025-10540-z · Cited by 12 · see citing works
Quantum Computing for Genomics: Conceptual Challenges and Practical Perspectives
Maurizio, A., & Mazzola, G. (2025) · PRX Life · doi:10.1103/h49j-bsc6 · Cited by 10 · see citing works
Quantum Accelerated Pattern Matching for Genome Sequencing in Complex RNA Secondary Structures
De, R. (2022) · IEEE International Conference on Quantum Computing and Engineering (QCE) · doi:10.1109/qce53715.2022.00139 · Cited by 5 · see citing works
Integration and Evaluation of Quantum Accelerators for Data-Driven User Functions
Hubregtsen, T., Segler, C., Pichlmeier, J., Sarkar, A., Gabor, T., & Bertels, K. (2020) · International Symposium on Quality Electronic Design (ISQED) · doi:10.1109/isqed48828.2020.9137029 · Cited by 5 · see citing works
Self-citationQuantum Accelerated Estimation of Algorithmic Information.Preprint
Sarkar, A., Al-Ars, Z., & Bertels, K. (2020) · arXiv (Cornell University) · Cited by 4 · see citing works
Self-citationString Comparison on a Quantum Computer Using Hamming DistancePreprint
Khan, M., & Miranskyy, A. V. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2106.16173 · Cited by 4 · see citing works
QOMIC: quantum optimization for motif identification
Ngo, H. M., Khatib, T., Thai, M. T., & Kahveci, T. (2024) · Bioinformatics Advances · doi:10.1093/bioadv/vbae208 · Cited by 3 · see citing works
Quantum–Classical Optimization for Efficient Genomic Data Transmission
Soto, I., García, V., & Játiva, P. P. (2025) · Mathematics · doi:10.3390/math13172792 · Cited by 2 · see citing works
A Survey on Sequence Alignment Algorithms and State-of-the-Art Aligners
Prousalis, K. P., Georgiou, K., Καλογερόπουλος, Α., Ntalaperas, D., Konofaos, N., Angelis, L., Papalitsas, C., Stavropoulos, T. G., & Gariboldi, N. (2025) · ACM Computing Surveys · doi:10.1145/3763229 · Cited by 2 · see citing works
ACSS-q: Algorithmic complexity for short strings via quantum accelerated approachPreprint
Sarkar, A., & Bertels, K. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2009.08866
Self-citationHardware accelerators for processing clusters in binary vectors
Skliarova, I., & Skliarov, V. (2024) · ITM Web of Conferences · doi:10.1051/itmconf/20246000010
Dedicated Bioinformatics Analysis Hardware
Schmidt, B., & Hildebrandt, A. (2024) · Elsevier eBooks · doi:10.1016/b978-0-323-95502-7.00022-1
Quantum algorithm for identifying RNA 3D motifs by processing RNA secondary structure graphsPreprint
Fang, J.-K., Guo, F., Ma, T., Zhang, Y., Wang, O., Huang, J.-H., & Li, Y. (2025) · bioRxiv (Cold Spring Harbor Laboratory) · doi:10.1101/2025.04.25.650554
Beyond the hype: an empirical assessment of quantum computing in bioinformatics
Arcieri, M., Zuliani, P., Carotenuto, G., Carrus, M., & Castrignanò, T. (2026) · Frontiers in High Performance Computing · doi:10.3389/fhpcp.2026.1923360
- Authors
- Sarkar, A., Al-Ars, Z., Almudever, C. G., & Bertels, K. L. M.
- Affiliations
- Delft University of Technology (NL)
- Department of Quantum & Computer Engineering, Faculty of Electrical Engineering, Mathematics and Computer Science, Delft University of Technology, 2628 CD Delft, The Netherlands
- KU Leuven (BE)
- Corresponding author
- Sarkar, Aritra
- Venue
- Electronics
- Publisher
- MDPI AG
- Published
- 2021-10-07
- Volume
- 10
- Issue
- 19
- Pages
- 2433
- ISSN
- 2079-9292 (ISSN-L)
- OpenAlex
- W3204611084
- Cited by
- 20
- References
- 33
- Citations by year
- 2026: 1 · 2025: 6 · 2024: 8 · 2023: 3 · 2022: 2
- FWCI
- 1.15
- Type
- journal article
- Language
- en
- Open access
- gold
- doi.org
- Licence
- Locations
- Electronics (publishedVersion, cc-by)
- Lirias (submittedVersion, cc-by)
- DOAJ (DOAJ: Directory of Open Access Journals) (submittedVersion, cc-by-sa)
- Research Repository (Delft University of Technology) (submittedVersion, cc-by)
- Data Archiving and Networked Services (DANS) (submittedVersion, other-oa)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
- Physical Sciences › Computer Science › Artificial Intelligence › Algorithms and Data Compression
- Life Sciences › Biochemistry, Genetics and Molecular Biology › Molecular Biology › DNA and Biological Computing
- Keywords
- quantum computing, approximate pattern matching, Hamming distance, Grover's algorithm, quantum accelerators, distributed search
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
