Quantum DNA sequencing using Gaussian amplitude amplification

Authors

  • Richard A. Marin ⋅ PH Department of Physics, Mapúa University
  • Carlos F. Baldo III ⋅ PH Department of Physics, Mapúa University

Abstract

DNA or genome sequencing is a computationally expensive task that is NP-hard to solve in the worst-case scenario. This study demonstrates how to use the quantum pathfinding algorithm called Gaussian Amplitude Amplification (GAA) to solve the sequencing problem in k = (π/4)(|S||S|)1/2 successive oracle and diffusion operator applications where |S| is the number of l-mers in the spectrum. The simulation for the case l = 2 with |S| = 4 further revealed that the probability of finding the optimal solution is approximately 71.97%. While this study only focused on the ideal scenario where there are no errors in the spectrum, the result of this study demonstrates the plausibility of using GAA as a genome sequencing method.

Downloads

Issue

Article ID

SPP-2023-2H-03

Section

Theoretical and Mathematical Physics

Published

2023-07-08

How to Cite

[1]
RA Marin and CF Baldo, Quantum DNA sequencing using Gaussian amplitude amplification, Proceedings of the Samahang Pisika ng Pilipinas 41, SPP-2023-2H-03 (2023). URL: https://proceedings.spp-online.org/article/view/SPP-2023-2H-03.