Quantum DNA sequencing using Gaussian amplitude amplification

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.